Участник:Shersh/Тикеты к 5ому терму — различия между версиями
Shersh (обсуждение | вклад) (→Разрешимые и перечислимые языки) |
Shersh (обсуждение | вклад) м (→Опровержение контекстно-свободности языка) |
||
| (не показано 158 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе | Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе | ||
| − | + | ||
== 1. Автоматы и регулярные языки == | == 1. Автоматы и регулярные языки == | ||
| − | + | === Регулярные языки и ДКА === | |
| − | + | <ol> | |
| − | + | <li value="1"> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]] </li> | |
| − | + | <li> [[Регулярные языки: два определения и их эквивалентность]] </li> | |
| − | # | + | <li> ''fixed'' [[Детерминированные конечные автоматы]] (2) </li> |
| − | # | + | # Оформить красиво табличку |
| − | + | # Оформить подробней и красивей способы представления | |
| − | + | <li> [[Прямое произведение ДКА]] </li> | |
| − | + | </ol> | |
| − | + | ||
| − | + | === НКА === | |
| − | + | <ol> | |
| − | + | <li value="5"> [[Недетерминированные конечные автоматы]] </li> | |
| − | + | <li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li> | |
| − | + | <li> [[Автоматы с eps-переходами. Eps-замыкание]] </li> | |
| − | + | <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> |
| − | # '''fixed''' [[ | + | # Добавить примеров различных языков (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. Контекстно-свободные грамматики == | == 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''' [[Лемма Огдена]] (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> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]] | ||
| − | # ''' | ||
| − | |||
| − | |||
| − | |||
| − | |||
== 3. Теория вычислимости == | == 3. Теория вычислимости == | ||
=== Разрешимые и перечислимые языки === | === Разрешимые и перечислимые языки === | ||
| − | # | + | # [[Разрешимые (рекурсивные) языки]] |
| − | + | # ''fixed'' [[Перечислимые языки]] (2) | |
| − | + | ## Добавить содержательный пример коперечислимого языка | |
| − | + | # ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] (2.5) | |
| − | + | ## Убрать лишние знаки препинания из списков в теоремах | |
| − | |||
| − | |||
| − | |||
| − | # '' | ||
| − | ## | ||
| − | |||
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | ## | ||
## Заменить литературу на источники информации | ## Заменить литературу на источники информации | ||
| + | ## Категории | ||
| + | ## Отформатировать по правилам | ||
# [[Вычислимые функции]] | # [[Вычислимые функции]] | ||
| − | # | + | # ''fixed'' [[Вычислимые числа]] (2) |
| − | |||
| − | |||
| − | |||
## Правильно оформить англоязычные термины | ## Правильно оформить англоязычные термины | ||
## Пояснить a(eps) в определении | ## Пояснить a(eps) в определении | ||
| Строка 240: | Строка 213: | ||
## Ссылки заменить на источники информации | ## Ссылки заменить на источники информации | ||
## Увеличить дроби | ## Увеличить дроби | ||
| − | # [[Универсальная функция]] | + | ## Пояснить подробней мутные места |
| + | # ''fixed'' [[Универсальная функция]] (1) | ||
## Англоязычные термины правильно оформить | ## Англоязычные термины правильно оформить | ||
## Оформить правильно источники информации | ## Оформить правильно источники информации | ||
## Заменить дефисы на тире | ## Заменить дефисы на тире | ||
| − | # '' | + | ## Пояснить нотацию про U(n, x) и U_n(x) |
| − | ## | + | ## Заголовки внутри конспекта поправить |
| − | + | # ''fixed'' [[Свойства перечислимых языков. Теорема Успенского-Райса]] (1) | |
| − | + | ## Почему языком L_g(i,x) будет X? Как i связано с X? | |
| − | + | ## И вообще доказательство можно сделать чуть менее мутным :) | |
| − | + | # [[Неотделимые множества]] | |
| − | ## | + | # '''fixed''' [[Иммунные и простые множества]] (7) |
| − | # | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | # ''' | ||
## английские источиники и термины | ## английские источиники и термины | ||
## ссылки на вики | ## ссылки на вики | ||
| Строка 266: | Строка 232: | ||
## Подробней расписать доказательства | ## Подробней расписать доказательства | ||
## Ссылки на леммы внутри конспекта | ## Ссылки на леммы внутри конспекта | ||
| − | # ''' | + | # '''fixed''' [[Теорема о рекурсии]] (8) |
## дать ссылки на английские источники и термины | ## дать ссылки на английские источники и термины | ||
## Неформальное пояснение к теореме | ## Неформальное пояснение к теореме | ||
## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод | ## у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод | ||
## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить. | ## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить. | ||
| + | # [[Квайны]] | ||
# [[Busy beaver]] | # [[Busy beaver]] | ||
| − | # | + | # [[Колмогоровская сложность]] |
| − | |||
| − | |||
=== Вычислительные формализмы === | === Вычислительные формализмы === | ||
<ol> | <ol> | ||
| − | <li value=" | + | <li value="14">[[Машина Тьюринга]] </li> |
| − | + | <li> [[Лямбда-исчисление]]</li> | |
| − | + | <li> '''fixed''' [[Примитивно рекурсивные функции]] (10) </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> ''' | ||
# названия функций надо в \mathrm | # названия функций надо в \mathrm | ||
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]] | # Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]] | ||
| − | <li> '' | + | <li> ''fixed'' [[Частично рекурсивные функции]] (2) </li> |
| − | # | + | # Замечание про взаимную рекурсию в обсуждениях |
| − | + | <li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | <li> [[Стековые машины, эквивалентность двухстековой машины МТ]]</li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li> | <li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li> | ||
| − | |||
| − | |||
<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li> | <li> [[Линейный клеточный автомат, эквивалентность МТ]] </li> | ||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li> | <li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li> | ||
| − | + | <li> [[Линейный ограниченный автомат]]</li> | |
| − | + | <li> [[Сверхтьюринговые вычисления (гипервычисления)]]</li> | |
| − | |||
</ol> | </ol> | ||
=== Примеры неразрешимых задач === | === Примеры неразрешимых задач === | ||
<ol> | <ol> | ||
| − | <li value=" | + | <li value="24"> ''fixed'' [[m-сводимость]] (3) </li> |
# Англоязычные термины правильно оформить | # Англоязычные термины правильно оформить | ||
# Добавить примеры m-сведения задач | # Добавить примеры m-сведения задач | ||
| Строка 348: | Строка 267: | ||
# Ссылку на ПСП оформить правильно | # Ссылку на ПСП оформить правильно | ||
# Переменные и константы взять в Tex | # Переменные и константы взять в Tex | ||
| − | <li> | + | <li> [[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]] </li> |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li> | <li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li> | ||
| − | + | <li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li> | |
| − | + | <li> '''fixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li> | |
| − | <li> [[ | ||
| − | |||
| − | <li> ''' | ||
# Оформить правильно англоязычные термины | # Оформить правильно англоязычные термины | ||
# Написать более подробное и понятное доказательство | # Написать более подробное и понятное доказательство | ||
| Строка 370: | Строка 276: | ||
# Добавить категории | # Добавить категории | ||
# Добавить см. также | # Добавить см. также | ||
| − | <li> | + | <li> [[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]] </li> |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<li> [[Неразрешимость исчисления предикатов первого порядка]] </li> | <li> [[Неразрешимость исчисления предикатов первого порядка]] </li> | ||
| − | + | <li> '''взяли''' [[Неразрешимость проблемы существования решения диофантова уравления в целых числах]] (10) </li> | |
| − | |||
| − | <li> ''' | ||
# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными. | # написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными. | ||
| − | <li> ''' | + | <li> [[Игра «Жизнь»]] </li> |
| + | <li> [[Неразрешимость игры Braid]] </li> | ||
| + | <li> '''fixed''' [[Теорема Райса-Шапиро]] (8) </li> | ||
# Англоязычные термины | # Англоязычные термины | ||
# Отформатировать псевдокоды | # Отформатировать псевдокоды | ||
Текущая версия на 20:16, 18 января 2017
Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе
Содержание
1. Автоматы и регулярные языки
Регулярные языки и ДКА
- Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
- Регулярные языки: два определения и их эквивалентность
- fixed Детерминированные конечные автоматы (2)
- Оформить красиво табличку
- Оформить подробней и красивей способы представления
- Прямое произведение ДКА
НКА
- Недетерминированные конечные автоматы
- Построение по НКА эквивалентного ДКА, алгоритм Томпсона
- Автоматы с eps-переходами. Eps-замыкание
- Теорема Клини (совпадение классов автоматных и регулярных языков)
- fixed Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях) (5)
- Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)
- Неплохо бы добавить ссылку на источник доказательства
- Исправить форматирование
Минимизация ДКА
- Эквивалентность состояний ДКА
- fixed Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний (2)
- Оформить таблички покрасивей и marked на что-нибудь заменить
- Сделать О-красивое
- fixed Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) (2.5)
- Отформатировать комментарии и добавить их побольше
- Оформить правильно декларации функций
- Отформатировать по правилам
- fixed Алгоритм Бржозовского (5)
- Добавить доказательство
Свойства конечных автоматов
- fixed Доказательство нерегулярности языков: лемма о разрастании (6)
- Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)
- Доказательство леммы о накачке в общем виде
- Отформатировать по правилам
- fixed Интерпретация булевых формул с кванторами как игр для двух игроков (1)
- Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта
- Решение уравнений в регулярных выражениях
- fixed Замкнутость регулярных языков относительно различных операций (6)
- Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
- fixed Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов) (5)
- Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё — для уточнения куратору написать)
- Оформить нормально источники информации
- Исправить багу с примечаниями
- Англоязычные термины
- fixed Контексты и синтаксические моноиды (1)
- Оформить примеры красиво
- Оформить красиво двусторонние доказательства
- Отформатировать по правилам
Другие автоматы
- fixed Локальные автоматы (5)
- Где это нужно и зачем применяется
- Двусторонний детерминированный конечный автомат
- Квантовые конечные автоматы
- fixed Автоматы Мура и Мили (5)
- Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)
2. Контекстно-свободные грамматики
Базовые понятия о грамматиках
- fixed Формальные грамматики (5)
- Пояснить пример контекстно-зависимой грамматики
- Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)
- Заменить многоточия на \ldots
- Оформить правильно источники инфрмации, добавить См. также
- Категория
- Выделить в разборах жирным часть правила, которая раскрывается на данном шаге
- Примеры обозначений
- Вертикальную черту заменить на \mid
- В определениях скобки в Tex
- Интервики на рефлексивно-транзитивное замыкание
- Убрать ; из определения
- Выводы в примерах оформить красивей
- Почистить обсуждения
- Иерархия Хомского формальных грамматик
- Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
- Правоконтекстные грамматики, эквивалентность автоматам
- fixed Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора (1)
- Оформить красиво двусторонние доказательства и исправить форматирование в остальном. +баллы за более красивые картинки
- fixed Замкнутость КС-языков относительно различных операций (5)
- Пропущен - в КС-языках
- Точку в конкатенации лучше опустить
- Half некрасивый, c маленькой буквы его
- Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half
- Добавить примеры других грамматик
- Добавить ссылок, см. также
- fixed Регулярная аппроксимация КС-языков (7)
- Добавить док-во леммы
- Отформатировать псевдокод
- Tex правильно оформить
- Описание перед псевдокодом перенести
- Картинки убого расположены
- "свободно-контекстной грамматики" — и далее встречаются баги в конспекте
- Расшифровать RTN (то же с MT)
- Источники информации нормально оформить
- См. обсуждения
Нормальные формы КС-грамматик
- fixed Удаление бесполезных символов из грамматики (6)
- Англоязычных термины нормально оформить
- Добавить ссылок
- Добавить интервики
- Грамматики оформлены криво
- Написать, что такое
- Написать, откуда берутся такие асимптотики, и как добавить очередь
- Аналогично про обход в глубину
- Ссылку на НФХ перенести в источники информации
- Алгоритмы оформить отдельным подзаголовком
- Категория
- Удаление длинных правил из грамматики
- Удаление eps-правил из грамматики
- Удаление цепных правил из грамматики
- Нормальная форма Хомского
- Устранение левой рекурсии
- fixed Приведение грамматики к ослабленной нормальной форме Грейбах (8)
- написать, для чего она нужна
- Какая асимптотика алгоритма приведения?
- Добавить источники информации
- Добавить примеры
- Англоязычные термины нормально оформить
- Отформатировать псевдокод
- Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)
- Нормальная форма Куроды
Алгоритмы разбора
- Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
- взяли Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики (10)
- Расписать подробней и формальней
- А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
- И желательно расписать динамики через полуинтервалы, а не отрезки
- Красиво всё оформить
- Алгоритм Эрли
- fixed Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики (5)
- Отформатировать псевдокод
- Грамматику G заменить на \Gamma
- Перенести описание алгоритма перед псевдокодом
- Хотелось бы адекватные доказательства читать (см. обсуждения)
Опровержение контекстно-свободности языка
- fixed Лемма о разрастании для КС-грамматик (6)
- Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена
- Источники нормально оформить
- Добавить см. также на варианты леммы
- Категория
- fixed Лемма Огдена (10)
- Источники информации добавить
- Добавить пример не КС-языка, который удовлетворяет условию этой леммы
- Категория
- Существенно неоднозначные языки
МП-автоматы
- fixed Автоматы с магазинной памятью (0.5)
- Картинки увеличить
- Определение жирным
- ; в определении заменить на ,
- Англоязычные термины правильно оформить, убрать дублирования
- Источники информации, См. также
- Категория
- МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
- Совпадение множества языков МП-автоматов и контекстно-свободных языков
- fixed Детерминированные автоматы с магазинной памятью (0.5)
- В пример добавить язык автомата
- Англоязычные термины
- Категория
- fixed Детерминированные автоматы с магазинной памятью, допуск по пустому стеку (0.5)
- Категория
- Палку заменить на \mid
- Источники информации
- взяли Нормальная форма ДМП-автомата (10)
- Написать!
- Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
- ДМП-автоматы и неоднозначность
3. Теория вычислимости
Разрешимые и перечислимые языки
- Разрешимые (рекурсивные) языки
- fixed Перечислимые языки (2)
- Добавить содержательный пример коперечислимого языка
- fixed Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций (2.5)
- Убрать лишние знаки препинания из списков в теоремах
- Заменить литературу на источники информации
- Категории
- Отформатировать по правилам
- Вычислимые функции
- fixed Вычислимые числа (2)
- Правильно оформить англоязычные термины
- Пояснить a(eps) в определении
- Единообразно оформить множество рациональных чисел
- Все переменные и константы занести в Tex
- Ссылки заменить на источники информации
- Увеличить дроби
- Пояснить подробней мутные места
- fixed Универсальная функция (1)
- Англоязычные термины правильно оформить
- Оформить правильно источники информации
- Заменить дефисы на тире
- Пояснить нотацию про U(n, x) и U_n(x)
- Заголовки внутри конспекта поправить
- fixed Свойства перечислимых языков. Теорема Успенского-Райса (1)
- Почему языком L_g(i,x) будет X? Как i связано с X?
- И вообще доказательство можно сделать чуть менее мутным :)
- Неотделимые множества
- fixed Иммунные и простые множества (7)
- английские источиники и термины
- ссылки на вики
- а зачем оно нужно?
- Интервики
- Добавить категории
- Подробней расписать доказательства
- Ссылки на леммы внутри конспекта
- fixed Теорема о рекурсии (8)
- дать ссылки на английские источники и термины
- Неформальное пояснение к теореме
- у меня такое ощущение, что эта версия программы, использующей свой код неправильно будет работать когда мы попытаемся что-нибудь экранировать. Надо либо показать, где мы экранируем, либо написать версию, которая была на паре (с символом $). Да, надо написать версию с $, чтобы показать, что getOtherSrc можно написать в любом месте программы, а не только в конце. А ешё надо отрефакторить псевдокод
- следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.
- Квайны
- Busy beaver
- Колмогоровская сложность
Вычислительные формализмы
- Машина Тьюринга
- Лямбда-исчисление
- fixed Примитивно рекурсивные функции (10)
- названия функций надо в \mathrm
- Помёрджить с конспектом математической логики Рекурсивные функции, представимость в формальной арифметике
- fixed Частично рекурсивные функции (2)
- Замечание про взаимную рекурсию в обсуждениях
- Стековые машины, эквивалентность двухстековой машины МТ
- Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
- Линейный клеточный автомат, эквивалентность МТ
- Возможность порождения формальной грамматикой произвольного перечислимого языка
- Линейный ограниченный автомат
- Сверхтьюринговые вычисления (гипервычисления)
Примеры неразрешимых задач
- fixed m-сводимость (3)
- Англоязычные термины правильно оформить
- Добавить примеры m-сведения задач
- Заменить знаки неравенств
- Добавить категории
- Ссылку на ПСП оформить правильно
- Переменные и константы взять в Tex
- Проблема соответствий Поста
- Однозначность КС-грамматики
- Неразрешимость задачи об эквивалентности КС-грамматик
- fixed Задача о замощении полимино (6)
- Оформить правильно англоязычные термины
- Написать более подробное и понятное доказательство
- Заменить ссылки на источники информации
- Добавить категории
- Добавить см. также
- Задача о выводе в полусистеме Туэ
- Неразрешимость исчисления предикатов первого порядка
- взяли Неразрешимость проблемы существования решения диофантова уравления в целых числах (10)
- написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.
- Игра «Жизнь»
- Неразрешимость игры Braid
- fixed Теорема Райса-Шапиро (8)
- Англоязычные термины
- Отформатировать псевдокоды
- Дать более формальное и понятное определение образца
- Разбить доказательство на две части, чтобы это было видно
- Написать строгую формулировку теоремы
- "следующим образом: для проверяемого элемента y подготовим программу g:" — плохо смотрится лишнее двоеточие
- Лучше явно написать разрешитель для K
- "Полуразрешитель для множества образцов, удовлетворяющих \Gamma" можно написать понятней
- Добавить категории, см. также
- Заменить литературу на источники информации
