The complete finite automaton
Boris Feliksovich Melnikov · International journal of open information technologies · 2017
There is well-known, that for the description of a regular language, there are different complete invariants: not only well-known canonical automata, but also basis automata and universal automata. While constructing basis and universal automata, there is necessary to construct canonical automata for both a given regular language and its mirror image. In the process of such a construction, we get, among other objects, a special binary relation $\#$, defined on the pairs of states of these two canonical automata. This relation is also an invariant (the incomplete one) for the given regular language. For each such binary relation, there is an entire subclass of the class of regular languages, that possesses it. Therefore, on the set of all regular languages, there is possible to define an (another) binary relation; it holds for some two languages, if and only if they have the same binary the relation $\#$. It is obvious, that the binary relation defined in this way is the equivalence relation on the set of all regular languages. The question arises of the most language which is the element of such class equivalence with respect to the last relation. In this paper, we describe languages that can be considered as typical elements, construct canonical finite automata for such languages, consider some of their properties. The main of these properties is the following: from such an automaton, using special transformations, we can obtain any canonical automaton whose language corresponds to the given binary relation $\#$.