|Perfecting State Elimination firstname.lastname@example.org (Bjoern Hoehrmann) (2007-10-01)|
|Re: Perfecting State Elimination email@example.com (2007-10-01)|
|Re: Perfecting State Elimination firstname.lastname@example.org (Bjoern Hoehrmann) (2007-10-01)|
|From:||Bjoern Hoehrmann <email@example.com>|
|Date:||Mon, 01 Oct 2007 18:23:25 +0200|
* Bjoern Hoehrmann wrote in comp.compilers:
I originally posted this in August, I suppose it got stuck in the
moderator's queue. [Stuck at his ISP, actually. -John]
I might as well answer my own question. While the transformation I
discussed is generally a good one, there is of course the inevitable
blowup caused by determinization of the auto- maton.
Unfortunately in my case I already start out with a DFA and would
need a small epsilon-NFA instead. Now NFA minimization is hard
and I haven't found any suitable reduction algorithm that would be
useful for my purposes. What I did come up with is this algorithm
that will compute a comperatively good removal sequence:
1. Ensure the automaton has only a single start and a single
final state with no incoming and respectively outgoing
transitions by adding new states and epsilon transitions
2. Compute for each state x which states are on all paths
Start --> x --> Final. This can be done in two breadth-
first traversals; for endpoint --> endpoint only the end-
point is on the path. For all others, the states that are
on the paths for all successors/predecessors are on the
path plus the state itself.
A simple approach would be to use a bitmap, starting with
all cells set to true, then setting the row for the end-
point, and during the traversal binary-and'ing the rows
of sucessors/predecessors with the current state's row
(while keeping bitmap[x][x] true).
3. Remove a state only after removing all states that must
visit it. In simple terms, this will collapse the auto-
maton starting with the most deeply nested states and
going outwards until only Start and Final are left.
Bjvrn Hvhrmann 7 mailto:firstname.lastname@example.org 7 http://bjoern.hoehrmann.de
Weinh. Str. 22 7 Telefon: +49(0)621/4309674 7 http://www.bjoernsworld.de
68309 Mannheim 7 PGP Pub. KeyID: 0xA4357E78 7 http://www.websitedev.de/
Return to the
Search the comp.compilers archives again.