NFA 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
transitions


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?


TIA


Andras Erdei
ccg@freemail.hu

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