|Perfecting State Elimination email@example.com (Bjoern Hoehrmann) (2007-10-01)|
|Re: Perfecting State Elimination firstname.lastname@example.org (2007-10-01)|
|Re: Perfecting State Elimination email@example.com (Bjoern Hoehrmann) (2007-10-01)|
|From:||firstname.lastname@example.org (Anton Ertl)|
|Date:||Mon, 01 Oct 2007 15:07:29 GMT|
|Organization:||Institut fuer Computersprachen, Technische Universitaet Wien|
|Keywords:||DFA, lex, optimize|
Bjoern Hoehrmann <email@example.com> writes:
> I am trying to find a method that will make regular expressions as
>short as possible (say, using only concatenation, alternation, zero or
>more repetition, characters and epsilon, I want to minimize the number
>of characters) given limited resources. I could not find much material
>on the problem on the web, except that I can turn the expression into
>a minimal DFA and the DFA into a regular expression using state elimi-
>nation, and that some removal sequences are better than others.
My feeling is that that approach is wrong, because a regexp
corresponds to an NFA, and a DFA can be much larger than an equivalent
NFA, so a regexp generated from the DFA is likely to be suboptimal,
unless the DFA->regexp step reintroduces nondeterminism.
M. Anton Ertl
Return to the
Search the comp.compilers archives again.