Re: Perfecting State Elimination (Anton Ertl)
Mon, 01 Oct 2007 15:07:29 GMT

          From comp.compilers

Related articles
Perfecting State Elimination (Bjoern Hoehrmann) (2007-10-01)
Re: Perfecting State Elimination (2007-10-01)
Re: Perfecting State Elimination (Bjoern Hoehrmann) (2007-10-01)
| List of all articles for this month |

From: (Anton Ertl)
Newsgroups: comp.compilers
Date: Mon, 01 Oct 2007 15:07:29 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 07-10-006
Keywords: DFA, lex, optimize
Posted-Date: 01 Oct 2007 12:07:54 EDT

Bjoern Hoehrmann <> 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.

- anton
M. Anton Ertl

Post a followup to this message

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