Preview

Математика и математическое моделирование

Расширенный поиск

Об одном достаточном условии нерегулярности языков

https://doi.org/10.24108/mathm.0418.0000121

Полный текст:

Аннотация

Данная статья посвящена доказательству одного достаточного условия нерегулярности языков. Это условие связано со свойствами некоторых отношений на множестве натуральных чисел, а именно отношений, обладающих свойством, названное сильной отделимостью. В свою очередь, это свойство связано с возможностью разложения арифметического векторного пространства в прямую сумму подпространств. Мы задаем языки в некотором конечном алфавите через свойства вектора, показывающего числа вхождений каждой буквы алфавита в слова языка и называемого вектором распределения букв в слове. Основной результат статьи состоит в доказательстве теоремы, согласно которой язык, задаваемый таким образом, что вектор распределения букв в каждом слове языка принадлежит сильно отделимому отношению на множестве натуральных чисел, нерегулярен. Такой подход к доказательству нерегулярности основан на известной в теории формальных языков теореме Майхилла-Нероуда, согласно которой необходимое и достаточное условие регулярности языка состоит в конечности индекса некоторого отношения эквивалентности, определяемого языком.

В статье дается определение сильно отделимого отношения на множестве натуральных чисел и рассматриваются примеры таких отношений. Дается также описание конструкции, покрывающей весьма широкий класс сильно отделимых отношений и связанной с разложением векторного пространства четной размерности в прямую сумму подпространств одинаковой размерности. Доказывается лемма, утверждающая существование бесконечной последовательности векторов, любые два члена которой попарно дизъюнктны, т.е. один принадлежит некоторому сильно отделимому отношению, а другой нет. На основании этой леммы доказывается основная теорема о нерегулярности языка, определяемым сильно отделимым отношением.

Этот результат проливает дополнительный свет на эффективность инструментов анализа регулярности/нерегулярности языков, базирующихся на теореме Майхилла-Нероуда. Кроме того, доказанная теорема и анализ некоторых примеров сильно отделимых отношений позволяет установить нетривиальные связи между теорией формальных языков и теорией линейных пространств, что, как показывает анализ источников, является актуальной проблематикой.

В плане развития полученных результатов интерес представляет задача общей характеристики сильно отделимых отношений, а также анализ других свойств числовых множеств, важных с точки зрения анализа регулярности/нерегулярности языков.

Об авторах

А. И. Белоусов
МГТУ им. Н.Э. Баумана, Москва
Россия

Белоусов Алексей Иванович

Каф. ФН-12, доцент, 1419-0968



Р. С. Исмагилов
МГТУ им. Н.Э. Баумана, Москва
Россия

Исмагилов Раис Сальманович

каф. ФН-1, профессор



Список литературы

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.


Для цитирования:


Белоусов А.И., Исмагилов Р.С. Об одном достаточном условии нерегулярности языков. Математика и математическое моделирование. 2018;(4):1-11. https://doi.org/10.24108/mathm.0418.0000121

For citation:


Belousov A.I., Ismagilov R.S. On One Sufficient Condition for the Irregularity of Languages. Mathematics and Mathematical Modeling. 2018;(4):1-11. (In Russ.) https://doi.org/10.24108/mathm.0418.0000121

Просмотров: 63


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)