Variants of finite automata corresponding to infinite iterative morphism trees. Part I
Abstract
Quite briefly, the subject of this paper can be formulated as follows: in the previously considered infinite iterative morphism trees, we combine equivalent states, obtaining in fact a deterministic finite automaton; after that, we investigate some properties of this automaton. 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 socalled primary automaton. It is deterministic, defined on sets of words, and each of these sets is a subset of the set of suffixes of the second of the given languages. Next, we consider several 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. At the end of the paper, we briefly formulate the directions for further work related to the issues discussed in it. In this Part I, we consider deterministic automata only.
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. 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.
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).
Dubasova О., Melnikov B. On an extension of the contextfree language class // Programming (Russian Academy of Sciences). – 1995. – No. 6. – P. 46–58 (in Russian).
Staneviciené L. On a research facility without contextual languages // Cybernetics. – 1989. – No. 4. – P. 135–136 (in Russian).
Meytus V. The solvability of the equivalence problem of deterministic pushdown automata // Cybernetics and systems analysis. – 1992. – No. 5. – P. 20–45 (in Russian).
Sénizergues G. L(A) = L(B)? decidability results from complete formal systems // Theoretical Computer Science. – 2001. – Vol. 251. No. 1–2. – P. 1–166.
Garey M., Johnson D. Computers and Intractability. A Guide to the Theory of NPCompleteness. – San Francisco, Freeman and Company. – 1979. – 338 p.
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.
Salomaa A. Jewels of Formal Language Theory. – Rockville, Maryland, Computer Science Press. – 1981. – 144 p.
Melnikov B., Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages // Informatica (Lithuanian Academy of Sciences). – 2000. – Vol. 11. No. 4. – P. 441– 454.
Lallement G. Semigroups and Combinatorial Applications. – NJ, Wiley & Sons, Inc. – 1979. – 376 p.
Skornyakov L. (Ed.) General Algebra. Vol. 1. – Moscow, Nauka. – 1990. – 592 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).
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162