1679
правок
Изменения
→Автоматы и регулярные языки
== Автоматы и регулярные языки ==
# '''!!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
## '''!!!''' В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
## Добавить английские аналоги терминам
# '''!!!''' [[Регулярные языки: два определения и их эквивалентность]]
## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. '''Короче, везде надо использовать для классов языков \mathrm!'''
## Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.)
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
# '''!!!''' [[Доказательство нерегулярности языков: лемма о разрастании]]
## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.
## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины
# [[Решение уравнений в регулярных выражениях]]
# '''!!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
#: фиг знает что это, но надо написать, видимо
# [[Эквивалентность состояний ДКА]]
# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
# '''!!!''' [[Контексты и синтаксические моноиды]]
## добавить английских терминов
## доказательство последнего утверждения
## вообще написать что-нибудь еще бы, типа зачем оно вообще надо.
