On Numerical Characteristics of Formal Languages
| Authors: Ismagilov R.S., Mastikhina A.A., Filippova L.E. | Published: 24.05.2017 |
| Published in issue: #4(73)/2017 | |
| DOI: 10.18698/1812-3368-2017-4-4-15 | |
| Category: Mathematics and Mechanics | Chapter: Mathematical Logics, Algebra, and Theory of Numbers | |
| Keywords: formal language, regular language, graph, generating function, order, composition of words | |
The purpose of this study was to count the number of layers of a regular language of a given composition. First, we specified the alphabet from the characters and defined the composition of the word as a vector. Then, we introduced the functions of the number of words of a given composition. Finally, we defined simple estimates of these functions for languages derived from languages using ordinary operations (union, concatenation, iteration). We also studied series for languages generated automatically.
References
[1] Goncharov V.L. From combinatorial theory. Izvestiya AN SSSR. Ser. Matem., 1944, vol. 8, iss. 1, pp. 3-48 (in Russ.).
[2] Korshunov A.D. On the asymptotics of the number of binary words with a given length of a maximal series. I. Diskretnyy analiz i issledovanie operatsiy, 1997, vol. 4, no. 4, pp. 13-46 (in Russ.).
[3] Kostochka A.V., Mazurov V.D., Savelyev L.Ya. The number of q-ary words with restrictions on the length of a maximal series. Discrete Mathematics and Applications, 1998, vol. 8, no. 2, pp. 109-118. DOI: https://doi.org/10.1515/dma.1998.8.2.109
[4] Chomsky N., Miller G.A. Finite state languages. In: Information and control. 1958, vol. 1, no. 2, pp. 91-112.
[5] Strogalov A.S. Regular languages with polynomial growth in the number of words. Discrete Mathematics and Applications, 1992, vol. 2, no. 3, pp. 285-292.
[6] Belousov A.I., Tkachev S.B. Diskretnaya matematika [Descrete mathematics]. Moscow, Bauman MSTU Publ., 2004. 744 p.
[7] Trakhtenbrot B.A., Bardzin Ya.M. Konechnye avtomaty (povedenie i sintez) [Finite-state machines: Behaviour and synthesis]. Moscow, Nauka Publ., 1970. 400 p.
[8] Hopcroft J.E., Rajeev Motwani, Ullman J.D. Introduction to automata theory, languages, and computation. Addison Wesley, 2001. 537 p.
[9] Arkhipov G.I., Sadovnichiy V.A., Chubarikov V.N. Lektsii po matematicheskomu analizu [Lectures on mathematical analysis]. Moscow, Drofa Publ., 2003. 640 p.
[10] Copson E.T. Asymptotic expansions. Cambridge Univ. Press, 2004. 120 p.
[11] Adel’son-Vel’skiy G.M., Kuznetsov O.P. Diskretnaya matematika dlya inzhenera [Descrete mathematics for an engineer]. Moscow, Energoatomizdat Publ., 1988. 480 p.
[12] Fedoryuk M.V. Asimptotika, integraly i ryady [Asymptotics, integrals and raws]. Moscow, Nauka Publ., 1987. 544 p.
