Re: Perfecting State Elimination

Bjoern Hoehrmann <>
Mon, 01 Oct 2007 18:23:25 +0200

          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: Bjoern Hoehrmann <>
Newsgroups: comp.compilers,comp.theory
Followup-To: comp.compilers
Date: Mon, 01 Oct 2007 18:23:25 +0200
Organization: Arcor
References: 07-10-006
Keywords: optimize, lex

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

Bjvrn Hvhrmann 7 7
Weinh. Str. 22 7 Telefon: +49(0)621/4309674 7
68309 Mannheim 7 PGP Pub. KeyID: 0xA4357E78 7

Post a followup to this message

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