On the State Minimization of Nondeterministic Finite Automata
- 1 July 1970
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-19 (7), 617-627
- https://doi.org/10.1109/t-c.1970.222994
Abstract
The aim of this paper is to obtain a procedure for finding a minimum state nondeterministic finite automaton (NDA) equivalent to a given (in general, nondeterministic) finite automaton. Given a finite automaton A, we derive from A a matrix of 1' s and 0's, called a reduced automaton matrix RAM) of A, in a certain way and show that each state of A corresponds to a grid over the RAM. A grid consists of a set of rows and a set of columns of an RAM such that only 1's appear at the intersections. It is also shown that the union of all the grids, each of which corresponds to a state of A, covers all the 1 entries of an RAM.Keywords
This publication has 5 references indexed in Scilit:
- Zur Theorie der nichtdeterministischen und unvollständigen AutomatenComputing, 1969
- Derivatives of Regular ExpressionsJournal of the ACM, 1964
- Transition graphs and the star-height of regular events.The Michigan Mathematical Journal, 1963
- Design of Sequential Machines from Their Regular ExpressionsJournal of the ACM, 1961
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959