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

Автоматы и регулярные языки

Регулярные языки и ДКА

1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
2. Регулярные языки: два определения и их эквивалентность, регулярные выражения
3. Детерминированные конечные автоматы
4. Прямое произведение ДКА
5. Простой сопоставитель регулярных выражений [math] \star [/math]

НКА

6. Недетерминированные конечные автоматы
7. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
8. Автоматы с eps-переходами. Eps-замыкание
9. Теорема Клини (совпадение классов автоматных и регулярных языков)
10. Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

Минимизация ДКА

11. Эквивалентность состояний ДКА
12. Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
13. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
14. Алгоритм Бржозовского[math] ^\star [/math]

Свойства конечных автоматов

15. Доказательство нерегулярности языков: лемма о разрастании
16. Интерпретация булевых формул с кванторами как игр для двух игроков
17. Решение уравнений в регулярных выражениях
18. Замкнутость регулярных языков относительно различных операций
19. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
20. Контексты и синтаксические моноиды

Другие автоматы

21. Локальные автоматы[math] ^\star [/math]
22. Двусторонний детерминированный конечный автомат[math] ^\star [/math]
23. Квантовые конечные автоматы[math] ^\star [/math]
24. Автоматы Мура и Мили[math] ^\star [/math]
25. Автоматы в современном мире[math] ^\star [/math]

Контекстно-свободные грамматики

Базовые понятия о грамматиках

26. Формальные грамматики
27. Иерархия Хомского формальных грамматик
28. Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
29. Правоконтекстные грамматики, эквивалентность автоматам
30. Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
31. Замкнутость КС-языков относительно различных операций
32. Регулярная аппроксимация КС-языков[math] ^\star [/math]

Нормальные формы КС-грамматик

33. Удаление бесполезных символов из грамматики
34. Удаление длинных правил из грамматики
35. Удаление eps-правил из грамматики
36. Удаление цепных правил из грамматики
37. Нормальная форма Хомского
38. Устранение левой рекурсии
39. Приведение грамматики к ослабленной нормальной форме Грейбах
40. Нормальная форма Куроды[math] ^\star [/math]

Алгоритмы разбора

41. Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
42. Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
43. Алгоритм Эрли 2
    1. разобраться с псевдокодами, там определенно есть лажа в индексах
44. Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики

Опровержение контекстно-свободности языка

45. Лемма о разрастании для КС-грамматик
46. Лемма Огдена
47. Существенно неоднозначные языки
48. Теорема Парика[math] ^\star [/math]

МП-автоматы

49. Автоматы с магазинной памятью
50. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
51. Совпадение множества языков МП-автоматов и контекстно-свободных языков
52. Детерминированные автоматы с магазинной памятью
53. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
54. Нормальная форма ДМП-автомата[math] ^\star [/math]
55. Эквивалентность ДМП-автоматов[math] ^\star [/math]
56. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
57. ДМП-автоматы и неоднозначность