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

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

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

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

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

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

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

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

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

О методике изложения некоторых разделов теории формальных языков: леммы о разрастании

Инженерный вестник # 12, декабрь 2015
УДК: 519.76+372.851

Файл статьи:

Belousov_A.pdf (665.82Кб)

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

В статье подробно изложены доказательства трех теорем: леммы Огдена о КС-языках, леммы о разрастании для линейных языков и утверждения о регулярности любого КС-языка в однобуквенном алфавите. В рамках излагаемой методики рассмотрения всех лемм о разрастании, одного из ключевых разделов теории формальных языков, особый акцент сделан на анализе нетривиальных примеров, обычно не рассматриваемых в известных руководствах. К числу таких примеров принадлежат примеры языков, в которых числа вхождений символов удовлетворяют некоторым неравенствам, языков, удовлетворяющих леммам о разрастании, но не принадлежащих соответствующему классу языков. На одном важном примере обсуждается метод анализа, названный «методом факториальной накачки» и основанный на лемме Огдена. В целом, предлагаемая система изложения позволяет глубже оценить возможности лемм о разрастании в плане анализа языков на предмет их принадлежности или непринадлежности к тому или иному классу языков.

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

       [1].      Белоусов А.И., Ткачев С.Б. Дискретная математика. 5-е изд. М.: Изд-во МГТУ им. Н.Э. Баумана. 2015. 744 с.
       [2].      Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. 2-е изд.: Пер. с англ. М.: Издательский дом «Вильямс». 2002. 528 с. [John E. Hopcroft, Rajeev Motvani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 2-nd ed.]
       [3].      Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Пер. с англ. В 2 т. Т. 1. М.: Мир. 1978. 612 с. [Aho A.V., Ullman J.D. The Theory of Parsing, Translation and Compiling. Vol. 1. 1978.]
       [4].      Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. М.: Интернет-университет информационных технологий. БИНОМ. Лаборатория знаний. 2006. 247 с.