Математика и математическое моделирование. 2018; : 1-11
Об одном достаточном условии нерегулярности языков
https://doi.org/10.24108/mathm.0418.0000121Аннотация
Данная статья посвящена доказательству одного достаточного условия нерегулярности языков. Это условие связано со свойствами некоторых отношений на множестве натуральных чисел, а именно отношений, обладающих свойством, названное сильной отделимостью. В свою очередь, это свойство связано с возможностью разложения арифметического векторного пространства в прямую сумму подпространств. Мы задаем языки в некотором конечном алфавите через свойства вектора, показывающего числа вхождений каждой буквы алфавита в слова языка и называемого вектором распределения букв в слове. Основной результат статьи состоит в доказательстве теоремы, согласно которой язык, задаваемый таким образом, что вектор распределения букв в каждом слове языка принадлежит сильно отделимому отношению на множестве натуральных чисел, нерегулярен. Такой подход к доказательству нерегулярности основан на известной в теории формальных языков теореме Майхилла-Нероуда, согласно которой необходимое и достаточное условие регулярности языка состоит в конечности индекса некоторого отношения эквивалентности, определяемого языком.
В статье дается определение сильно отделимого отношения на множестве натуральных чисел и рассматриваются примеры таких отношений. Дается также описание конструкции, покрывающей весьма широкий класс сильно отделимых отношений и связанной с разложением векторного пространства четной размерности в прямую сумму подпространств одинаковой размерности. Доказывается лемма, утверждающая существование бесконечной последовательности векторов, любые два члена которой попарно дизъюнктны, т.е. один принадлежит некоторому сильно отделимому отношению, а другой нет. На основании этой леммы доказывается основная теорема о нерегулярности языка, определяемым сильно отделимым отношением.
Этот результат проливает дополнительный свет на эффективность инструментов анализа регулярности/нерегулярности языков, базирующихся на теореме Майхилла-Нероуда. Кроме того, доказанная теорема и анализ некоторых примеров сильно отделимых отношений позволяет установить нетривиальные связи между теорией формальных языков и теорией линейных пространств, что, как показывает анализ источников, является актуальной проблематикой.
В плане развития полученных результатов интерес представляет задача общей характеристики сильно отделимых отношений, а также анализ других свойств числовых множеств, важных с точки зрения анализа регулярности/нерегулярности языков.
Список литературы
1. Myhill J. Finite automata and the representation of events // WADD Technical Report. 1957. TR-57-624. Pp. 112–137.
2. Nerode A. Linear automation transformations // Proc. of the Amer. Math. Soc. 1958. Vol. 9. No. 4. Pp. 541–544. DOI: 10.2307/2033204
3. Khoussainov В., Nerode A. Automata theory and its applications. Boston: Birkhauser, 2001. 430 p.
4. Kozen D.C. Automata and computability. N.Y.: Springer, 1997. 400 p.
5. Comon H., Dauchet M., Gilleron R., Jacquemard F., Lugiez D., Loding C., Tison S., Tommasi M. Tree automata techniques and applications. TATA. 2014. 262 p. Режим доступа: http://tata.gforge.inria.fr/ (дата обращения 6.05.2016).
6. Borchardt B. The Myhill-Nerode theorem for recognizable tree series // Developments in language theory: DLT 2003: 7th Intern. conf. on developments in language theory (Szeged, Hungary, July 7-11, 2003): Proc. B.: Springer, 2003. Pp. 146–158. DOI: 10.1007/3-540-45007-6_11
7. Klarlund N. A homomorphism concept for ω-regularity. Aarhus: BRICS, Dep. of Computer Science Univ. of Aarhus, 1994. 19 p.
8. Doczkal C., Kaiser J.-O., Smolka G. A constructive theory of regular languages in Coq // Certified programs and proofs: CPP 2013: 3rd Intern. conf. on certified programs and proofs (Melbourne, Australia, December 11-13, 2013): Proc. Cham: Springer, 2013. Pp. 82-97. DOI: 10.1007/978-3-319-03545-1_6
9. Белоусов А.И. Теорема Майхилла-Нероуда в теории формальных языков и ее применение // Инженерный вестник. МГТУ им. Н.Э. Баумана: Электрон. журн. 2016. № 7. С. 1001–1009. Режим доступа: http://ainjournal.ru/doc/843177.html (дата обращения 15.07.16).
10. Белоусов А.И. О методике изложения некоторых разделов теории формальных языков: леммы о разрастании // Инженерный вестник. МГТУ им. Н.Э. Баумана: Электрон. журн. 2015. № 12. Режим доступа: http://engbul.bmstu.ru/doc/828263.html (дата обращения 23.12.15).
11. Guo-Qiang Zhang, Canfield E.R. The end of pumping? // Theoretical Computer Science. 1997. Vol. 174. No. 1-2. Pp. 275–279. DOI: 10.1016/S0304-3975(96)00247-2
12. Исмагилов Р.С., Мастихина А.А., Филиппова Л.Е. О числовых характеристиках формальных языков // Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 4. С. 4–15. DOI: 10.18698/1812-3368-2017-4-4-15
13. Ахтеров А.В., Белоусов А.И., Воронин А.Ю., Кирильченко А.А., Пряничников В.Е. Формирование действий распределенных мобильных систем в режиме информационного мониторинга // Информационно-измерительные и управляющие системы. 2009. Т. 7. № 6. С. 27–34.
14. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков: учеб. пособие. М.: БИНОМ. Лаборатория знаний, 2006. 247 с.
15. Мартыненко Б.К. Регулярные языки и КС-грамматики // Компьютерные инструменты в образовании. 2012. № 1. С. 14–20.
16. Долгов В.Н. Об одном отношении эквивалентности на множестве регулярных языков и его свойствах // Вектор науки Тольяттинского гос. ун-та. 2012. № 3. С. 19–22.
17. Вялый М.Н., Тарасов С.П. Орбиты линейных отображений и свойства регулярных языков // Дискретный анализ и исследование операций. 2010. Т. 17. № 6. С. 20–49.
Mathematics and Mathematical Modeling. 2018; : 1-11
On One Sufficient Condition for the Irregularity of Languages
https://doi.org/10.24108/mathm.0418.0000121Abstract
The article deals with a proof of one sufficient condition for the irregularity of languages. This condition is related to the properties of certain relations on the set of natural numbers, namely relations possessing the property, referred to as strong separability. In turn, this property is related to the possibility of decomposition of an arithmetic vector space into a direct sum of subspaces. We specify languages in some finite alphabet through the properties of a vector that shows the number of occurrences of each letter of the alphabet in the language words and is called the word distribution vector in the word. The main result of the paper is the proof of the theorem according to which a language given in such a way that the vector of distribution of letters in each word of the language belongs to a strongly separable relation on the set of natural numbers is not regular. Such an approach to the proof of irregularity is based on the Myhill-Nerode theorem known in the theory of formal languages, according to which the necessary and sufficient condition for the regularity of a language consists in the finiteness of the index of some equivalence relation defined by the language.
The article gives a definition of a strongly separable relation on the set of natural numbers and examines examples of such relations. Also describes a construction covering a considerably wide class of strongly separable relations and connected with decomposition of the even-dimensional vector space into a direct sum of subspaces of the same dimension. Gives the proof of the lemma to assert an availability of an infinite sequence of vectors, any two terms of which are pairwise disjoint, i.e. one belongs to some strongly separable relation, and the other does not. Based on this lemma, there is a proof of the main theorem on the irregularity of a language defined by a strongly separable relation.
This result sheds additional light on the effectiveness of regularity / irregularity analysis tools based on the Myhill-Neroud theorem. In addition, the proved theorem and analysis of some examples of strongly separable relations allows us to establish non-trivial connections between the theory of formal languages and the theory of linear spaces, which, as analysis of sources shows, is relevant.
In terms of development of the obtained results, the problem of the general characteristic of strongly separable relations is of interest, as well as the analysis of other properties of numerical sets that are important from the point of view of regularity / irregularity analysis of languages.
References
1. Myhill J. Finite automata and the representation of events // WADD Technical Report. 1957. TR-57-624. Pp. 112–137.
2. Nerode A. Linear automation transformations // Proc. of the Amer. Math. Soc. 1958. Vol. 9. No. 4. Pp. 541–544. DOI: 10.2307/2033204
3. Khoussainov V., Nerode A. Automata theory and its applications. Boston: Birkhauser, 2001. 430 p.
4. Kozen D.C. Automata and computability. N.Y.: Springer, 1997. 400 p.
5. Comon H., Dauchet M., Gilleron R., Jacquemard F., Lugiez D., Loding C., Tison S., Tommasi M. Tree automata techniques and applications. TATA. 2014. 262 p. Rezhim dostupa: http://tata.gforge.inria.fr/ (data obrashcheniya 6.05.2016).
6. Borchardt B. The Myhill-Nerode theorem for recognizable tree series // Developments in language theory: DLT 2003: 7th Intern. conf. on developments in language theory (Szeged, Hungary, July 7-11, 2003): Proc. B.: Springer, 2003. Pp. 146–158. DOI: 10.1007/3-540-45007-6_11
7. Klarlund N. A homomorphism concept for ω-regularity. Aarhus: BRICS, Dep. of Computer Science Univ. of Aarhus, 1994. 19 p.
8. Doczkal C., Kaiser J.-O., Smolka G. A constructive theory of regular languages in Coq // Certified programs and proofs: CPP 2013: 3rd Intern. conf. on certified programs and proofs (Melbourne, Australia, December 11-13, 2013): Proc. Cham: Springer, 2013. Pp. 82-97. DOI: 10.1007/978-3-319-03545-1_6
9. Belousov A.I. Teorema Maikhilla-Nerouda v teorii formal'nykh yazykov i ee primenenie // Inzhenernyi vestnik. MGTU im. N.E. Baumana: Elektron. zhurn. 2016. № 7. S. 1001–1009. Rezhim dostupa: http://ainjournal.ru/doc/843177.html (data obrashcheniya 15.07.16).
10. Belousov A.I. O metodike izlozheniya nekotorykh razdelov teorii formal'nykh yazykov: lemmy o razrastanii // Inzhenernyi vestnik. MGTU im. N.E. Baumana: Elektron. zhurn. 2015. № 12. Rezhim dostupa: http://engbul.bmstu.ru/doc/828263.html (data obrashcheniya 23.12.15).
11. Guo-Qiang Zhang, Canfield E.R. The end of pumping? // Theoretical Computer Science. 1997. Vol. 174. No. 1-2. Pp. 275–279. DOI: 10.1016/S0304-3975(96)00247-2
12. Ismagilov R.S., Mastikhina A.A., Filippova L.E. O chislovykh kharakteristikakh formal'nykh yazykov // Vestnik MGTU im. N.E. Baumana. Ser. Estestvennye nauki. 2017. № 4. S. 4–15. DOI: 10.18698/1812-3368-2017-4-4-15
13. Akhterov A.V., Belousov A.I., Voronin A.Yu., Kiril'chenko A.A., Pryanichnikov V.E. Formirovanie deistvii raspredelennykh mobil'nykh sistem v rezhime informatsionnogo monitoringa // Informatsionno-izmeritel'nye i upravlyayushchie sistemy. 2009. T. 7. № 6. S. 27–34.
14. Pentus A.E., Pentus M.R. Matematicheskaya teoriya formal'nykh yazykov: ucheb. posobie. M.: BINOM. Laboratoriya znanii, 2006. 247 s.
15. Martynenko B.K. Regulyarnye yazyki i KS-grammatiki // Komp'yuternye instrumenty v obrazovanii. 2012. № 1. S. 14–20.
16. Dolgov V.N. Ob odnom otnoshenii ekvivalentnosti na mnozhestve regulyarnykh yazykov i ego svoistvakh // Vektor nauki Tol'yattinskogo gos. un-ta. 2012. № 3. S. 19–22.
17. Vyalyi M.N., Tarasov S.P. Orbity lineinykh otobrazhenii i svoistva regulyarnykh yazykov // Diskretnyi analiz i issledovanie operatsii. 2010. T. 17. № 6. S. 20–49.
