# NFA question

## Andras Erdei <ccg@freemail.hu>

20 Jun 2000 02:53:24 -0400

*From comp.compilers*

Related articles |

**NFA question ***ccg@freemail.hu (Andras Erdei)* (2000-06-20) |

| List of all articles for this month |

**From: ** | Andras Erdei <ccg@freemail.hu> |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.