NFA question

Andras Erdei <>
20 Jun 2000 02:53:24 -0400

          From comp.compilers

Related articles
NFA question (Andras Erdei) (2000-06-20)
| List of all articles for this month |

From: Andras Erdei <>
Newsgroups: comp.theory,comp.compilers
Date: 20 Jun 2000 02:53:24 -0400
Organization: Sonera corp Internet services
Keywords: lex, question

I'm trying to convert a regular expression to an NFA. The
resulting NFA must have two properties:

(i) for each node there must be at most one node from which
it can be reached with a non-epsilon transition

(ii) there should be no path with two consecutive epsilon

The number of transitions is not a concern, but the NFA should have as
few nodes as possible (it does not have to be minimal, although it
would be nice :O). Also, i would like to create the NFA on-the-fly --
no postprocessing for optimization.

So far i've found two solutions, none of them satisfactory:

1) Create any kind of NFA, convert it to DFA, then replace every edge
in the DFA with two edges by inserting an additional node, where the
first edge has the same label as the original one, and the second is
labelled with epsilon. (This actually proves that there's always an
NFA with the required properties.) Unfortunately the intermediate DFA
may have exponential size (and it also seems to be an overkill).

2) Almost the same as above, but a more direct approach: we match
every symbol with a two-node NFA like above (this ensures (i)), and
take care not to violate (ii) when transforming a * or |. This seems
to be a bit arbitrary, i'm never sure whether i get the * and | (and ?
and +) transformations right (i've actually failed to do it right
several times the last two weeks), and the result is still two times
bigger than it should be.

Any suggestions?


Andras Erdei

Post a followup to this message

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