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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Алгоритмы разбора)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 2 участников)
Строка 3: Строка 3:
 
<ol>
 
<ol>
 
<li>[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]</li>
 
<li>[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]</li>
−
<li>[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]</li>
+
<li>[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]] 0.5</li>
 +
# поправить тех
 
<li>[[Детерминированные конечные автоматы]]</li>
 
<li>[[Детерминированные конечные автоматы]]</li>
−
<li>[[Прямое произведение ДКА]]</li>
+
<li>[[Прямое произведение ДКА]] 0.5</li>
−
<li>[[Простой сопоставитель регулярных выражений]] <tex> \star </tex></li>
+
# поправить тех
 +
<li>[[Простой сопоставитель регулярных выражений]] 0.5 <tex> \star  
 +
</tex></li>
 +
# поправить тех
 
=== НКА ===
 
=== НКА ===
 
<li>[[Недетерминированные конечные автоматы]]</li>
 
<li>[[Недетерминированные конечные автоматы]]</li>
Строка 15: Строка 19:
 
=== Минимизация ДКА ===
 
=== Минимизация ДКА ===
 
<li>[[Эквивалентность состояний ДКА]]</li>
 
<li>[[Эквивалентность состояний ДКА]]</li>
−
<li>[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]</li>
+
<li>[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] 0.5</li>
−
<li>[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]</li>
+
# поправить тех
 +
<li>[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
 +
0.5</li>
 +
# поправить тех
 +
# заменить дефис на тире, там где это надо
 
<li>[[Алгоритм Бржозовского]]<tex> ^\star </tex></li>
 
<li>[[Алгоритм Бржозовского]]<tex> ^\star </tex></li>
 
=== Свойства конечных автоматов ===
 
=== Свойства конечных автоматов ===
−
<li>[[Доказательство нерегулярности языков: лемма о разрастании]]</li>
+
<li>[[Доказательство нерегулярности языков: лемма о разрастании]] 0.5</li>
−
<li>[[Интерпретация булевых формул с кванторами как игр для двух игроков]]</li>
+
# оформить правильно английские термины
 +
<li>[[Интерпретация булевых формул с кванторами как игр для двух игроков]] 2</li>
 +
# Создать новый конспект и вынести материал из статьи "Исчисление предикатов"
 
<li>[[Решение уравнений в регулярных выражениях]]</li>
 
<li>[[Решение уравнений в регулярных выражениях]]</li>
−
<li>[[Замкнутость регулярных языков относительно различных операций]]</li>
+
<li>[[Замкнутость регулярных языков относительно различных операций]]
 +
0.5</li>
 +
# поправить тех
 
<li>[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]</li>
 
<li>[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]</li>
−
<li>[[Контексты и синтаксические моноиды]]</li>
+
<li>[[Контексты и синтаксические моноиды]] 0.5</li>
 +
# поправить тех
 
=== Другие автоматы ===
 
=== Другие автоматы ===
−
<li>[[Локальные автоматы]]<tex> ^\star </tex></li>
+
<li>[[Локальные автоматы]]<tex> ^\star </tex> 0.5 </li>
 +
# поправить тех
 
<li>[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex></li>
 
<li>[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex></li>
 
<li>[[Квантовые конечные автоматы]]<tex> ^\star </tex></li>
 
<li>[[Квантовые конечные автоматы]]<tex> ^\star </tex></li>
 
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
 
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
−
<li>[[Автоматы в современном мире]]<tex> ^\star </tex></li>
+
<li>[[Автоматы в современном мире]]<tex> ^\star </tex> 0.5</li>
 +
# поправить тех
 +
 
 
== Контекстно-свободные грамматики ==
 
== Контекстно-свободные грамматики ==
 
=== Базовые понятия о грамматиках ===
 
=== Базовые понятия о грамматиках ===
 
<li>[[Формальные грамматики]]
 
<li>[[Формальные грамматики]]
 
</li><li>[[Иерархия Хомского формальных грамматик]]
 
</li><li>[[Иерархия Хомского формальных грамматик]]
−
</li><li>[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
+
</li><li>[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] 1
−
</li><li>[[Правоконтекстные грамматики, эквивалентность автоматам]]
+
# Поправить тех
−
</li><li>[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
+
</li><li>[[Правоконтекстные грамматики, эквивалентность автоматам]] 0.5
−
</li><li>[[Замкнутость КС-языков относительно различных операций]]
+
# Добавить см. также
 +
</li><li>[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] 0.5
 +
# Поправить тех
 +
</li><li>[[Замкнутость КС-языков относительно различных операций]] 0.5
 +
# поправить тех
 
</li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
 
</li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
 
</li>
 
</li>
 +
 
=== Нормальные формы КС-грамматик ===
 
=== Нормальные формы КС-грамматик ===
 
<li>[[Удаление бесполезных символов из грамматики]]
 
<li>[[Удаление бесполезных символов из грамматики]]
 
</li><li>[[Удаление длинных правил из грамматики]]
 
</li><li>[[Удаление длинных правил из грамматики]]
−
</li><li>[[Удаление eps-правил из грамматики]]
+
</li><li>[[Удаление eps-правил из грамматики]] 0.5
 +
# Поправить тех
 
</li><li>[[Удаление цепных правил из грамматики]]
 
</li><li>[[Удаление цепных правил из грамматики]]
 
</li><li>[[Нормальная форма Хомского]]
 
</li><li>[[Нормальная форма Хомского]]
 
</li><li>[[Устранение левой рекурсии]]
 
</li><li>[[Устранение левой рекурсии]]
 
</li><li>[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
 
</li><li>[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
−
</li><li>[[Нормальная форма Куроды]]<tex> ^\star </tex>
+
</li><li>[[Нормальная форма Куроды]]<tex> ^\star </tex> 0.5
 +
# Поправить тех
 
</li>
 
</li>
 +
 
=== Алгоритмы разбора ===
 
=== Алгоритмы разбора ===
−
<li>[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
+
<li>[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] 0.5
−
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
+
# Поправить тех
 +
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] 0.5
 +
# Поправить тех
 
</li><li>[[Алгоритм Эрли]] 2
 
</li><li>[[Алгоритм Эрли]] 2
 
# разобраться с псевдокодами, там определенно есть лажа в индексах
 
# разобраться с псевдокодами, там определенно есть лажа в индексах
Строка 62: Строка 88:
 
=== Опровержение контекстно-свободности языка ===
 
=== Опровержение контекстно-свободности языка ===
 
</li><li>[[Лемма о разрастании для КС-грамматик]]
 
</li><li>[[Лемма о разрастании для КС-грамматик]]
−
</li><li>[[Лемма Огдена]]
+
</li><li>[[Лемма Огдена]] 0.5
−
</li><li>[[Существенно неоднозначные языки]]
+
# В названиях раздела цифры в тех
 +
</li><li>[[Существенно неоднозначные языки]] 0.5
 +
# Добавить см. также
 
</li><li>[[Теорема Парика]]<tex> ^\star </tex>
 
</li><li>[[Теорема Парика]]<tex> ^\star </tex>
 
</li>
 
</li>
 +
 
=== МП-автоматы ===
 
=== МП-автоматы ===
 
<li>[[Автоматы с магазинной памятью]]
 
<li>[[Автоматы с магазинной памятью]]
−
</li><li>[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
+
</li><li>[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] 0.5
−
</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
+
# Добавить см. также
−
</li><li>[[Детерминированные автоматы с магазинной памятью]]
+
</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]] 0.5
−
</li><li>[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
+
# Поправить тех
 +
</li><li>[[Детерминированные автоматы с магазинной памятью]]  
 +
</li><li>[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]] 0.5
 +
# Добавить см. также
 
</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>
 
</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>
 
</li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>
 
</li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>

Текущая версия на 19:11, 4 сентября 2022

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

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

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

    НКА

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  45. Лемма о разрастании для КС-грамматик
  46. Лемма Огдена 0.5
    1. В названиях раздела цифры в тех
  47. Существенно неоднозначные языки 0.5
    1. Добавить см. также
  48. Теорема Парика[math] ^\star [/math]

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

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