Iterations of languages and finite automata

Boris Melnikov, Alexey Vylitok, Elena Melnikova

Abstract


In this paper we consider the representation of iterations of finite languages using special nondeterministic finite automata. For two iterated languages, a special equivalence relation is defined. We give the reduction of the conditions for the fulfillment of this relation to the definition of the equivalence of two nondeterministic finite automata, based on two given finite languages. Also we are considering a trivial proof of the regularity of the morphic preimage of regular language; this proof is related to the issues. In addition, using the equivalence relation under consideration hypotheses are formulated on the existence of a polynomial-time algorithm for the construction of an inverse morphism, possessing the specified special properties, as well as the relationship of the problems we are considering with the question of the possible equality of classes P=NP

Full Text:

PDF (Russian)

References


Alekseeva A. G. Mel'nikov B. F. Iteracii konechnyh i beskonechnyh jazykov i nedeterminirovannye konechnye avtomaty. Vektor nauki Tol'jattinskogo gosudarstvennogo universiteta. # 3. 2011. S. 30--33.

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

Lallement G. Semigroups and Combinatorial Applications. N.Y.: John Wiley & Sons, Inc., 1979, 376 p. (Lalleman Zh.: Polugruppy i kombinatornye prilozhenija. M.: Mir, 1985, 437 s.)

Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems. Fundamenta Informaticae. Vol. 104. No. 3. 2010. P. 267--283.

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

Brauer W. Automatentheorie. Eine Einf"uhrung in die Theorie endlicher Automaten. Stuttgart: B. G. Teubner, 1984, 493 S. (Braujer V.: Vvedenie v teoriju konechnyh avtomatov. M.: Radio i svjaz', 1987, 391 s.)

Mel'nikov B. F. Nekotorye sledstvija uslovija jekvivalentnosti dnoznachnyh skobochnyh grammatik. Vestnik Moskovskogo universiteta, ser. 15. # 3. 1991. S. 51--53.

Mel'nikov B. F. Opisanie special'nyh podmonoidov global'nogo admonoida svobodnogo monoida. Izvestija vysshih uchebnyh zavedenij. Matematika. #3. 2004. S. 46--56.

Dang V. V., Korabel'shhikova S. Ju., Mel'nikov B. F. O zadache nahozhdenija minimal'noj polugruppy approksimacii. Izvestija vysshih uchebnyh zavedenij. Povolzhskij region. Fiziko-matematicheskie nauki. #3 (35). 2015. S. 88--99.

Salomaa A. Jewels of Formal Language Theory. Rockville (Maryland): Computer Science Press, Inc. 1981, 144 p. (Salomaa A.: Zhemchuzhiny teorii formal'nyh jazykov. M.: Mir, 1986, 160 s.)

Computer Science Stack Exchange [Jelektronnyj resurs] = Obmen znanijami o teoreticheskoj informatike. – Rezhim dostupa: https://cs.stackexchange.com/questions/14785, svobodnyj. – Zagl. s jekrana, angl. jaz.

Glushkov V. M. Abstraktnaja teorija avtomatov. Uspehi matematicheskih nauk. T. 16. # 6 (101). 1961. S. 3--62.

Skornjakov L. A. (red). Obshhaja algebra. T. 2. M.: Nauka, 1991, 480 s.

Garey M., Johnson D. S. Computers and Intractability. USA: W. H. Freeman and Company. 1979, 338 p. (Gjeri M., Dzhonson D.: Vychislitel'nye mashiny i trudnoreshaemye zadachi. M.: Mir, 1982, 416 s.)


Refbacks

  • There are currently no refbacks.


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

ISSN: 2307-8162