|minimizing vertex NFAs email@example.com (Ralph Boland) (2006-04-21)|
|From:||"Ralph Boland" <firstname.lastname@example.org>|
|Date:||21 Apr 2006 23:48:28 -0400|
|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.
HOW EXPENSIVE is it to find a vertex nfa Vmin equivalent
to a vertex nfa Vorig such that the number of states of Vmin
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
Return to the
Search the comp.compilers archives again.