Участник:Dgerasimov/Тикеты по конспектам year2011 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎1. Автоматы и регулярные языки)
(→‎1. Автоматы и регулярные языки)
Строка 1: Строка 1:
 +
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
 
== 1. Автоматы и регулярные языки ==
 
== 1. Автоматы и регулярные языки ==
−
# '''!!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
+
# '''взяли !!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
 
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать  
 
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать  
 
## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
 
## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
Строка 30: Строка 31:
 
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
 
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
 
#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
 
#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
−
# '''!!!''' [[Доказательство нерегулярности языков: лемма о разрастании]]
+
# '''взяли !!!''' [[Доказательство нерегулярности языков: лемма о разрастании]]
 
## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.
 
## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.
 
## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины  
 
## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины  
 
# [[Решение уравнений в регулярных выражениях]]
 
# [[Решение уравнений в регулярных выражениях]]
−
# '''!!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
+
# '''взяли !!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
 
#: фиг знает что это, но надо написать, видимо
 
#: фиг знает что это, но надо написать, видимо
 
# [[Эквивалентность состояний ДКА]]
 
# [[Эквивалентность состояний ДКА]]
 
# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
 
# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
 
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
 
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
−
# '''!!!''' [[Контексты и синтаксические моноиды]]
+
# '''взяли !!!''' [[Контексты и синтаксические моноиды]]
 
## добавить английских терминов
 
## добавить английских терминов
 
## доказательство последнего утверждения
 
## доказательство последнего утверждения
 
## вообще написать что-нибудь еще бы, типа зачем оно вообще надо.
 
## вообще написать что-нибудь еще бы, типа зачем оно вообще надо.
 +
 +
== 2. Контекстно-свободные грамматики ==
 +
# [[Формальные грамматики]]
 +
# [[Иерархия Хомского формальных грамматик]]
 +
# [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
 +
# [[Правоконтекстные грамматики, эквивалентность автоматам]]
 +
# [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
 +
# [[Замкнутость КС-языков относительно различных операций]]
 +
# [[Удаление бесполезных символов из грамматики]]
 +
# [[Удаление eps-правил из грамматики]]
 +
# [[Удаление цепных правил из грамматики]]
 +
# [[Удаление длинных правил из грамматики]]
 +
# [[Нормальная форма Хомского]]
 +
# [[Устранение левой рекурсии]]
 +
# [[Приведение грамматики к ослабленной нормальной форме Грейбах]]
 +
# [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
 +
# [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
 +
# [[Алгоритм Эрли]]
 +
# [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
 +
# [[Лемма о разрастании для КС-грамматик]]
 +
# [[Лемма Огдена]]
 +
# [[Существенно неоднозначные языки]]
 +
# [[Автоматы с магазинной памятью]]
 +
# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
 +
# [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
 +
# [[Детерминированные автоматы с магазинной памятью]]
 +
# [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
 +
# [[Нормальная форма ДМП-автомата]]
 +
# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]

Версия 16:29, 21 октября 2013

Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе

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

  1. взяли !!! Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
    1. Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их отсюда, оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
    2. В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
    3. Добавить английские аналоги терминам
  2. done !!! Регулярные языки: два определения и их эквивалентность
    1. Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. Короче, везде надо использовать для классов языков \mathrm!
    2. Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.)
    3. Мне кажется, первое определение — это по сути означает множество языков, представимое регулярными выражениями, думаю, надо это упомянуть. P.S. Более того, если я не ошибаюсь, кажется, вообще в конспектах нигде нет определения регулярных выражений, так что это определение по сути им является.
    4. [math]\bigcap\limits_{R - nadreg}[/math], вот это nadreg выглядит совершенно мерзко, надо от него избавиться. Возможно, найти/придумать разумный английский термин и писать под объединением что-то вроде R is X, где X — это название, которое вы найдется или придумаете.
  3. Детерминированные конечные автоматы
    1. Английские термины
    2. Добавить ссылку на факт про эквивалентность автоматных и регулярных
    3. Англоязычные источники (хотя бы википедия)
  4. Прямое произведение ДКА
    1. Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.
  5. Недетерминированные конечные автоматы
    1. Английские термины
    2. Англоязычные источники (хотя бы википедия)
    3. Написать, что класс языков совпадает с AUT, и почему (потому что алгоритм Томпсона)
  6. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
  7. Автоматы с eps-переходами. Eps-замыкание
  8. Теорема Клини (совпадение классов автоматных и регулярных языков)
    1. Опять классы языков курсивом
    2. Внутренние ссылки на автоматные и регулярные языки
  9. Замкнутость регулярных языков относительно различных операций
    см. 1
  10. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
    1. [math]paths[/math] выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm
  11. Интерпретация булевых формул с кванторами как игр для двух игроков
    вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
  12. взяли !!! Доказательство нерегулярности языков: лемма о разрастании
    1. пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.
    2. добавить ссылок на англоязычные источники, добавить в статью англоязычные термины
  13. Решение уравнений в регулярных выражениях
  14. взяли !!! Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
    фиг знает что это, но надо написать, видимо
  15. Эквивалентность состояний ДКА
  16. Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
  17. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
  18. взяли !!! Контексты и синтаксические моноиды
    1. добавить английских терминов
    2. доказательство последнего утверждения
    3. вообще написать что-нибудь еще бы, типа зачем оно вообще надо.

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

  1. Формальные грамматики
  2. Иерархия Хомского формальных грамматик
  3. Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
  4. Правоконтекстные грамматики, эквивалентность автоматам
  5. Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
  6. Замкнутость КС-языков относительно различных операций
  7. Удаление бесполезных символов из грамматики
  8. Удаление eps-правил из грамматики
  9. Удаление цепных правил из грамматики
  10. Удаление длинных правил из грамматики
  11. Нормальная форма Хомского
  12. Устранение левой рекурсии
  13. Приведение грамматики к ослабленной нормальной форме Грейбах
  14. Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
  15. Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
  16. Алгоритм Эрли
  17. Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
  18. Лемма о разрастании для КС-грамматик
  19. Лемма Огдена
  20. Существенно неоднозначные языки
  21. Автоматы с магазинной памятью
  22. МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
  23. Совпадение множества языков МП-автоматов и контекстно-свободных языков
  24. Детерминированные автоматы с магазинной памятью
  25. Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
  26. Нормальная форма ДМП-автомата
  27. Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Dgerasimov/Тикеты_по_конспектам_year2011&oldid=33184»