Теория автоматов и формальные грамматики

Кафедра информатики и автоматизации научных исследований

Специальность: Прикладная информатика

Преподаватель: Афраймович Л.Г.

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

В результате освоения дисциплины обучающийся должен:

Знать: основные понятия теории конечных автоматов, формальных грамматик, контекстно-свободных грамматик и автоматов с магазинной памятью.

Уметь: доказывать основные теоремы теории автоматов, формальных грамматик. Для заданных языков уметь строить конечный автоматы, МП-автоматы, контекстно-свободные грамматики. Уметь доказывать нерегулярность языков, не принадлежность к классу контекстно-свободных языков. Уметь решать задачи минимизации КА; задачи проверки принадлежности слова языку, порождаемому контекстно-свободной грамматике. Уметь определять множество непорождаемых и непродуктивных нетерминальных символов для КСГ.

Владеть: представлениями (навыками)  об автоматах и о формальных грамматиках.

Содержание

1. Конечные автоматы. КА и регулярные языки. Примеры построения КА. Теорема о нерегулярности языка La-b. Замкнутость регулярных языков относительно операций объединения, пересечения и дополнения. Недетерминированные КА и определяемые ими языки. Регулярность языков, определяемых недетерминированными КА. Лемма о разрастании для регулярных языков. Примеры доказательства нерегулярности языков. Операции конкатенации, возведения в степень и итерации. Замкнутость регулярных языков относительно данных операций. Понятие R-выражения и R-языка. Теорема Клини. Алгоритмы синтеза и анализа КА. Бинарное отношение EL(a,b) и критерий регулярности языка. Бинарные отношения неразличимости и p-неразличимости. Связь между бинарными отношениями p и (p+1)-неразличимости. Построение бинарного отношения неразличимости. Минимальный КА. Алгоритм минимизации КА. 7 основных алгоритмических проблем для КА и регулярных языков.

2. Формальные грамматики. Формальные грамматики и языки, порождаемые грамматиками. Классификация грамматик по Хомскому. Элементарные грамматики. Совпадение класса регулярных языков и языков типа 1. Контекстно-свободные грамматики (КСГ) и контекстно-свободные языки (КСЯ). Дерево вывода. Примеры построения КСГ. Алгоритм определения множества продуктивных нетерминальных символов. Алгоритм определения множества порождаемых нетерминальных символов. Алгоритм преобразование КСГ к приведенной форме. Проблемы непустоты КСЯ. Проблема бесконечности КСЯ, теорема о бесконечности КСЯ. Лемма о разрастании для КСЯ. Примеры языков не являющихся КСЯ. Класс КСЯ и операции объединения, пересечения, дополнения, конкатенации и итерации. Понятие грамматики в нормальной форме Хомского. Преобразование КСГ к грамматике в нормальной форме Хомского. Алгоритм Кока-Янгера-Касами.

3. Автоматы с магазинной памятью. МП-автоматы и распознаваемые ими языки. Примеры построения МП-автоматов. Теорема о совпадение класса контекстно-свободных языков и языков распознаваемых МП-автоматами. Детерминированные  контекстно-свободные языки (ДКСЯ). Вопросы замкнутости ДКСЯ относительно операций объединения, пересечения и дополнения.

Лабораторный практикум

  1. Построение КА для заданных языков.
  2. Построение КА распознающего объединение и пересечения заданных языков.
  3. Построение детерминированного КА по заданному недетерминированному КА.
  4. Доказательства нерегулярности языков через лемму о разрастании.
  5. Алгоритм минимизации КА.
  6. Построение элементарных грамматик через КА.
  7. Построение КСГ для заданных языков.
  8. Доказательство не принадлежности к классу КСЯ через лемму о разрастании.
  9. Преобразование КСГ к грамматике в нормальной форме Хомского.
  10. Алгоритм Кока-Янгера-Касами.
  11. Построение детерминированных МП-автоматов для заданных языков.
  12. Построение недетерминированных МП-автоматов для заданных языков.

 

Литература

а) основная литература:

  1. Коган Д.И., Бабкина Т.С. Основы теории конечных автоматов и регулярных языков. Учебное пособие. Издательство ННГУ. 2002.
  2. Ахо А., Хопкрофт Дж., Ульман Дж. Теория синтаксического анализа, перевода и компиляции в 2 тт. Т. 1. М.: Мир., 1978.

б) дополнительная литература:

  1. Гинзбург С. Математическая теория контекстно-свободных языков - М.: Мир. 1973.
  2. Глушков В.М. Синтез цифровых автоматов. - М.: Физматгиз. 1980.
  3. Карпов Ю.Г. Теория автоматов. - С.Пб.: Изд.дом "Питер". 2002.

Отчетность

  • Семестр 4: Экз