Экзаменационная программа по курсу «Теория автоматов и формальных языков», 2008/09 уч. год

Экзаменационная программа по курсу «Теория автоматов и формальных языков»

Лектор	Деундяк Владимир Михайлович
Семестр	весна
Курс	2
Учебный год	2008/9
Продолжительность	51
Отделение	Информационные технологии
Факультет	Математики, механики и компьютерных наук

1. Полугруппы и моноиды. Степени. Свойства степеней. Подполугруппы иподмоноиды. Примеры.
2. Алфавит. Слова. Операции над словами. Префиксы и суффиксы, подслова. Длина слова. Примеры.
3. Язык над алфавитом Σ. Пустой язык. Язык Σ*. Язык Σ* как моноид. Операции над языками. Примеры.
4. Грамматики. Выводимые слова. Язык, порождаемый грамматикой. Примеры.
5. Общая схема автомата распознавателя.
6. Классификация Хомского формальных языков. Примеры.
7. Регулярные множества. Регулярные выражения. Примеры.
8. Лемма о регулярных выражениях.
9. Линейные уравнения с регулярными коэффициентами. Неподвижная точка. Теорема.
10. Системы линейных уравнений с регулярными коэффициентами. Алгоритм Гаусса. Примеры.
11. Лемма о праволинейности элементарных языков. Лемма о праволинейности результатов операций над ПЛ-языками. Следствие. Лемма о регулярности ПЛ-языков (схема доказательства).
12. Конечные автоматы. Конфигурация. Достижимые состояния. Такт. Язык L(M), определяемый автоматом M. Примеры автоматов.
13. Детерминированные и недетерминированные автоматы. Теорема о редукции (схема доказательства).
14. Лемма о праволинейности конечных автоматов (схема доказательства).
15. Лемма об автоматности элементарных языков (схема доказательства).
16. Лемма об автоматности результатов операций над языками (схема доказательства).
17. Теорема о совпадении праволинейных, регулярных и автоматных языков.
18. Алгоритм 1 проверки КС-грамматики на непустоту. Алгоритм 2 построения по КС-грамматике стабилизационного множества. Примеры.
19. Недостижимые и бесполезные символы в КС-грамматике. Алгоритм 3 устранения у КС-грамматик недостижимых символов. Алгоритм 4 устранения у КС-грамматик бесполезных символов. Примеры.
20. Неукорачивающиеся КС-грамматики. Алгоритм 5 преобразования КС-грамматик к неукорачивающемуся виду. Примеры.
21. Цепные продукции в КС-грамматиках. КС-грамматики без циклов. Алгоритм 6 удаления цепных продукций. Примеры.
22. Приведенные КС-грамматики. Алгоритм преобразования КС-грамматик к приведенному виду. Примеры.
23. МП-автоматы. Конфгурация. Достижимые состояния. Такт. Язык L(M), определяемый МП-автоматом M. Примеры. ДМП-автоматы.
24. Нормальная форма Хомского КС-грамматик. Алгоритм преобразования КС-грамматик к нормальной форме Хомского. Примеры.
25. Каноническая форма Грейбах КС-грамматик. Примеры.
26. РМП-автоматы. Языки L(M) и Lm(M), определяемые РМП-автоматом M. Теорема о совпадении языков.