Variants of finite automata corresponding to infinite iterative morphism trees. Part II

Boris Melnikov

Abstract


Quite briefly, the subject of this paper can be formulated as follows: in the previously considered infinite iterative morphism trees, we combine equivalent vertices, in fact, obtaining a deterministic finite automaton; after that, we investigate some properties of the resulting automaton. In addition, the article describes the possible connection of the automata we are considering with problems arising in other areas of the theory of formal languages. In more detail, we work with various variants of finite automata, each of which corresponds to some infinite iterative tree of the morphism under consideration. In this case, the automata constructed for different morphisms describe the main properties of the given morphisms. In addition, in each case (i.e., for each variant of the automaton), the following “inverse problem” also arises: to describe a morphism (or simply specify a pair of languages) for which some given automaton is obtained. In addition, the paper describes the possible connection of the material under consideration with problems arising in other areas of the theory of formal languages. Among the variants of automata corresponding to an infinite iterative morphism tree for a given ordered pair of finite languages, we first define the so­called primary automaton. 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. Next, we consider some variants of nondeterministic automata corresponding to it. After that, we introduce a completely different object, i.e., a simplified primary automaton defined not on sets of words, but on words. Despite the significant difference with automata built on sets of words, all constructions for specific examples of languages can be performed using the same computer program. Next, we consider the features that appear when applying algorithms that form finite automata to pairs of matching languages. In conclusion, we briefly formulate the directions of further work related to the issues discussed in this paper. In this Part II, we consider primarily nondeterministic automata. The features that appear when applying algorithms that form finite automata to pairs of matching languages are also briefly considered. In addition, we consider an important property of the introduced automata, we define a special algebraic system, the properties of which is proposed to consider in more detail in following publications.

Full Text:

PDF (Russian)

References


Melnikov B., Vakhitova A. Some more on the finite automata //Journal of Applied Mathematics and Computing (The Korean Journal of Computational & Applied Mathematics). – 1998. – Vol. 5. No. 3. – P. 495–505.

Melnikov B., Melnikova A. Multidimensional minimization of nondeterministic finite automata. Part I. Auxiliary facts and algorithms // News of higher educational institutions. Volga region. Physical and mathematical sciences. – 2011. – No. 4 (20). – P. 59–69 (in Russian).

Melnikov B., Melnikova A. Multidimensional minimization of nondeterministic finite automata. Part II. Basis algorithms // News of higher educational institutions. Volga region. Physical and mathematical sciences. – 2012. – No. 1 (21). – P. 31–43 (in Russian).

Melnikov B., Tsyganov A. The state minimization problem for nondeterministic finite automata: the parallel implementation of the truncated branch and bound method // Proceedings – 5th International

Symposium on Parallel Architectures, Algorithms and Programming (PAAP­2012). – 2012. – P. 194–201.

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 // IOP Conference Series: Materials Science and Engineering. Krasnoyarsk Science and Technology City Hall of the Russian Union of Scientific and Engineering Associations. 2020. С. 52055.

Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. – 2017. – Vol. 5. No. 10. – P. 9–17.

Melnikov B., Melnikova A. An approach to the classification of the loops of finite automata. Part I: Long corresponding loops //International Journal of Open Information Technologies. – 2018. – Vol. 6. No. 9. – P. 9–14.

Melnikov B., Melnikova A. An approach to the classification of the loops of finite automata. Part II: The classification of the states based on the loops // International Journal of Open Information Technologies. – 2018. – Vol. 6. No. 11. – P. 1–6.

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. 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. 2021. – Vol. 9. No. 5. – P. 1–11 (in Russian).

Melnikov B. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundation of Computer Science. – 1993. – Vol. 4. No. 3. – P. 267–274.

Aho A., Hopcroft J., Ullman J. The Design and Analysis of Computer Algorithms. – Massachusetts, Addison­Wesley. – 1974. – 470 p.

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

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

Melnikov B. Some consequences of the equivalence condition of unambiguous bracketed grammars // Bulletin of the Moscow University, Series 15 (“Computational Mathematics and Cybernetics”). – 1991. – No. 10. – P. 51–53 (in Russian).

Melnikov B., Korabelshchikova S., Dolgov V. On the task of extracting the root from the language // International Journal of Open Information Technologies. – 2019. – Vol. 7. No. 3. – P. 1–6.

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).


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162