3622
правки
Изменения
→1. Автоматы и регулярные языки
__TOC__
== 1. Автоматы и регулярные языки ==
# '''fixed !!!''' [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать ## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.## Добавить английские аналоги терминам# '''fixed !!!''' [[Регулярные языки: два определения и их эквивалентность]]## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. '''Короче, везде надо использовать для классов языков \mathrm!'''## Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.) ## Мне кажется, первое определение — это по сути означает множество языков, представимое регулярными выражениями, думаю, надо это упомянуть. P.S. Более того, если я не ошибаюсь, кажется, вообще в конспектах нигде нет определения регулярных выражений, так что это определение по сути им является.## <tex>\bigcap\limits_{R - nadreg}</tex>, вот это nadreg выглядит совершенно мерзко, надо от него избавиться. Возможно, найти/придумать разумный английский термин и писать под объединением что-то вроде R is X, где X — это название, которое вы найдется или придумаете.Англоязычные термины
# [[Детерминированные конечные автоматы]]
## Английские термины
## Добавить ссылку на факт про эквивалентность автоматных и регулярных
## Англоязычные источники (хотя бы википедия)
# '''!!!''' [[Прямое произведение ДКА]]## Вообще зачем такой короткий конспект нужен, не знаюНаписать, надо придумать, куда его запихать.как построить автомат для пересечения языков (с картинками)# ''fixed'' [[Недетерминированные конечные автоматы]]
## Английские термины
## Англоязычные источники (хотя бы википедия)## Написать, что класс языков совпадает с AUT, и почему (потому что алгоритм Томпсона)Отрефакторить псевдокод
# [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
## Отрефакторить псевдокод
## Добавить ссылки, см. также
## Исправить tex в знаках неравенств
# [[Автоматы с eps-переходами. Eps-замыкание]]
# ''fixed'' # Добавить источники информации, см. также## Написать, где используется алгоритм eps-замыкания# [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]## Опять классы языков курсивомДобавить ссылок# '''!!!''' [[Решение уравнений в регулярных выражениях]]## Исправить неясный переход во второй части утверждения (да и вообще лучше доказательство поясней написать)## Внутренние Добавить ссылки на автоматные и регулярные языки## Добавить ещё что-нибудь про то, где используются такие системы (кроме теоремы Клини)# [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]## Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини
# [[Замкнутость регулярных языков относительно различных операций]]
#: см. 1# ''fixed'' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]## <tex>paths</tex> выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm
# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]
#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)
# '''взяли !!!''' [[Доказательство нерегулярности языков: лемма о разрастании]]## пофиксить неправильное доказательство. Точнее, может, оно и правильное, но не нужно, так как не показывает пример нерегулярного языка, для которого лемма о накачке выполняется.## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины # [[Решение уравнений в регулярных выражениях]]# '''написан !!!''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]#: фиг знает что это, но надо написать, видимо
# [[Эквивалентность состояний ДКА]]
# # Добавить ссылок# '''!!!''' [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]## Структурно написать алгоритм## Таблички оформить прилично## Добавить ссылок
# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
# '''!!!''' [[Контексты и синтаксические моноиды]]## добавить английских терминов, ссылку на англоязычную вики## доказательство последнего утверждения## вообще написать что-нибудь еще бы, типа зачем оно вообще надо, ну или хотя бы еще пару интересных примеров про синтактические моноиды каких-нибудь классов языков, например.
== 2. Контекстно-свободные грамматики ==
