Программа дисциплины Формальные языки и автоматы Семестр
| Вид материала | Программа дисциплины |
- Рабочая программа дисциплины теория автоматов и формальных языков направление подготовки, 146.98kb.
- 12. Формальные грамматики и автоматы, 176.6kb.
- Календарный план курса учебных занятий по спецкурсу «Формальные языки моделирования, 61.45kb.
- Системное программное обеспечение, 30.48kb.
- Программа учебной дисциплины «Языковая политика СССР и рф» (факультатив для бакалавриата), 71.42kb.
- Программа дисциплины дпп. Дс. 01. Введение в славянскую филологию с элементами страноведения, 146.35kb.
- Программа дисциплины "Языки и методы программирования" (федеральный компонент цикла, 136.22kb.
- Примерные экзаменационные билеты по Информатике и икт, 57.84kb.
- 11. Вероятностные автоматы, 87.13kb.
- Рабочей программы учебной дисциплины языки программирования Уровень основной образовательной, 47.91kb.
Направление 010100 Математика
Профиль Дискретная математика и приложения
Степень бакалавр
Программа
дисциплины Формальные языки и автоматы
Семестр 7
Цель дисциплины:
Углубленное изучение основных разделов теории формальных языков и теории автоматов.
Задачи дисциплины:
ознакомить студентов с базовыми понятиями, методами и результатами теории формальных языков и теории конечных автоматов.
Разделы курса, темы, их краткое содержание
- Языки, грамматики, распознаватели.
- Классы грамматик и классы языков. Иерархия Хомского.
- Контекстно-свободные грамматики: теорема о приведенной грамматике, лемма о накачке, теорема о подстановке, теорема о пересечении, теорема о λ-свободной грамматике, нормальная форма Хомского, алгоритм Кока-Янгера-Касами, устранение левой рекурсии.
- Автоматы с магазинной памятью: конфигурации, варианты распознавания, ДМПА и НМПА, прямая и обратная теоремы о языках, распознаваемых НМПА.
- Синтаксический анализ контекстно-свободных языков. Нисходящий анализ: построение LL-анализатора. Восходящий анализ: метод перенос-свертка, построение LR-анализатора.