On Certain Classes of Irregular Languages

Авторы: Belousov A.I., Ismagilov R.S., Filippova L.E. Опубликовано: 08.06.2020
Опубликовано в выпуске: #3(90)/2020  
DOI: 10.18698/1812-3368-2020-3-30-43

Раздел: Математика | Рубрика: Вычислительная математика  
Ключевые слова: formal language, alphabet, regular language, distribution vector, irregularity condition, equivalence relation, equivalence relation index, sparse sets

Objective of this paper is to prove certain regularity and irregularity conditions in languages determined by a set of integer vectors called distribution vectors of the number of letters in words over a finite alphabet. Each language over the finite alphabet uniquely determines its proprietary set of distribution vectors and vice versa, i.e., each set of vectors is associated with a language having this set of distribution vectors. A single necessary condition for the language regularity was considered associated with the concept of Z+-plane (sets of points with non-negative integer coordinates lying on a plane in the affine space). The condition is that a set of distribution vectors determined by any regular language could be represented as a finite union of the Z+-planes. Certain sufficient irregularity conditions associated with the distribution vector properties were proven. Based on this, classes of irregular languages could be identified. These classes are determined by a set of vectors (points) that could not be represented as a finite union of the Z+-planes; by a set of vectors containing vectors with arbitrarily high values of each coordinate and having certain restrictions on the difference between maximum and minimum values of the coordinates; by a set of vectors called the sparse sets. A method is proposed for building such sets using strictly convex and strictly increasing numerical sequences. These sufficient irregularity conditions are based on the Myhill --- Nerode theorem, which is known in the formal languages' theory. Examples of applying the proved theorems to the analysis of languages' regularity/irregularity are presented


[1] Akhtyorov A.V., Belousov A.I., Voronin A.Yu., et al. Distributed mobile systems for information monitoring. Information-Measuring and Control Systems, 2009, no. 6, pp. 27--34 (in Russ.).

[2] Vyalyi M., Tarasov S. Orbits of linear maps and regular languages properties. J. Appl. Ind. Math., 2011, vol. 5, no. 3, art. no. 448. DOI: https://doi.org/10.1134/S1990478911030173

[3] Denisova D.S. Regular expressions. Nauchnaya gipoteza, 2018, no. 5, pp. 37--43 (in Russ.).

[4] Mel’nikov B.F., Vylitok A.A., Mel’nikova E.A. Iterations of languages and finite automata. International Journal of Open Information Technologies, 2017, no. 12, pp. 1--17 (in Russ.).

[5] Wang Y., Roohi N., Dullerud G.E., et al. Stability analysis of switched linear systems defined by regular languages. IEEE Trans. Autom. Control, 2017, vol. 62, iss. 5, pp. 2568--2575. DOI: https://doi.org/10.1109/TAC.2016.2599930

[6] Ismagilov R.S., Mastikhina A.A., Filippova L.E. On numerical characteristics of formal languages. Herald of the Bauman Moscow State Technical University, Series Natural Sciences, 2017, no. 4, pp. 4--15 (in Russ.). DOI: http://doi.org/10.18698/1812-3368-2017-4-4-15

[7] Allender E., Arvind V., Mahajan M. Arithmetic complexity, Kleene closure, and formal power series. Theory Comput. Systems, 2003, vol. 36, no. 4, pp. 303--328. DOI: https://doi.org/10.1007/s00224-003-1077-7

[8] Belousov A.I., Ismagilov R.S. On one sufficient condition for the irregularity of languages. Matematika i matematicheskoe modelirovanie [Mathematics and Mathematical Modeling], 2018, no. 4, pp. 1--11 (in Russ.). DOI: https://doi.org/10.24108/mathm.0418.0000121

[9] Myhill J. Finite automata and the representation of events. Technical report WADD TR 57-624. Dayton, OH, Wright Patterson Air Force Base, 1957.

[10] Nerode A. Linear automation transformations. Proc. Amer. Math. Soc., 1958, vol. 9, no. 4, pp. 541--544.

[11] Khoussainov B., Nerode A. Automata theory and its applications. In: Progress in Computer Science and Applied Logic. Birkhauser, Boston, Springer, 2001. DOI: https://doi.org/10.1007/978-1-4612-0171-7

[12] Comon H., Dauchet M., Gilleron R., et al. Tree automata techniques and applications. TATA. 2014. Available at: http://tata.gforge.inria.fr (accessed: 05.04.2019).

[13] Borchardt B. The Myhill --- Nerode theorem for recognizable tree series. In: Esik Z., Fulop Z., eds. Developments in Language Theory. DLT 2003. Lecture Notes in Computer Science, vol. 2710. Berlin, Heidelberg, Springer, 2003. DOI: https://doi.org/10.1007/3-540-45007-6_11

[14] Grinchenkov D.V., Kushchiy D.N., Spiridonova I.A. [On the implementation of the finite state machine for recognizing formal language descripting partially structured texts]. Fundamental’nye issledovaniya, metody i algoritmy prikladnoy matematiki v tekhnike, meditsine i ekonomike. Mater. 16-y Mezhdunar. molodezh. nauch.-prakt. konf. [Fundamental Study, Methods and Algorithms of Applied Mathematics in Technique, Medicine and Economy. Proc. 16th Int. Youth Sci.-Pract. Conf.]. Novocherkassk, Lik Publ., 2017, pp. 49--53 (in Russ.).

[15] Belousov A.I. On presentation technique for certain sections of formal languages theory: pumping lemmas. Inzhenernyy vestnik [Engineering Bulletin], 2015, no. 12 (in Russ.). Available at: http://engbul.bmstu.ru/doc/828263.html (accessed: 06.04.2019).

[16] Zhang G.-Q., Canfield E.R. The end of pumping. Theoretical Comput. Sci., 1997, vol. 174, iss. 1-2, pp. 275--279. DOI: https://doi.org/10.1016/S0304-3975(96)00247-2

[17] Aho A.V., Ullman J.D. The theory of parsing, translation, and compiling. Vol. 1. Parsing, Prentice Hall, 1972.

[18] Salomaa A. Formal languages and power series. In: Handbook of Тheoretical Сomputer Science. Vol. B. MIT Press, 1990, pp. 103--132.