Re: Regular expressions; cannonical form and reducer?

Mats Kindahl <matkin@iar.se>
7 Mar 1998 22:33:07 -0500

          From comp.compilers
Related articles
Regular expressions; cannonical form and reducer? guthrie@mum.edu (1998-03-06)
Re: Regular expressions; cannonical form and reducer? matkin@iar.se (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? dietz@interaccess.com (Paul Dietz) (1998-03-08)
Re: Regular expressions; cannonical form and reducer? henry@zoo.toronto.edu (Henry Spencer) (1998-03-08)
| List of all articles for this month |
From: Mats Kindahl <matkin@iar.se>
Newsgroups: comp.compilers
Date: 7 Mar 1998 22:33:07 -0500
Organization: IAR Systems
References: 98-03-034
Keywords: DFA

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
> forms.
>
> 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
more appropriate.


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
states merged.


Regards,
Mats Kindahl


A reference:


Robert Paige and Robert E. Tarjan.
Three partition refinement algorithms.
SIAM Journal on Computing,
          16(6):973-989, December 1987.
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.