×

A new algorithm of the state-minimization for the nondeterministic finite automata. (English) Zbl 0942.68069

Summary: The problem of the state-minimization for the nondeterministic finite Rabin-Scott’s automata is considered. A new algorithm for this problem is obtained.
The obtained algorithm has the exponential effectiveness, like the earlier known algorithms for this problem. But each of previous algorithms amounts to the search of minimum generative system for local reaction of equal automaton of canonical form, and unlike them, we use in this paper two special functions, marking states of the given automaton.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite