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