Re: Perfecting State Elimination

anton@mips.complang.tuwien.ac.at (Anton Ertl)
Mon, 01 Oct 2007 15:07:29 GMT

          From comp.compilers

Related articles
Perfecting State Elimination bjoern@hoehrmann.de (Bjoern Hoehrmann) (2007-10-01)
Re: Perfecting State Elimination anton@mips.complang.tuwien.ac.at (2007-10-01)
Re: Perfecting State Elimination bjoern@hoehrmann.de (Bjoern Hoehrmann) (2007-10-01)
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (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

Bjoern Hoehrmann <bjoern@hoehrmann.de> 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
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/



Post a followup to this message

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