9 Oct 91 09:38:00 +0100

Related articles |
---|

NFA to DFA, minimize DFA roberto@cernvax.cern.ch (1991-10-04) |

Re: NFA to DFA, minimize DFA bburshte@pyrps5.eng.pyramid.com (1991-10-07) |

Re: NFA to DFA, minimize DFA karsten@tfl.dk (1991-10-09) |

Newsgroups: | comp.compilers |

From: | karsten@tfl.dk (Karsten Nyblad, TFL) |

Keywords: | NFA, DFA |

Organization: | TFL, A Danish Telecommunication Research Laboratory |

References: | 91-10-015 |

Date: | 9 Oct 91 09:38:00 +0100 |

In article 91-10-015, roberto@cernvax.cern.ch (roberto bagnara) writes:

*> Has anybody got a good (e.g. *fast*) algorithm/implementation for the*

*> problem of converting an NFA (nondeterministic finite automaton) to a DFA*

*> (deterministic finite automaton)? And for the problem of minimizing the*

*> number of states of a DFA?*

A few tricks:

1) The algorithm in the dragon book is more general than needed

in most cases. The algorithm assumes that there may be

states from where there is no way to an accept state. That

is often not the case. If there is a path from all states

to an accept state, then you know that two states are only equal

if they accept the same set of letters. This can be used

for dividing the states into equivalence classes before

using the general algorithm, that will then be simpler and

have much less work.

2) The order in which the states are checked to find

out whether or not they should still be considered

equivalent is important. In scanner generators,

the algorithm using best order might be linear in

the number of states' time consumption, but the worst

might be in the square.

3) You can mark states with direct transitions to states

that are in equivalence classes that are split in two.

You will need to add pointers from states to their

predecessors in order to do that. When you search

for equivalence classes to split, you search for marked

states instead, and before splitting a class, you remove

the marks on states in that class.

Karsten Nyblad

TFL, A Danish Telecommunication Research Laboratory

E-mail: karsten@tfl.dk

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.