Minimalization of NFA using the universal automaton

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

POLÁK Libor

Year of publication 2004
Type Article in Proceedings
Conference Descriptional Complexity of Formal Systems
MU Faculty or unit

Faculty of Science

Citation
Field Informatics
Keywords minimalization of NFA; universal automaton
Description As well-known, each minimal NFA for a regular language L is isomorphic to a subautomaton of the so-called universal automaton U for L . We explore and compare various conditions on sets of states of U which are related to the fact that induced subautomata of U accept the whole language L . The methods of several previous works on minimalizations of NFA can be transparently seen in our approach. We also propose a new algorithm which is easy to implement.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.