On some approaches to automatic generation of Waterloo-like automata

In this paper, we consider algorithms for generating nondeterministic finite automata possessing the following property (the so-called walibad property): among their covering automata, there exist automata that are not equivalent to the original automaton. The Waterloo automaton has this property; it plays an important role in vertex minimization algorithms. Two algorithms are described: one is based on recursive analysis of covering automata for automata with the walibad property, the other uses a set of non-equivalent transformations of a complete automaton based on an automaton with the walibad property. Examples of application of both algorithms to the Waterloo automaton are given.