Re: Regular expressions; cannonical form and reducer?

Paul Dietz <dietz@interaccess.com>
8 Mar 1998 12:07:02 -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: Paul Dietz <dietz@interaccess.com>
Newsgroups: comp.compilers
Date: 8 Mar 1998 12:07:02 -0500
Organization: InterAccess Co., Chicago's Full Service Internet Provider
References: 98-03-034 98-03-060
Keywords: DFA, comment

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.


The problem of testing the equivalence of two regular expressions
is PSPACE complete. Converting to deterministic automata (for
which equivalence can be checked efficiently) doesn't help,
because the automata can have exponentially many states.


Paul
[Sounds like a situation which is intractible in theory but usually
works in practice. People turn expressions into DFAs all the time,
e.g. in lex, and the exponential blowup just doesn't happen on useful
expressions. -John]
--

Post a followup to this message

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