Реферат: Программа дисциплины Формальные языки и автоматы Семестр

Направление 010100 Математика


Профиль Дискретная математика и приложения


Степень бакалавр


Программа

дисциплины Формальные языки и автоматы


Семестр 7


Цель дисциплины:

Углубленное изучение основных разделов теории формальных языков и теории автоматов.


Задачи дисциплины:

ознакомить студентов с базовыми понятиями, методами и результатами теории формальных языков и теории конечных автоматов.


Разделы курса, темы, их краткое содержание


Языки, грамматики, распознаватели.

Классы грамматик и классы языков. Иерархия Хомского.

Контекстно-свободные грамматики: теорема о приведенной грамматике, лемма о накачке, теорема о подстановке, теорема о пересечении, теорема о λ-свободной грамматике, нормальная форма Хомского, алгоритм Кока-Янгера-Касами, устранение левой рекурсии.

Автоматы с магазинной памятью: конфигурации, варианты распознавания, ДМПА и НМПА, прямая и обратная теоремы о языках, распознаваемых НМПА.

Синтаксический анализ контекстно-свободных языков. Нисходящий анализ: построение LL-анализатора. Восходящий анализ: метод перенос-свертка, построение LR-анализатора.