Some new heuristical algorithms for minimization of nondeterministic finite automata

Abstract

In this paper, we propose an algorithm example for the transformation of so-called complete automaton given by a table of binary relation #. At the same time, we know that for this table for the binary relation #, there exists some corresponding nondeterministic automaton having Waterloo-like badness. The proposed transformation, which is not equivalent, is the serial removal of a state and combining a pair of states. It gives the opportunity to build on the basis of the given relation # some automaton which also has the walibad-property. And, generally speaking, the obtained automaton is different from the known in advance.