Теория формальных языков:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритмы разбора)
Строка 54: Строка 54:
 
<li>[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
 
<li>[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
 
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
 
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
</li><li>[[Алгоритм Эрли]]
+
</li><li>[[Алгоритм Эрли]] 2
 +
# разобраться с псевдокодами, там определенно есть лажа в индексах
 
</li><li>[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
 
</li><li>[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
 
</li>
 
</li>
 +
 
=== Опровержение контекстно-свободности языка ===
 
=== Опровержение контекстно-свободности языка ===
 
</li><li>[[Лемма о разрастании для КС-грамматик]]
 
</li><li>[[Лемма о разрастании для КС-грамматик]]

Версия 16:24, 12 февраля 2018

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

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

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

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

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

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

  25. Локальные автоматы[math] ^\star [/math]
  26. Двусторонний детерминированный конечный автомат[math] ^\star [/math]
  27. Квантовые конечные автоматы[math] ^\star [/math]
  28. Автоматы Мура и Мили[math] ^\star [/math]
  29. Автоматы в современном мире[math] ^\star [/math]
  30. Контекстно-свободные грамматики

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

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

  39. Удаление бесполезных символов из грамматики
  40. Удаление длинных правил из грамматики
  41. Удаление eps-правил из грамматики
  42. Удаление цепных правил из грамматики
  43. Нормальная форма Хомского
  44. Устранение левой рекурсии
  45. Приведение грамматики к ослабленной нормальной форме Грейбах
  46. Нормальная форма Куроды[math] ^\star [/math]
  47. Алгоритмы разбора

  48. Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
  49. Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
  50. Алгоритм Эрли 2
    1. разобраться с псевдокодами, там определенно есть лажа в индексах
  51. Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
  52. Опровержение контекстно-свободности языка

  53. Лемма о разрастании для КС-грамматик
  54. Лемма Огдена
  55. Существенно неоднозначные языки
  56. Теорема Парика[math] ^\star [/math]
  57. МП-автоматы

  58. Автоматы с магазинной памятью
  59. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
  60. Совпадение множества языков МП-автоматов и контекстно-свободных языков
  61. Детерминированные автоматы с магазинной памятью
  62. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
  63. Нормальная форма ДМП-автомата[math] ^\star [/math]
  64. Эквивалентность ДМП-автоматов[math] ^\star [/math]
  65. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
  66. ДМП-автоматы и неоднозначность