|Regular expressions; cannonical form and reducer? email@example.com (1998-03-06)|
|Re: Regular expressions; cannonical form and reducer? firstname.lastname@example.org (Mats Kindahl) (1998-03-07)|
|Re: Regular expressions; cannonical form and reducer? zss@ZenSpider.com (1998-03-07)|
|Re: Regular expressions; cannonical form and reducer? email@example.com (Paul Dietz) (1998-03-08)|
|Re: Regular expressions; cannonical form and reducer? firstname.lastname@example.org (Henry Spencer) (1998-03-08)|
|From:||Mats Kindahl <email@example.com>|
|Date:||7 Mar 1998 22:33:07 -0500|
Gregory Guthrie wrote:
> I am interested in any references to a standard cannonical form for
> regular expressions, and any system that would transform Regex into
> such forms.
> This would, for example allow one to test equivalence of two Regex
> Seems like this should either exist, or be impossible. :-)
It would certainly be possible to construct a canonical form for
regular expressions, but using automata as canonical form would be
The easiest way would probably be to construct an DFA for the regular
expression and then reduce it using a slightly modified version of
Paige-Tarjan's algorithm to compute a reduced graph with bisimilar
Robert Paige and Robert E. Tarjan.
Three partition refinement algorithms.
SIAM Journal on Computing,
16(6):973-989, December 1987.
Return to the
Search the comp.compilers archives again.