21 Apr 2006 23:48:28 -0400

Related articles |
---|

minimizing vertex NFAs rpboland@gmail.com (Ralph Boland) (2006-04-21) |

From: | "Ralph Boland" <rpboland@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 21 Apr 2006 23:48:28 -0400 |

Organization: | http://groups.google.com |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.