A polynomial algorithm for constructing a finite automaton for determining the equality of infinite iterations of two finite languages

Boris Melnikov, Aleksandra Melnikova

Abstract


In this paper, we continue the topic related to the special binary relation on the set of formal languages (considered primarily on the set of iterations of non­empty finite languages); this is so called equivalence relation at infinity. We have formulated a simpler binary relation in a variety of languages (i.e. the covering relation), the double use of which is equivalent to the use of the equivalence relation at infinity. After that, we considered the algorithm for verifying the implementation of the coverage relation, and identified the auxiliary objects used to prove the correctness of this algorithm. One such object is an infinite iterative tree. In the infinite iterative trees considered, we combine the equivalent states, obtaining in fact a deterministic finite automaton. We have defined a specific such automaton for two given finite languages; this is so called primary automaton, PRI. It is deterministic, defined on sets of words, and each of these sets is a subset of the set of prefixes of the second of the given languages. After that, we define some variants of special nondeterministic automata corresponding to it, describing in fact the construction of this iterative morphism tree. We introduce a completely different object (i.e., a simplified primary automaton, NSPRI), which also describes the construction of an iterative morphism tree, but is defined not on sets of words, but on words. The main idea of the proof of the fact, that the algorithm for constructing a finite automaton for checking the equality of infinite iterations of two finite languages is polynomial is as follows. It is natural to construct a deterministic automaton for this problem, and each state of such deterministic automaton describes the whole set of possible prefixes remaining from various decompositions of the word (this is decompositions of the morphism of the iteration of the first given finite language according to the words of the second given finite language). However, in doing so, we are working with many sets of possible prefixes, which makes it impossible for the algorithm to be polynomial. Therefore, we construct a nondeterministic automaton defined simply on the set of possible prefixes; at the same time, there is some question related to when exactly this automaton gives a positive result. We solve this problem by requiring that the resulting nondeterministic automaton be an analog of the total deterministic automaton.

Full Text:

PDF (Russian)

References


Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 4. – P. 1–11 (in Russian).

Melnikov B., Melnikova A. Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part II // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 5. – P. 1–11 (in Russian).

Melnikov B Variants of finite automata corresponding to infinite iterative morphism trees. Part I // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. 7. – P. 5–13 (in Russian).

Melnikov B Variants of finite automata corresponding to infinite iterative morphism trees. Part II // International Journal of Open Information Technologies. – 2021. – Vol. 9. No. ??. – P. ??–?? (in Russian).

Kameda T., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Transactions on Computers. – 1970. – Vol. C19. No. 7. – P. 617–627.

Polák L. Minimizations of NFA using the universal automaton // International Journal of Foundation of Computer Sciences. – 2005. – Vol. 16. No. 5. – P. 999–1010.

Melnikov B., Sayfullina M. On some algorithms for equivalent transformation of nondeterministic finite automata // News of higher

educational institutions. Mathematics. – 2009. – No. 4. – P. 67–72 (in Russian).

Melnikov B., Tsyganov A. The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method // In: Proceedings – 5th International Symposium on Parallel Architectures, Algorithms and Programming, PAAP–2012. – 2012. – P. 194–201.

Dolgov V., Melnikov B. Building a universal finite automaton. I. From the theory to the practical algorithms // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2013. – No. 2. – P. 173–181 (in Russian).

Dolgov V., Melnikov B. Building a universal finite automaton. II. Examples of how algorithms work // Bulletin of the Voronezh State University. Series: Physics. Mathematics. – 2014. – No. 1. – P. 78–85 (in Russian).

Abramyan M., Melnikov B. An approach to algorithmizing the problem of vertex minimization of nondeterministic automata. Part I. Problem statement and the brief description of the basis methods // In: IOP Conference Series: Materials Science and Engineering. Krasnoyarsk Science and Technology City Hall of the Russian Union of Scientific and Engineering Associations. – 2020. – C. 52055.

Markov A. Theory of algorithms (Proceedings of the V. Steklov Mathematical Institute. Vol. 42). – Moscow, Leningrad: USSR Academy of Sciences Ed. – 1954. – 376 p. (in Russian).

Igoshin V. Mathematical logic and theory of algorithms. – Moscow: Akademia. – 2004. – 447 p. (in Russian).

Skornyakov L. (Ed.) General Algebra. Vol. 2. – Moscow, Nauka. – 1991. – 480 p. (in Russian).

Alekseeva A., Melnikov B. Iterations of finite and infinite languages and nondeterministic finite automata // Vector of Science of Togliatti State University. – 2011. – No. 3 (17). – P. 30–33 (in Russian).

Pin J.­E. Mathematical Foundations of Automata Theory. – Berlin, Springer­Verlag. – 2012. – 310 p


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162