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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 31: Строка 31:
 
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
 
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
 
<li>[[Автоматы в современном мире]]<tex> ^\star </tex></li>
 
<li>[[Автоматы в современном мире]]<tex> ^\star </tex></li>
 +
== Контекстно-свободные грамматики ==
 +
=== Базовые понятия о грамматиках ===
 +
<li>[[Формальные грамматики]]
 +
</li><li>[[Иерархия Хомского формальных грамматик]]
 +
</li><li>[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
 +
</li><li>[[Правоконтекстные грамматики, эквивалентность автоматам]]
 +
</li><li>[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
 +
</li><li>[[Замкнутость КС-языков относительно различных операций]]
 +
</li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
 +
</li>
 +
=== Нормальные формы КС-грамматик ===
 +
<li>[[Удаление бесполезных символов из грамматики]]
 +
</li><li>[[Удаление длинных правил из грамматики]]
 +
</li><li>[[Удаление eps-правил из грамматики]]
 +
</li><li>[[Удаление цепных правил из грамматики]]
 +
</li><li>[[Нормальная форма Хомского]]
 +
</li><li>[[Устранение левой рекурсии]]
 +
</li><li>[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
 +
</li><li>[[Нормальная форма Куроды]]<tex> ^\star </tex>
 +
</li>
 +
=== Алгоритмы разбора ===
 +
<li>[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
 +
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
 +
</li><li>[[Алгоритм Эрли]]
 +
</li><li>[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
 +
</li>
 +
=== Опровержение контекстно-свободности языка ===
 +
</li><li>[[Лемма о разрастании для КС-грамматик]]
 +
</li><li>[[Лемма Огдена]]
 +
</li><li>[[Существенно неоднозначные языки]]
 +
</li><li>[[Теорема Парика]]<tex> ^\star </tex>
 +
</li>
 +
=== МП-автоматы ===
 +
<li>[[Автоматы с магазинной памятью]]
 +
</li><li>[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
 +
</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
 +
</li><li>[[Детерминированные автоматы с магазинной памятью]]
 +
</li><li>[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
 +
</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>
 +
</li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>
 +
</li><li>[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 +
</li><li>[[ДМП-автоматы и неоднозначность]]</li>
 +
 
</ol>
 
</ol>

Версия 16:00, 17 мая 2017

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

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

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

    6. НКА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    49. МП-автоматы

  49. Автоматы с магазинной памятью
  50. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
  51. Совпадение множества языков МП-автоматов и контекстно-свободных языков
  52. Детерминированные автоматы с магазинной памятью
  53. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
  54. Нормальная форма ДМП-автомата[math] ^\star [/math]
  55. Эквивалентность ДМП-автоматов[math] ^\star [/math]
  56. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
  57. ДМП-автоматы и неоднозначность
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков:Тикеты&oldid=60791»