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) |
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]
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.