1. Автомат. Подходы к определению и изучению автоматов. Концепция порождения и распознавания. Применение теории автоматов.
2. Знак. Символ. Алфавит. Множество универсум. Слово. Строка. Конкатенация. Формальный язык. Операции над формальными языками.
3. Формальная грамматика. Терминальный и нетерминальные знаки. Продукция. Вывод в грамматике. Сентенциальная форма. Сентенция.
4. Способы задания формальной грамматики. Нотация Бэкуса-Наура.
5. Классификация языков по Хомскому.
6. Лемма о виде продукций формальных грамматик. Теорема об e-свободной КС-грамматике.
7. Теорема о приведении КС-грамматик.
8. Теорема о КС-грамматике без цепных правил.
9. Разрешимость языков. Теоремы о разрешимости языков, заданных произвольной и неукорачивающей грамматикой.
10. Теоремы о разрешимости проблем пустоты и бесконечности КС-языка.
11. Теорема о разрешимости языка, заданного КС-грамматикой.
12. Машина Тьюринга. Способы задания машины Тьюринга. Конфигурация машины Тьюринга. Тезис Тьюринга.
13. Вычислимость по Тьюрингу. Операции над машинами Тьюринга.
14. Теорема о вычислимости композиции машин Тьюринга.
15. Лемма о вычислимости предиката с восстановлением.
16. Теорема о вычислимости разветвления машин Тьюринга.
17. Лемма о машине Тьюринга с правой полулентой.
18. Теорема об универсальной машине Тьюринга. Теоремы Шеннона и Боброу-Минского.
19. Теорема о неразрешимости проблемы остановки для машины Тьюринга.
20. Теорема Райса.
21. Теоретические ограничения алгоритмического метода.
22. Классификация автоматов. Автоматы и грамматики.
23. Тезис Поста. Теорема о распознавании и порождении языков, заданных произвольными грамматиками.
24. Детерминированная и недетерминированная машина Тьюринга.
25. Сеть Петри. Способы задания и функционирование. Языки сети Петри.
26. Свободный, префиксный и терминальный языки сети Петри. Теорема о мощности классов языков сети Петри.
27. Магазинный автомат. Детерминированный и недетерминированный магазинный автомат. Теорема о магазинном автомате и КС-языках.
28. Дерево грамматического разбора. Семантическое дерево. Синтаксический анализ и компиляция.
29. Методы синтаксического анализа. Грамматический разбор «сверху-вниз» и «снизу-вверх».
30. Грамматический разбор «сверху-вниз». Теорема о LL(k) грамматиках.
31. Грамматический разбор «снизу-вверх». LR(k)-грамматики.
32. Лемма о левостороннем (правостороннем) выводе для КС-грамматик.
33. Конечный автомат и регулярные языки. Устройство управления автоматов как конечный автомат.
34. Конечный автомат. Задание функций на множестве строк. Автоматное отображение.
35. Изоморфизм и гомоморфизм конечных автоматов. Неотличимые состояния и неотличимые автоматы.
36. Теорема о минимизации конечных автоматов. Алгоритм Мили.
37. Определение автомата Мура. Теорема о существование автомата Мура.
38. Построение автомата Мура. Минимизация автомата Мура.
39. Теорема о представимости регулярных языков конечными автоматами.
40. Алгебра регулярных событий. Теорема о представимости регулярного события регулярной грамматикой.
41. Алгебра регулярных событий. Теорема о представимости регулярного события конечным автоматом.
42. Источник. Источник и регулярный язык. Теорема о детерминации источников.
43. Сети из автоматов. Основные виды соединения автоматов. Способы синхронизации в автоматной сети.
44. Комбинационный автомат. Теорема о комбинационном автомате.
45. Теорема о структурном синтезе конечных автоматов.
46. Синхронный автомат. Синтез синхронных автоматов. Синхронный элемент задержки.
47. Асинхронный автомат. Синтез асинхронных автоматов. Асинхронный элемент задержки.
48. Апериодические схемы. Синтез апериодических схем.
49. Структурный синтез комбинационных автоматов. Теорема о полноте автоматных базисов.
50. Кодирование алфавитов конечного автомата. Синтез конечных автоматов в заданном автоматном базисе.
Доцент кафедры ВКСС В.С. Выхованец
