minimizing vertex NFAs

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
bottom.)


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?


NOTE:
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
nfa.)


Thanks


Ralph Boland

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