Изменения

== 1. Автоматы и регулярные языки (проверяются) ==# === Регулярные языки и ДКА ===<ol><li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]](0.5) </li># <li> [[Регулярные языки: два определения и их эквивалентность]](0.5) </li>## Англоязычные термины# '''fixed''' Ссылки заменить на источники информации# Добавить См. также на ДКА<li> [[Детерминированные конечные автоматы]]</li>## Английские термины## Добавить ссылку на факт про эквивалентность автоматных и регулярных## Англоязычные источники (хотя бы википедия)## Добавить про изоморфизм автоматов вместе с алгоритмом# '''fixed''' <li> [[Прямое произведение ДКА]]</li></ol>## Написать, как построить автомат для пересечения языков (с картинками)## Добавить фактов про прямое произведение (задание 4.2.14 из ХМУ)=== НКА ===## Источники информации, см. также<ol># ''fixed'' <li value="5"> [[Недетерминированные конечные автоматы]]</li>## Английские термины## Отрефакторить псевдокод## Источники информации# '''fixed''' <li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]</li>## Отрефакторить псевдокод## Добавить ссылки, см. также## Исправить tex в знаках неравенств## Какой-то абсолютно нечитабельный конспект. Словесное описание не помешало бы в начале## Можно добавить простое альтернативное доказательство# <li> [[Автоматы с eps-переходами. Eps-замыкание]](0.7) </li>#Англоязычные термины правильно# Добавить источники информации, см. также## Написать, где используется алгоритм eps-замыкания# Пофиксить знаки неравенств# Определение жирным# Многоточия на \ldots<li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]](0.3) </li>## Добавить ссылок# <li> '''fixed!!!''' [[Решение Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]](5) </li>## Исправить неясный переход во второй части утверждения Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (да и вообще лучше доказательство поясней написатьпривести пример)## Добавить ссылкиНеплохо бы добавить ссылку на источник доказательства</ol> === Минимизация ДКА ===<ol><li value="10"> [[Эквивалентность состояний ДКА]] </li><li> [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] </li>## Добавить ещё что-нибудь про то<li> [[Минимизация ДКА, где используются такие системы алгоритм Хопкрофта (сложность O(n log n))]] </li><li> '''!!!''' [[Алгоритм Бржозовского]] (кроме теоремы Клини5)</li>## Добавить пример решениядоказательство</ol> === Свойства конечных автоматов ===<ol># <li value="14"> '''!!!''' [[Альтернативное доказательство теоремы Клини Доказательство нерегулярности языков: лемма о разрастании]] (5) </li># Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (через систему уравнений с википедии)# Доказательство леммы о накачке в регулярных выражениях)общем виде<li> [[Интерпретация булевых формул с кванторами как игр для двух игроков]](1) </li>## Написать* Вообще левая штука, относящаяся скорее к логике. Наверное, почему получение регулярного выражение надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из системы уравнений лучшелеммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, чем напрямую и сделать интервики из теоремы Клинипрошлого конспекта<li> [[Решение уравнений в регулярных выражениях]] </li># <li> '''!!!''' [[Замкнутость регулярных языков относительно различных операций]](6) </li>## Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности# <li> '''!!!''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]](5) </li>## Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)## Оформить нормально источники информации## Исправить багу с примечаниями## Англоязычные термины# <li> [[Интерпретация булевых формул с кванторами как игр для двух игроковКонтексты и синтаксические моноиды]]</li></ol> === Другие автоматы ===#: вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось)<ol># <li value="20"> '''!!!''' [[Доказательство нерегулярности языков: лемма о разрастанииЛокальные автоматы]]## Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии5)</li>## Доказательство леммы о накачке в общем видеГде это нужно и зачем применяется# '''fixed''' <li> [[Эквивалентность состояний ДКАДвусторонний детерминированный конечный автомат]]</li>## Добавить ссылок## Добавить алгоритм проверки на эквивалентность не через минимизацию## Добавить см. также, источники информации (если есть)# '''fixed''' <li> [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состоянийКвантовые конечные автоматы]]</li>## Структурно написать алгоритм## Таблички оформить прилично## Добавить ссылок# <li> '''взяли!!!''' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))Автоматы Мура и Мили]]## Отформатировать псевдокоды {{---}} там путается Tex и \mathtt, выглядит иногда не очень красиво## Пояснить подробней "очевидные" факты## Исправить знаки неравенств## Сделать пары угловыми скобками## Обернуть while в тексте в \mathrm## Заменить литературу на источники информации## Добавить более простой алгоритм через hashset'ы и hashmap'ы (по возможности5)## Исправить ошибки в конспекте# '''fixed''' [[Контексты и синтаксические моноиды]]## Добавить примеры контекстов## Добавить правку про <state/li> \cdot <word> из обсуждений## Картинки Примеры интересных задач или применений на эти автоматы (автомата правых контекстов хотя быдля согласования написать куратору)## Кривое начало рассуждения в лемме о конечности двухсторонних контекстов## Да и вообще всё рассуждение какое-то сумбурное и нечёткое {{---}} переписать</ol>