Изменения

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

== '''в процессе проверки''' 2. Контекстно-свободные грамматики ==# '''взяли''' [[Формальные грамматики]]## примеры неинтересные, хотя бы какуюМП-нибудь контекстно-зависимую грамматику надо. Станкевич рассказывал клевый пример с грамматикой 0^n 1^n 2^n, вот его надо запилить## определение выводимости за 0 или более шагов немного неправильное, надо бы потребовать, чтобы альфа было равно первому гамма, а бета — последнему гамма. Ну и написать что это рефлексивно-транзитивное замыкание. ## заголовки здоровенные, они первого уровня (автоматы =) , а надо второго (==)## англоязычные термины## ссылки на английские источники# [[Иерархия Хомского формальных грамматик]]## добавить англоязычные термины## добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.## интервики, ссылка на автоматные граммматики, например, которые есть на вики## на машину Тьюринга можно внутреннюю ссылку сделать# [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]# [[Правоконтекстные грамматики, эквивалентность автоматам]]## Англоязычные термины## Источник бесполезен без конкретного указания, где искать## Внутреннюю ссылку на ДКА# '''взяли''' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]## нормально оформить уже существующий источник## добавить англоязычные термины## интервики## Расписать формально пример грамматики, который уже есть, указать, что именно является множеством нетерминалов, что — множеством терминалов и т.п.## а еще тут стрелки одинаковые и в правилах (надо <texol>\to</tex>) и в выводе (надо <tex>\Rightarrow</tex>)## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.# '''взяли''' [[Замкнутость КС-языков относительно различных операций]]## Че за --? Заменить на —## Half некрасивый, в \mathrm его## В конкатенации что-то немного муть написана## li value="Необходима картинка. 23" — запилить!## Про разворот — доказать## побольше внутренних ссылок, на МП-автомат там, например## проставить категории# '''взяли''' [[Удаление бесполезных символов из грамматики]]## запилить пример (уже есть)## англоязычных терминов где можно## если есть, ссылок на википедию.## вообще нет внутренних ссылок, надо бы добавить## "нетерминалы правой части являются порождающими" — правой части правила, наверное## первый пример сделай чуть более интеллектуальным, добавь что-нибудь типа "D -> aD", напримре (а то какой дурак будет вводить нетерминал без правил :) )## асимптотики какие-нибудь нужны## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также# '''взяли'fixed'' [[Удаление eps-правил из грамматикиАвтоматы с магазинной памятью]]## запилить пример (уже есть)## англоязычных терминов где можно## если есть, ссылок на википедию.## почти нет внутренних ссылок, надо бы добавить## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также## асимптотики какие-нибудь нужны. Вроде для произвольной грамматики это сложно посчитать, но можно: 1. сослаться куда-нибудь на оценки асимптотики. 20. привести пример, на котором будет экспоненциальное время работы (вроде тут так можно) 3. написать, что обычно этот алгоритм запускается после удаления длинных правил, и там все полиномиально (сослаться на НФХ5)</li>## для алгоритма поиска eps-порождающих точно можно асимптотику написатьКартинки увеличить# '''взяли''' [[Удаление цепных правил из грамматики]]Определение жирным## как-то странно ; в примере, определении заменить на первом шаге вроде надо взять все пары (A, A), (B, B), (C, C), (D, D)## англоязычных терминов где можно## если естьАнглоязычные термины правильно оформить, ссылок на википедию.## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также## асимптотикуубрать дублирования# '''взяли''' [[Удаление длинных правил из грамматики]]## англоязычных терминов где можно## если естьИсточники информации, ссылок на википедию.## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также## асимптотикуКатегория# '''взяли''' [[Нормальная форма Хомского]]## "Несколько определений" — а определение одно, выкинуть вообще этот пункт и вынести определение НФХ в заголовок## если есть, ссылок на википедию.## такие кавычки в примере мерзко как-то выглядят, надо либо прямые, либо вообще забить и писать без кавычек# [[Устранение левой рекурсии]]# [[Приведение грамматики к ослабленной нормальной форме Грейбах]]## написать, для чего она нужна## какая асимптотика алгоритма приведения?## ссылки на источники? --[[Участник:Dgerasimov|Дмитрий Герасимов]]# [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]# [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]# [[Алгоритм Эрли]]# [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]# [[Лемма о разрастании для КС-грамматик]]# [[Лемма Огдена]]# ''взяли'' [[Существенно неоднозначные языки]]## добавить английские термины## добавить всякое интервики## добавить ссылок на русские и английские источники## упомянуть то, что проверка грамматики на неоднозначность неразрешима и добавить ссылку на это.# [[Автоматы с магазинной памятью]]# <li> [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]</li># '''fixed''' <li> [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]## Исправить оформление списков: нужно использовать либо точки, либо нумерацию числами</символами, но не оба способа одновременно.li>## Картинка. Что она означает?## Доказательства утверждений написаны непонятно.## Вообще, вся статья является сжатой копипастой из соответствующей главы ХМУ, возможно, нужно полностью переписать ее.# <li> ''fixed'' [[Детерминированные автоматы с магазинной памятью]](0.5) </li># В пример добавить язык автомата# Англоязычные термины# Категория<li> ''fixed'' [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]](0.5) </li># Категория# Палку заменить на \mid# Источники информации<li> '''!!!взяли'''[[Нормальная форма ДМП-автомата]](10) </li>## написатьНаписать!# <li> [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]</li><li> [[ДМП-автоматы и неоднозначность]] </li></ol>

== '''в процессе проверки''' 3. Теория вычислимости ===== Разрешимые и перечислимые языки ===# ''fixed'' [[Разрешимые (рекурсивные) языки]]## англоязычные термины## категории## ссылки на википедию, русскую и английскую# ''fixed'' [[Перечислимые языки]](2)## англоязычные термины## ссылки на википедию## написать про классы RE, R, co-RE. Добавить содержательный пример коперечислимого языка# ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]](2.5)# ''fixed'' [[Вычислимые функции]]# Убрать лишние знаки препинания из списков в теоремах## Заменить литературу на источники информации## англоязычные терминыКатегории## ссылки на википедиюОтформатировать по правилам# [[Вычислимые числафункции]]# '''взяли'fixed'' [[Диагональный методВычислимые числа]] (2)## объяснить, что такое универсальная функция неформально, и нафига она нужна. ## Правильно оформить англоязычные термины ## внутренние ссылкиПояснить a(eps) в определении## нужны ссылки на литературу и статьи, особенно на англоязычные. В уже существующем русском источнике не указан номер конкретной страницы, например Единообразно оформить множество рациональных чисел## непонятно, где, собственно, возникает диагональ, надо это показать Все переменные и константы занести в Tex## также статья называется как-то глупо, лучше назвать ее "Универсальная функция" Ссылки заменить на источники информации## см. замечания для главных нумерацийУвеличить дроби## категорию проставитьПояснить подробней мутные места# ''fixed'' [[Свойства перечислимых языков. Теорема Успенского-РайсаУниверсальная функция]](1)## классы языков в mathrmАнглоязычные термины правильно оформить ## заголовки верхнего уровня в ==, а не =Оформить правильно источники информации## англоязычные терминыЗаменить дефисы на тире## категорию проставитьПояснить нотацию про U(n, x) и U_n(x)## ссылки на викиЗаголовки внутри конспекта поправить# ''fixed'' [[Главные нумерацииСвойства перечислимых языков. Теорема Успенского-Райса]](1)## см. "Диагональный метод"## во-первыхПочему языком L_g(i, тут какая-то муть## во-вторых, тут копипаста из Шеня, кажется## в третьих тут наполовину совпадает x) будет X? Как i связано с "Диагональным методом". Короче их надо смержить и нормально написать.X? ## ну и надо написать, зачем И вообще нужны эти главные нумерациидоказательство можно сделать чуть менее мутным :)

## английские источиники и термины ## нормально оформить уже существующий источник ## написать, зачем оно может пригодиться# '''fixed''' [[Иммунные и простые множества]](7)

## Интервики## Добавить категории## Подробней расписать доказательства## Ссылки на леммы внутри конспекта# '''взялиfixed''' [[Теорема о рекурсии]]## во-первых, теоремы именные, соответственно надо эти имена вписать (русские и английские8)

## Неформальное пояснение к теореме## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод

# '''взяли''' [[Теорема о рекурсииКвайны]]#: Добавить примеры простых доказательств с использованием теоремы о рекурсии:## Теоремы Успенского-Райса ## Невычислимости Колмогоровской сложности ## Невычислимости Busy beaver ## аналога I теоремы Геделя о неполноте ## аналога II теоремы Геделя о неполноте ## теоремы о неподвижной точке (простое док-во, есть в Sipser'e и его вроде Станкевич рассказывает)

# [[Колмогоровская сложность]] === Вычислительные формализмы ===<ol><li value="14">[[Машина Тьюринга]]</li># <li> [[Лямбда-исчисление]]</li># <li> '''fixed''' [[Примитивно рекурсивные функции]](10) </li>## названия функций надо в \mathrm или \mathtt## привести пример использования теоремы о примитивной рекурсивностиПомёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]# <li> ''fixed'' [[Частично рекурсивные функции]](2) </li>## англоязычные терминыЗамечание про взаимную рекурсию в обсуждениях## <li> [[Стековые машины, эквивалентность двухстековой машины МТ]]</li># <li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]</li># <li> [[Линейный клеточный автомат, эквивалентность МТ]]</li># <li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]]</li><li> [[Линейный ограниченный автомат]]</li>## внутренние ссылки<li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li></ol> === Примеры неразрешимых задач ===## категории<ol># '<li value="24"> ''взяли'fixed'' [[m-сводимость]](3) </li>#Англоязычные термины правильно оформить# англоязычные терминыДобавить примеры m-сведения задач# Заменить знаки неравенств#Добавить категории# ссылка Ссылку на английскую википедию, у существующих источников ссылки на номер страницыПСП оформить правильно## написать еще про сведение по Тьюрингу Переменные и чем m-сведение от него принципиально отличается. Написать, что произойдет, если использовать программы с оракулом, который разрешает задачу останова, написать про иерархию Тьюрингаконстанты взять в Tex# '''взяли''' <li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]</li>## англоязычные термины## {{tick}} англоязычные источники, в частности, википедия## {{tick}} Выполним m-сведение множества пар из машины Тьюринга (МТ) и строки w , где M(w) не зависает — у этого множества есть название## {{tick}} "Договоримся, что состояния в автомате МТ не существует (его роль может выполнять сток)," — щито? Что такое сток?## {{tick}} "можно доказать по индукции, что если первая строка имеет вид", ну так доказать надо## {{tick}} побольше интервики## {{tick}} форматирование внутри теорем упоротое, какое-то полотно текста. Можно оформить правила преобразования как список, например и т.п.## {{tick}} Вот эти вот left и right в док-ве основной теоремы совсем непонятны. Либо убрать их и написать понятнее, либо там же показать пример применения этих функций.## вообще в целов привести к более адекватному и понятному виду# <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>