minimizing vertex NFAs

"Ralph Boland" <>
21 Apr 2006 23:48:28 -0400

          From comp.compilers

Related articles
minimizing vertex NFAs (Ralph Boland) (2006-04-21)
| List of all articles for this month |

From: "Ralph Boland" <>
Newsgroups: comp.compilers
Date: 21 Apr 2006 23:48:28 -0400
Keywords: lex, question
Posted-Date: 21 Apr 2006 23:48:28 EDT

I mean by a vertex nfa an "nfa" in which all transitions are epsilon
transitions but every "state" has a vocabulary symbol associated with
it which must be read before exiting the state. (See also note at

Now the problem of constructing an nfa Nmin equivalent to an nfa Norig
such that the number of states of Nmin is minimized is known to be
P-Space complete (i.e. hard or expensive or both).

I would like to know if the same is true for vertex nfas.
That is:

HOW EXPENSIVE is it to find a vertex nfa Vmin equivalent
to a vertex nfa Vorig such that the number of states of Vmin
is minimized?

An algorithm to solve this problem would also be nice!

IS THERE a proper name for vertex nfas?

A vertex nfa can be converted into a normal (edge) nfa by splitting
each state S into two states Sin and Sout such that every transition
into S now goes to Sin and every transition out of S now comes out of
Sout. If the vocabulary symbol for S is vS then there is a transition
from Sin to Sout on vocabulary symbol vS.

By the way, normal nfas can also be converted to vertex nfas! (hint:
It is straightforward to convert a regular expression into a vertex


Ralph Boland

Post a followup to this message

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