The complete finite automaton

Boris Melnikov


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 typical" 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 $\#$.

Full Text:



Melnikov B., Melnikova A., Edge-minimization of non-deterministic finite automata. Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 2001, vol. 8, no. 3, pp. 469–479.

Melnikov B., Once more on the edge-minimization of nondeterministic finite automata and the connected problems. Fundamenta Informaticae., vol. 104, no. 3. pp. 267–283.

Melnikov B., Melnikova A., Some more on the basis finite automaton. Acta Univ. Sapientiae, Informatica. 2013, vol. 5, no. 2, pp. 227–244.

Lombardy S., Sakarovitch J., The Universal Automaton. in: Logic and Automata, Texts in Logic and Games Amsterdam Univ. Press. 2008, vol. 2, pp. 457–504.

Melnikov B., DolgovV., Some more algorithms for Conway’s universal automaton. Acta Univ. Sapientiae, Informatica. 2014, vol. 6, no. 1, pp. 5–20.

Melnikov B., Vakhitova A., Some more on the finite automata. Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 1998, vol. 5, no. 3, pp. 495–505.

Melnikov B., Sciarini-Guryanova N., Possible edges of a finite automaton defining a given regular language. Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). 2002, vol. 9, no. 2., pp. 475–485.

Pol´ak L., Minimalizations of NFA using the universal automaton. International Journal of Foundation of Compututer Sciences. 2005, vol. 16, no. 5, pp. 999–1010.

Melnikov B., Once more on the combining states of nondeterministic finite automaton. Proceedings of XI International Scientific Conference on the Problems of Theoretical Cybernetics. M., Russian State University for the Humanities Ed. 1996. P. 139–141. (in Russian)

Kameda T., Weiner P., On the state minimization of nondeterministic finite automata. IEEE Trans. on Comp. 1970, vol. C-19, no. 7, pp. 617–

Krivolapova A., Melnikova E., Sofonova N., Some auxiliary algorithms for construction of Waterloo-like automata. Vestnik of Voronezh State University. Series: System analysis and information technologies. 2016, no. 4, pp. 20–28. (in Russian)

Melnikov B., Sayfullina M., On some algorithms of equivalent transformations of nondeterministic finite automata. Izvestiya of universities. Mathematics. 2009, no. 4, pp. 67–72. (in Russian) (English translation: Mel’nikov B., Saifullina M., Some algorithms for equivalent transformations of nondeterministic finite automata. Russian Mathematics (Izv. VUZ). 2009, no. 4, pp. 54–56.)

Hromkoviˇc J., Theoretical Computer Science. An Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Springer, 2003. 321 p.

Melnikov B., Tsyganov A., The state minimizaton problem for nondeterministic finite automata: The parallel implementation of the truncated branch and bound method. Proceedings of the International Symposium on Parallel Architectures, Algorithms and Programming, PAAP-2012. Taipei, Taiwan. 2012, pp. 194–201.

Melnikov B., Radionov A., Moseev A., Melnikova E., Some specific heuristics for situation clustering problems. Proceedings of the 1st International Conference on Software and Data Technologies, ICSOFT-Setubal, Portugal. 2006, pp. 272–279.


  • There are currently no refbacks.

IT-EDU-2017   Servletsuite

ISSN: 2307-8162