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