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