Re: Perfecting State Elimination

* 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
          as necessary.


    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.


regards,
--
Bjvrn Hvhrmann 7 mailto:bjoern@hoehrmann.de 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 comp.compilers page.
Search the comp.compilers archives again.