Изменения

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

# === Базовые понятия о грамматиках ===<ol><li value="1"> '''fixed''' [[Формальные грамматики]](5) </li>## Пояснить пример контекстно-зависимой грамматики## Можно ещё примеров различных интересных грамматик добавить(и добавить ссылку на грамматики языков программирования)# '''!!!''' [[Иерархия Хомского формальных грамматик]]Заменить многоточия на \ldots## добавить англоязычные термины## добавить ссылок на русские и английские Оформить правильно источники. И указать конкретные страницы у уже существующегоинфрмации, либо выпилить его нафигдобавить См.также#Категория# интервики, ссылка на автоматные граммматики, напримерВыделить в разборах жирным часть правила, которые есть которая раскрывается на викиданном шаге## на машину Тьюринга можно внутреннюю ссылку сделатьПримеры обозначений## Ссылку на вики Вертикальную черту заменить на ссылку примечанием\mid#В определениях скобки в Tex# Добавить интервики Интервики на другие факты (добавить См. также)рефлексивно-транзитивное замыкание#Убрать ; из определения# Добавить по примеру на каждую грамматику (примеры можно перенести из прошлого конспекта)Выводы в примерах оформить красивей# Почистить обсуждения<li> [[Иерархия Хомского формальных грамматик]] </li><li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]</li>## Добавить источники информации, ссылок, интервики (на Иерархию)# <li> [[Правоконтекстные грамматики, эквивалентность автоматам]]</li>## Англоязычные термины## Источник бесполезен без конкретного указания, где искать## Добавить интервики# ''<li> '!!!'fixed'' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]## нормально оформить уже существующий источник## добавить англоязычные термины## интервики## Симольные скобки взять в tex## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>1) и в выводе (надо <tex>\Rightarrow</texli>)## пояснить, почему грамматика из первого примера неоднозначна, Оформить красиво двусторонние доказательства и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначностьисправить форматирование в остальном.+баллы за более красивые картинки## Добавить заголовков## Перерисовать картинку# <li> '''!!!fixed''' [[Замкнутость КС-языков относительно различных операций]](5) </li>## Пропущен - в КС-языках## Точку в конкатенации лучше опустить## Half некрасивый, c маленькой буквы его## Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half## Добавить примеры других грамматик## Добавить ссылок, см. также# <li> '''!!!fixed''' [[Регулярная аппроксимация КС-языков]](7) </li>## Добавить док-во леммы## Отформатировать псевдокод## Tex правильно оформить## Описание перед псевдокодом перенести## Картинки убого расположены## "свободно-контекстной грамматики" {{---}} и далее встречаются баги в конспекте## Расшифровать RTN (то же с MT)## Источники информации нормально оформить# См. обсуждения</ol> === Нормальные формы КС-грамматик ===<ol><li value="8"> '''!!!fixed''' [[Удаление бесполезных символов из грамматики]](6) </li>## Англоязычных термины нормально оформить## Добавить ссылок## Добавить интервики## Грамматики оформлены криво## Написать, что такое <tex> | \Gamma | </tex>## Написать, откуда берутся такие асимптотики, и как добавить очередь## Аналогично про обход в глубину## Ссылку на НФХ перенести в источники информации## Алгоритмы оформить отдельным подзаголовком# Категория<li> [[Удаление длинных правил из грамматики]]</li>## Добавить источники информации## Подробней расписать время работы## Лишняя запятая в алгоритме после многоточия# '''!!!''' <li> [[Удаление eps-правил из грамматики]]## Англоязычных термины нормально оформить ## Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект## Грамматику G заменить на <tex/li> \Gamma </texli>## Ссылку на НФХ перенести в источники информации## Написать, почему при удалении длинных правил асимптотика будет линейной## Грамматики криво оформлены## Пояснить использование очереди## Пропущены дефисы после КС местами# [[Удаление цепных правил из грамматики]]</li>## Англоязычные термины оформить нормально## Провести в алгоритме аналогию с транзитивным замыканием## Грамматика криво криво оформлена## Расписать асимптотику алгоритма## Ссылку на НФХ перенести в источники информации# '''!!!''' <li> [[Нормальная форма Хомского]]</li>## Англоязычные термины хорошо оформить## Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)## Константы взять в Tex## Пример грамматики криво оформлен## Ссылку на НФХ перенести в источники информации## Заменить знаки неравенств в Tex# '''!!!''' <li> [[Устранение левой рекурсии]]</li>## Англоязычные термины оформить правильно## Кинуть интервики на методы нисходящего разбора (или см. также)## Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило## Отформатировать псевдокод## Знаки неравенств заменить## Источники информации нормально оформить# <li> '''!!!!!fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]](8) </li>## написать, для чего она нужна## Какая асимптотика алгоритма приведения?## Добавить источники информации## Добавить примеры## Англоязычные термины нормально оформить## Отформатировать псевдокод# '''!!!''' Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё) <li> [[Нормальная форма Куроды]] </li></ol> === Алгоритмы разбора ===<ol><li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]</li>## Аккуратно помёрджить с аналогичным конспектом первого курса# <li> '''!!!взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]](10) </li>## Расписать подробней и формальней# '''взяли''' А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать# И желательно расписать динамики через полуинтервалы, а не отрезки# Красиво всё оформить<li> [[Алгоритм Эрли]]</li>## Отформатировать псевдокод## Описать понятно (гуглится ссылка, где алгоритм понятно расписан)## Доказательство плохо отформатировано## Оформить красиво источники информации# <li> '''!!!fixed''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]](5) </li>## Отформатировать псевдокод## Грамматику G заменить на \Gamma## Перенести описание алгоритма перед псевдокодом## Хотелось бы адекватные доказательства читать (см. обсуждения)# </ol> === Опровержение контекстно-свободности языка ===<ol><li value="20"> '''!!!fixed''' [[Лемма о разрастании для КС-грамматик]](6) </li>## Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена## Источники нормально оформить## Добавить см. также на варианты леммы# Категория<li> '''fixed''' [[Лемма Огдена]](10) </li>## Источники информации добавить## '''!!!''' Сюда бы тоже неплохо пример привести, который удовлетворяет обычной лемме, но не удовлетворяет этой (можно взять из прошлого конспекта, если там появится), а так же привести Добавить пример не КС-языка, который удовлетворяет условию этой леммы# Категория<li> [[Существенно неоднозначные языки]]</li></ol> ## Англоязычные термины оформить правильно=== МП-автоматы ===## Ссылки из См. также перенести в источники информации<ol># <li value="23"> ''fixed'' [[Автоматы с магазинной памятью]](0.5) </li>## Картинки увеличить# Определение жирным# ; в определении заменить на ,# Англоязычные термины правильно оформить, убрать дублирования# Источники информации, См. также# Категория<li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]</li>## Добавить источники информации# <li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]</li>## Ссылки и литературу оформить правильно# <li> ''fixed'' [[Детерминированные автоматы с магазинной памятью]](0.5) </li>## В пример добавить язык автомата## Англоязычные термины# Категория<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]](0.5) </li># Категория# Палку заменить на \mid# Источники информации<li> '''!!!!!взяли''' [[Нормальная форма ДМП-автомата]](10) </li>## Написать!# <li> [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]</li>## Разве доказательство не следует из теоремы конспекта о допуске по пустому стеку?<li> [[ДМП-автоматы и неоднозначность]] </li>## Добавить источники информации</ol>

# '''!!!''' [[Разрешимые (рекурсивные) языки]]## Оформить правильно англоязычные термины## Отформатировать псевдокод## Перенести сюда определение вычислимой функции## Добавить определение разрешимого языка в терминах вычислимой функции## Заменить источники на источники информации## Обернуть if в доказательстве неразрешимого языка в \mathrm## Ещё примеров разрешимых языков (желательно не очень тривиальных)# '''!!!'fixed'' [[Перечислимые языки]](2)## Оформить правильно англоязычные термины## Поправить чуть определение полуразрешимого Добавить содержательный пример коперечислимого языка## Отформатировать псевдокоды## Оформить правильно в обе стороны доказательство теоремы## Заменить источники на источники информации## Добавить примеры перечислимых и коперечеслимых языков# ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]](2.5)## Чуть-чуть код форматнутьУбрать лишние знаки препинания из списков в теоремах

## Заменить источники на источники информации## Определения вычислимой функции перенести в конспект Разрешимых языков## Переименовать конспект и чуть-чуть реструктуризовать# ''fixed'' [[Вычислимые числа]](2)

# # Пояснить подробней мутные места# ''fixed'' [[Универсальная функция]] (1)

## Пояснить нотацию про U(n, x) и U_n(x)## Заголовки внутри конспекта поправить# '''!!!'fixed'' [[Свойства перечислимых языков. Теорема Успенского-Райса]](1)## англоязычные термины## классы языков в mathrm## заголовки верхнего уровня в ==Почему языком L_g(i, а не =## категорию проставить## Добавить источники информацииx) будет X? Как i связано с X? ## Заменить в множестве | на \midИ вообще доказательство можно сделать чуть менее мутным :)## Отформатировать псевдокод# '''!!!''' [[Неотделимые множества]]## английские источиники и термины ## нормально оформить уже существующий источник ## написать, зачем оно может пригодиться## Добавить категории## Интервики# '''!!!fixed''' [[Иммунные и простые множества]](7)

# '''!!!fixed''' [[Теорема о рекурсии]](8)

## Правильно оформить англоязычные термины[[Колмогоровская сложность]]## Отформатировать псевдокод## Нормально оформить см. также, источники информации и вывод из теоремы

# '''!!!''' <ol><li value="14">[[Машина Тьюринга]]</li>## Англоязычные термины## Добавить то, для чего она была придумана, рассказать про связь Тьюринга с Чёрчом (научную связь)## Выделить машину Тьюринга жирным в определении## Алгоритмы примеров красиво оформить## Подробней написать про машину Тьюринга с полубесконечной лентой (добавить картинку)## Добавить в многоленточной, что эмулируется многодорожечной## Рассказать весёлую историю про тезис Чёрча-Тьюринга## Заменить ссылки на источники информации## Добавить категории# '''!!!''' <li> [[Лямбда-исчисление]] ''(можно получить 10 баллов суммарно)''## Англоязычные термины## Заменить "в разработке" на "nohate"## Написать грамматику лямбд адекватно## "Аппликация забирает себе всё," - ошибка - абстракция забирает## Провести аналогию между связанными переменными и локальными переменными## "Рассмотрим функции (\lambda x\ .\ x) z и (\lambda y\ .\ y) z." -- а z причём?</li>## Написать, что alpha-конверсия -- отношение эквивалентности## beta-редукция не олицетворяет. Написать определение формально## Написать подробней про нотацию Де Брёйна {{---}} что это упрощает alpha-эквивалентность, дать примеры выражений в этой нотации, пару слов сказать о приведении лямбда выражения в эту нотацию и как делать подстановку в ней## Провести аналогию между нумералами Чёрча и нумерацией Гёделя## Убрать маркированный список из чисел, лучше просто отступ оставить## "<<числуli>>" {{---}} получше оформить## Все константы и переменные взяь в Tex## Добавить примеры выполнения операций сложения, умножения и вычитания## "\operatorname{not} = \lambda b\ .\ \operatorname{if} b\ \operatorname{false} \operatorname{true}" {{---}} пробел не отображается## Добавить в неподвижной точке про Y-комбинатор## Сказать пару слов о типизированном лямбда-исчилении, о выводе типов и подобном## Оформить правильно источники информации, см. также## Добавить категории# '''!!!fixed''' [[Примитивно рекурсивные функции]](10) </li>## названия функций надо в \mathrm## Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]# ''<li> '!!!'fixed'' [[Частично рекурсивные функции]](2) </li>## См. замечания Замечание про взаимную рекурсию в обсуждениях## англоязычные термины## Дефис заменить на тире## "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом## Заменить знаки неравенств ## "неразрешимость проврк," {{---}} опечатки## Оформить правильно источники информации## Добавить категории# <li> [[Стековые машины, эквивалентность двухстековой машины МТ]]</li>## Интервики## Разбить доказательство на абзацы для читабельности## Добавить категории## Правильно оформить источники информации# <li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]</li>## Оформить правильно источники информации## Добавить категории# <li> [[Линейный клеточный автомат, эквивалентность МТ]]</li>## Англоязычные термины правильно оформить## Переменные взять в Tex## Добавить категории## Оформить правильно источники информации# <li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]</li>## внутренние ссылки<li> [[Линейный ограниченный автомат]]</li><li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li>## категории</ol>## Добавить см. также и источники информации

# <ol><li value="24"> '''!!!'fixed'' [[m-сводимость]](3) </li>## Англоязычные термины правильно оформить## Добавить примеры m-сведения задач## Заменить знаки неравенств## Добавить категории## Ссылку на ПСП оформить правильно## Переменные и константы взять в Tex# '''!!!''' <li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]</li>## Англоязычные термины правильно оформить## Заменить дефисы на тире## Заменить знаки неравенств## Все переменные и константы взять в Tex## Добавить примеров решения задач ПСП## Отфомартировать псевдокод## Добавить больше подзаголовков нижнего уровня## Больше интервики## Заменить источники на источники информации## Добавить категории, см. также# <li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]</li>## Источники информации## Добавить см. также# <li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность Неразрешимость задачи об эквивалентности КС-грамматикиграмматик]]</li>## Добавить см. также# <li> '''!!!fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]](6) </li>## Оформить правильно англоязычные термины## Написать более подробное и понятное доказательство## Заменить ссылки на источники информации## Добавить категории## Добавить см. также# '''!!!''' <li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]</li>## Англоязычные термины оформить правильно## Заменить дефисы на тире## Заменить прим. на более адекватный аналог## Заменить источники на источники информации## Добавить информацию по последнему замечанию из обсуждений## Добавить см. также# <li> [[Неразрешимость исчисления предикатов первого порядка]]</li>## Добавить см. также## Заменить ссылки на источники информации# <li> '''!!!взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]](10) </li>## написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.# <li> [[Игра «Жизнь»]] </li><li> [[Неразрешимость игры Braid]] </li><li> '''!!!fixed''' [[Теорема Райса-Шапиро]](8) </li>## Англоязычные термины## Отформатировать псевдокоды## Дать более формальное и понятное определение образца## Разбить доказательство на две части, чтобы это было видно## Написать строгую формулировку теоремы## "следующим образом: для проверяемого элемента y подготовим программу g:" {{---}} плохо смотрится лишнее двоеточие## Лучше явно написать разрешитель для K## "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней## Добавить категории, см. также## Заменить литературу на источники информации</ol>