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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Автоматы и регулярные языки: баг)
(Автоматы и регулярные языки)
Строка 1: Строка 1:
== Автоматы и регулярные языки ==
+
== 1. Автоматы и регулярные языки ==
 
# '''!!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
 
# '''!!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
 
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать  
 
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать  

Версия 22:59, 17 октября 2013

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

  1. !!! Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
    1. Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их отсюда, оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
    2. В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
    3. Добавить английские аналоги терминам
  2. !!! Регулярные языки: два определения и их эквивалентность
    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. Детерминированные конечные автоматы
  4. Прямое произведение ДКА
    1. Английские термины
    2. Добавить ссылку на факт про эквивалентность автоматных и регулярных
  5. Недетерминированные конечные автоматы
    1. Английские термины
  6. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
  7. Автоматы с eps-переходами. Eps-замыкание
  8. Теорема Клини (совпадение классов автоматных и регулярных языков)
    1. Опять классы языков курсивом
  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. вообще написать что-нибудь еще бы, типа зачем оно вообще надо.