Методическая периодика: проблемы и решения

Организационно-методическая работа
Традиции и новации в методике преподавания
Педагогические технологии и методы
УМКД: теория и практика
Педагогические экспромты

Организация производства (промышленность)

Ключевые слова
Аннотации
Архив рубрик

регистрация
забыли пароль?

Другие журналы

электронный научно-технический журнал

ИНЖЕНЕРНЫЙ ВЕСТНИК

Издатель: Общероссийская общественная организация "Академия инженерных наук им. А.М. Прохорова".

Теорема Майхилла-Нероуда в теории формальных языков и ее применение

Инженерный вестник # 07, июль 2016
УДК: 519.76+372.851

Файл статьи:

Belousov...1009.pdf (552.79Кб)

автор: Белоусов А. И.

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

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

      [1].      Белоусов А.И., Ткачев С.Б. Мультиграфовое представление автоматов с магазинной памятью // Наука и образование. МГТУ им. Н.Э. Баумана. Электронный журн., 2012. № 9. С.141-152. DOI: 10.7463/0912.0460973
      [2].      Белоусов А.И., Ткачев С.Б. Построение контекстно-свободной грамматики по мультиграфу автомата с магазинной памятью // Наука и образование. МГТУ им. Н.Э. Баумана. Электронный журн., 2014. № 7. С.128-142. DOI: 10.7463/0714.0717777
      [3].      Белоусов А.И. О методике изложения некоторых разделов теории формальных языков: леммы о разрастании // Инженерный вестник. МГТУ им. Н.Э. Баумана. Электрон. журн. 2015. № 12. С. 1020-1031. Режим доступа: http://engbul.bmstu.ru/doc/828263.html (дата обращения: 23.12.15).
      [4].      Nerode A. Linear Automaton Transformations // Proceedings of the American Mathematical Society. 1958. № 9. pp. 541—544. DOI: http://dx.doi.org/10.1090/S0002-9939-1958-0135681-9
      [5].      Trevisan L. Notes on the Myhill-Nerode Theorem // Stanford University – CS103: Math for Computer Science, Handout LN15, 5/12/2014 Режим доступа: http://www.eecs.berkeley.edu/~luca/cs103-14/lecture15.pdf (дата обращения: 6.05.2016)
      [6].      Regan K. Notes on the Myhill-Nerode Theorem // CSE396, 2010, retrieved 2016-03-22. Режим доступа: http://www.cse.buffalo.edu/~regan/cse396/CSE396MNT.pdf (дата обращения: 6.05.2016)
      [7].      Comon H., Dauchet M., Gilleron R., Löding C., Jacquemard F., Lugiez D., Tison S., Tommasi M. Tree Automata Techniques and Applications. – TATA Ed. 2008. 262 p. Режим доступа: http://tata.gforge.inria.fr/ (дата обращения: 6.05.2016)
      [8].      Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. М.: Интернет-университет информационных технологий. БИНОМ. Лаборатория знаний. 2006. 247 с.
      [9].      Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е изд. Пер. с англ. М.: Издательский дом «Вильямс». 2002. 528 с.
    [10].     Белоусов А.И., Ткачев С.Б. Дискретная математика. 4-е изд. М.: Изд-во МГТУ им. Н.Э. Баумана. 2006. 744 с.
    [11].      Исмагилов Р.С., Мастихина А.А. К вопросу частичного угадывания формальных языков // Вестник МГТУ им. Н.Э. Баумана. Сер. «Естественные науки». 2016. № 2. С. 3-15.