Изменения

# '''fixed !!!''' === Регулярные языки и ДКА ===<ol><li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]</li>## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать ## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.## Добавить английские аналоги терминам# '''fixed !!!''' <li> [[Регулярные языки: два определения и их эквивалентность]]</li>## Множества языков (вроде Reg, и Reg') тут зачем-то пишутся курсивом, что вообще не принято, их всегда обозначают большими прямыми (возможно, жирными) буквами. <li> '''Короче, везде надо использовать для классов языков \mathrm!'fixed''## Множества вроде R_i тоже следует обозначать большими прмямыми буквами, так как они перепутываются с языками L, M и т.п.) ## Мне кажется, первое определение — это по сути означает множество языков, представимое регулярными выражениями, думаю, надо это упомянуть. P.S. Более того, если я не ошибаюсь, кажется, вообще в конспектах нигде нет определения регулярных выражений, так что это определение по сути им является.## <tex>\bigcap\limits_{R - nadreg}</tex>, вот это nadreg выглядит совершенно мерзко, надо от него избавиться. Возможно, найти/придумать разумный английский термин и писать под объединением что-то вроде R is X, где X — это название, которое вы найдется или придумаете.# [[Детерминированные конечные автоматы]](2) </li>## Английские терминыОформить красиво табличку## Добавить ссылку на факт про эквивалентность автоматных Оформить подробней и регулярныхкрасивей способы представления## Англоязычные источники (хотя бы википедия)# <li> [[Прямое произведение ДКА]]</li></ol> === НКА ===## Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.<ol># ''fixed'' <li value="5"> [[Недетерминированные конечные автоматы]]</li>## Английские термины## Англоязычные источники (хотя бы википедия)## Написать, что класс языков совпадает с AUT, и почему (потому что алгоритм Томпсона)# <li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]</li># <li> [[Автоматы с eps-переходами. Eps-замыкание]]</li># ''fixed'' <li> [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]</li><li> '''fixed''' [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] (5) </li>## Опять классы языков курсивомНаписать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)## Внутренние ссылки Неплохо бы добавить ссылку на автоматные и регулярные языкиисточник доказательства# Исправить форматирование</ol> === Минимизация ДКА ===<ol><li value="10"> [[Эквивалентность состояний ДКА]] </li><li> ''fixed'' [[Замкнутость регулярных языков относительно различных операцийМинимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]](2) </li>#: см. 1Оформить таблички покрасивей и marked на что-нибудь заменить# Сделать О-красивое<li> ''fixed'' [[Анализ свойств регулярных языков Минимизация ДКА, алгоритм Хопкрофта (сложность O(пустота, совпадение, включение, конечность, подсчет числа словn log n))]](2.5) </li># Отформатировать комментарии и добавить их побольше# Оформить правильно декларации функций#Отформатировать по правилам<li> '''fixed''' [[Алгоритм Бржозовского]] (5) </li># Добавить доказательство</ol> === Свойства конечных автоматов ===<ol><texli value="14">paths'''fixed''' [[Доказательство нерегулярности языков: лемма о разрастании]] (6) </texli> выглядит мерзко# Ещё один пример нерегулярного языка, такие штуки надо оборачивать для которого выполнена лемма о разрастании (с википедии)# Доказательство леммы о накачке в какой-нибудь \mathrmобщем виде# Отформатировать по правилам<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> [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состоянийКвантовые конечные автоматы]]</li># [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]# <li> '''!!!fixed''' [[Контексты Автоматы Мура и синтаксические моноидыМили]](5) </li>## добавить английских терминов, ссылку Примеры интересных задач или применений на англоязычную викиэти автоматы (для согласования написать куратору)## доказательство последнего утверждения## вообще написать что-нибудь еще бы, типа зачем оно вообще надо, ну или хотя бы еще пару интересных примеров про синтактические моноиды каких-нибудь классов языков, например.</ol>

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

=== Разрешимые и перечислимые языки ===# ''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>