Waterloo-like finite automata and algorithms for their automatic construction

Abstract

In the problems of minimization of nondeterministic finite automata, there may be situations, when a covering set of blocks defines an automaton, which is not equivalent to the original one. For the first time, such an example was obtained in 1970 by Kameda and Weiner, and according to their paper, was given the name Waterloo. The existence of such constructions ("walibad" in our terminology, from "Waterloo-like badness") greatly complicates the description of practical algorithms
for the state minimization of nondeterministic finite automata. Hence the problems of the search and description of such constructions arouse, and, where possible, it should be done before applying the said algorithms of minimization.
In this paper, we propose an example of algorithm 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. We emphasize, that in the process of building we used only relation #, and did not use automaton known in advance.