Изменения

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

# === Базовые понятия о грамматиках ===<ol><li value="1"> '''fixed''' [[Формальные грамматики]](5) </li>## Пояснить пример контекстно-зависимой грамматики## Можно ещё примеров различных интересных грамматик добавить(и добавить ссылку на грамматики языков программирования)# '''fixed''' [[Иерархия Хомского формальных грамматик]]Заменить многоточия на \ldots## добавить англоязычные термины## добавить ссылок на русские и английские Оформить правильно источники. И указать конкретные страницы у уже существующегоинфрмации, либо выпилить его нафигдобавить См.также#Категория# интервики, ссылка на автоматные граммматики, напримерВыделить в разборах жирным часть правила, которые есть которая раскрывается на викиданном шаге## на машину Тьюринга можно внутреннюю ссылку сделатьПримеры обозначений## Ссылку на вики Вертикальную черту заменить на ссылку примечанием\mid#В определениях скобки в Tex# Добавить интервики Интервики на другие факты (добавить См. также)рефлексивно-транзитивное замыкание#Убрать ; из определения# Добавить по примеру на каждую грамматику (примеры можно перенести из прошлого конспекта)Выводы в примерах оформить красивей# Почистить обсуждения<li> [[Иерархия Хомского формальных грамматик]] </li><li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]</li>## Добавить источники информации, ссылок, интервики (на Иерархию)# ''fixed'' <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>## Написать, откуда берутся такие асимптотики, и как добавить очередь## Аналогично про обход в глубину## Ссылку на НФХ перенести в источники информации## Алгоритмы оформить отдельным подзаголовком# ''fixed'' Категория<li> [[Удаление длинных правил из грамматики]]</li>## Добавить источники информации## Подробней расписать время работы## Лишняя запятая в алгоритме после многоточия# '''!!!''' <li> [[Удаление eps-правил из грамматики]]## Англоязычных термины нормально оформить ## Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект## Грамматику G заменить на <tex/li> \Gamma </texli>## Ссылку на НФХ перенести в источники информации## Написать, почему при удалении длинных правил асимптотика будет линейной## Грамматики криво оформлены## Пояснить использование очереди## Пропущены дефисы после КС местами# [[Удаление цепных правил из грамматики]]</li>## Англоязычные термины оформить нормально## Провести в алгоритме аналогию с транзитивным замыканием## Грамматика криво криво оформлена## Расписать асимптотику алгоритма## Ссылку на НФХ перенести в источники информации# '''взяли''' <li> [[Нормальная форма Хомского]]</li>## Англоязычные термины хорошо оформить## Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)## Константы взять в Tex## Пример грамматики криво оформлен## Ссылку на НФХ перенести в источники информации## Заменить знаки неравенств в Tex# '''!!!''' <li> [[Устранение левой рекурсии]]</li>## Англоязычные термины оформить правильно## Кинуть интервики на методы нисходящего разбора (или см. также)## Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило## Отформатировать псевдокод## Знаки неравенств заменить## Источники информации нормально оформить# <li> '''!!!!!fixed''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]](8) </li>## написать, для чего она нужна## Какая асимптотика алгоритма приведения?## Добавить источники информации## Добавить примеры## Англоязычные термины нормально оформить## Отформатировать псевдокод## Добавить алгоритм приведения к сильной нормальной форме Грейбах(или хотя бы сказать как-нибудь подробней про неё) <li> [[Нормальная форма Куроды]] </li></ol> # '''fixed''' === Алгоритмы разбора ===<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)

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

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

<li> '''взяли'fixed'' [[Частично рекурсивные функции]] (2) </li># См. замечания Замечание про взаимную рекурсию в обсуждениях# англоязычные термины# Дефис заменить на тире# "функция g(x_1,\ldots,x_k) = минимальное y" {{---}} плохо, когда смешиваются формулы с текстом# Заменить знаки неравенств # "неразрешимость проврк," {{---}} опечатки# Оформить правильно источники информации# Добавить категории <li> [[Стековые машины, эквивалентность двухстековой машины МТ]]</li># Интервики# Разбить доказательство на абзацы для читабельности# Добавить категории# Правильно оформить источники информации

<li value="2024"> '''взяли'fixed'' [[m-сводимость]] (3) </li>

<li> '''fixed''' [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li># Англоязычные термины правильно оформить# Заменить дефисы на тире# Заменить знаки неравенств# Все переменные и константы взять в Tex# Добавить примеров решения задач ПСП# Отфомартировать псевдокод# Добавить больше подзаголовков нижнего уровня# Больше интервики# Заменить источники на источники информации# Добавить категории, см. также

# Источники информации# Добавить см. также<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность Неразрешимость задачи об эквивалентности КС-грамматикиграмматик]]</li># Добавить см. также<li> '''!!!fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li>

<li> '''!!!''' [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li># Англоязычные термины оформить правильно# Заменить дефисы на тире# Заменить прим. на более адекватный аналог# Заменить источники на источники информации# Добавить информацию по последнему замечанию из обсуждений# Добавить см. также

# Добавить см. также# Заменить ссылки на источники информации<li> '''!!!взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li>

<li> [[Игра «Жизнь»]] </li><li> [[Неразрешимость игры Braid]] </li><li> '''!!!fixed''' [[Теорема Райса-Шапиро]] (8) </li>