Изменения

=== Регулярные языки и ДКА ===

<ol>

<li> [[Прямое произведение ДКА]] </li>

</ol>

<li value="5"> [[Недетерминированные конечные автоматы]] </li>

<li> [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] </li>

# Написать, почему получение регулярного выражение из системы уравнений лучше, чем напрямую из теоремы Клини (привести пример)

# Неплохо бы добавить ссылку на источник доказательства

</ol>

<ol>

<li value="10"> [[Эквивалентность состояний ДКА]] </li>

# Добавить доказательство

</ol>

=== Свойства конечных автоматов ===

<ol>

# Ещё один пример нерегулярного языка, для которого выполнена лемма о разрастании (с википедии)

# Доказательство леммы о накачке в общем виде

* Вообще левая штука, относящаяся скорее к логике. Наверное, надо вообще выпилить это из списка конспектов по автоматам и сделать ссылку из леммы о накачке (оно для нее, видимо, и рассказывалось). Итого, придумать, куда выпилить, и сделать интервики из прошлого конспекта

<li> [[Решение уравнений в регулярных выражениях]] </li>

# Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности

# Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)

# Оформить нормально источники информации

# Исправить багу с примечаниями

# Англоязычные термины

</ol>

=== Другие автоматы ===

<ol>

# Где это нужно и зачем применяется

<li> [[Двусторонний детерминированный конечный автомат]] </li>

<li> [[Квантовые конечные автоматы]] </li>

# Примеры интересных задач или применений на эти автоматы (для согласования написать куратору)

</ol>

=== Базовые понятия о грамматиках ===

<ol>

# Пояснить пример контекстно-зависимой грамматики

# Можно ещё примеров различных интересных грамматик добавить (и добавить ссылку на грамматики языков программирования)

# Почистить обсуждения

<li> [[Иерархия Хомского формальных грамматик]] </li>

<li> [[Правоконтекстные грамматики, эквивалентность автоматам]] </li>

# Пропущен - в КС-языках

# Точку в конкатенации лучше опустить

# Добавить примеры других грамматик

# Добавить ссылок, см. также

# Добавить док-во леммы

# Отформатировать псевдокод

=== Нормальные формы КС-грамматик ===

<ol>

# Англоязычных термины нормально оформить

# Добавить ссылок

# Категория

<li> [[Удаление длинных правил из грамматики]] </li>

# написать, для чего она нужна

# Какая асимптотика алгоритма приведения?

# Отформатировать псевдокод

# Добавить алгоритм приведения к сильной нормальной форме Грейбах (или хотя бы сказать как-нибудь подробней про неё)

</ol>

=== Алгоритмы разбора ===

<ol>

# Расписать подробней и формальней

# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать

# И желательно расписать динамики через полуинтервалы, а не отрезки

# Красиво всё оформить

# Отформатировать псевдокод

# Грамматику G заменить на \Gamma

=== Опровержение контекстно-свободности языка ===

<ol>

# Добавить пример не КС-языка, который удовлетворяют условию леммы, но уже не удовлетворяет условию леммы Огдена

# Источники нормально оформить

# Добавить см. также на варианты леммы

# Категория

# Источники информации добавить

# Категория

</ol>

=== МП-автоматы ===

<ol>

# Картинки увеличить

# Определение жирным

# Источники информации, См. также

# Категория

# В пример добавить язык автомата

# Англоязычные термины

# Категория

# Категория

# Палку заменить на \mid

# Источники информации

# Написать!

<li> [[ДМП-автоматы и неоднозначность]] </li>

</ol>

=== Разрешимые и перечислимые языки ===

## Заменить литературу на источники информации

# [[Вычислимые функции]]

## Правильно оформить англоязычные термины

## Пояснить a(eps) в определении

## Ссылки заменить на источники информации

## Увеличить дроби

## Англоязычные термины правильно оформить

## Оформить правильно источники информации

## Заменить дефисы на тире

## английские источиники и термины

## ссылки на вики

## Подробней расписать доказательства

## Ссылки на леммы внутри конспекта

## дать ссылки на английские источники и термины

## Неформальное пояснение к теореме

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

## следующая теорема о рекурсии (которая на самом деле называется теоремой о неподвижной точке) во-первых, списана из Шеня, во-вторых, списана неправильно и непонятно. Соответственно, пофиксить.

# [[Busy beaver]]

=== Вычислительные формализмы ===

<ol>

# названия функций надо в \mathrm

# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]

<li> [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] </li>

<li> [[Линейный клеточный автомат, эквивалентность МТ]] </li>

<li> [[Возможность порождения формальной грамматикой произвольного перечислимого языка]] </li>

</ol>

=== Примеры неразрешимых задач ===

<ol>

# Англоязычные термины правильно оформить

# Добавить примеры m-сведения задач

# Ссылку на ПСП оформить правильно

# Переменные и константы взять в Tex

<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>

# Оформить правильно англоязычные термины

# Написать более подробное и понятное доказательство

# Добавить категории

# Добавить см. также

<li> [[Неразрешимость исчисления предикатов первого порядка]] </li>

# написать. Тут все не написать, но хотелось бы какой-нибудь скетч доказательства с выделением основных технических моментов, примерами диофантовых множеств, всякими трюками, с ними связанными.

# Англоязычные термины

# Отформатировать псевдокоды