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

Материал из Викиконспекты
Перейти к: навигация, поиск
(sta)
Строка 5: Строка 5:
 
## Добавить английские аналоги терминам
 
## Добавить английские аналоги терминам
 
# [[Регулярные языки: два определения и их эквивалентность]]
 
# [[Регулярные языки: два определения и их эквивалентность]]
 +
## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами.
 +
## Множества вроде R_i тоже следует обозначать большими прмямыми буквами (\mathrm, кажется), так как они перепутываются с языками L, M и т.п.)
 +
## Мне кажется, первое определение — это по сути означает множество языков, представимое регулярными выражениями, думаю, надо это упомянуть.
 +
## <tex>\bigcap\limits_{R - nadreg}</tex>, вот это nadreg выглядит совершенно мерзко, надо от него избавиться. Возможно, найти/придумать разумный английский термин и писать под объединением что-то вроде R is X, где X — это название, которое вы найдется или придумаете.
 
# [[Детерминированные конечные автоматы]]
 
# [[Детерминированные конечные автоматы]]
 
# [[Недетерминированные конечные автоматы]]
 
# [[Недетерминированные конечные автоматы]]

Версия 18:20, 16 октября 2013

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

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