On the groupoid of the primary automaton PRI defined for the only finite language

Lingqian Meng, Boris Melnikov

Abstract


In this paper, we continue the theme of our previous papers devoted to the important equivalence relation in a set of formal languages, i.e., the equivalence relation in infinity; for its detailed study we also considered the binary coverage relation. In the study of these relations, we used infinite iterative morphism trees, for each of which, after combining its equivalent vertices, a deterministic finite automaton is obtained. Among some similar variants of automata corresponding to an infinite iterative morphism tree, of greatest interest is the socalled primary automaton (PRI automaton), which is defined in a special way for a given pair of finite languages. It is defined on subsets of the set of prefixes of one of these languages, and we consider these subsets as states of the  defined automaton. In this paper, we continue to consider the primary automaton constructed for any pair of finite languages, but we also define new objects: an automaton constructed for only one finite language, as well as the groupoid and semigroup of transformations corresponding to this automaton.
Let us describe the main subject of this paper. If we “combine line by line” the structures arising in the PRI automaton, then we get the result of the transition of each state – in the case when the input is some language. As a result, we can study a primary automaton built on the basis of only one language, and this language can be called the basic one. For both the set of states and the input alphabet, we shall use a subset of the set of proper prefixes of the base language, or its prototype obtained using some inverse morphism.
The paper considers the resulting groupoid and proves the theorem that in this case, it is possible to define a semigroup of transformations. The main idea of proving this fact is as follows. If the semigroup requirement is considered from the point of view of a finite automaton, then on the two parts of the equation used in it, we can say the following. The left part of the equation of this semigroup requirement describes the transition from the current state in accordance with the first subword (the prefix) of the input to some intermediate state; then the continuation of work in accordance with the second subword (the suffix) of the input. We can say the same for the right side of the equation, and the input string in both cases can be considered the same. This paper also discusses some algebraic properties of the described semigroup, including simple examples. We propose to consider more complex examples in the continuation paper. 


Full Text:

PDF (Russian)

References


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. 10. – P. 1–8 (in Russian).

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

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

Melnikov B. 2ω-finite automata and sets of obstructions of their language // The Korean Journal of Computational and Applied Mathematics (Journal of Applied Mathematics and Computing). – 2000. – Vol. 6. No. 3. – P. 565–574.

Lyapin E. Semigrioups. – Moscow, Fizmatlit. – 1960. – 592 p. (in Russian).

Birkhoff G., Bartee T. Modern Applied Algebra. – NY, McGraw-Hill. – 1970. – 431 p.

Lallement G. Semigroups and Combinatorial Applications. – NY, John Wiley & Sons. – 1979. – 376 p.

Salomaa A. Jewels of Formal Language Theory. – Rockville, Maryland, Computer Science Press. – 1981. – 144 p.

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

Melnikov B., Melnikova A. The use of petal finite automata to verify the fulfillment of a special case of the Zyu hypothesis (for a given finite language) // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 3. – P. 1–11 (in Russian).

Melnikov B., Dolgov V. Simplified regular languages and a special equivalence relation on a class of regular languages. Part I // International Journal of Open Information Technologies. – 2022. – Vol. 10. No. 9. – P. 12–20 (in Russian).

Melnikov B. A polynomial algorithm for constructing the optimal inverse morphism // International Journal of Open Information Technologies. – 2023. – Vol. 11. No. 6. – P. 1–10 (in Russian).


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162