On Certain Classes of Irregular Languages

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

References

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