Вклад участника
15 апреля 2012
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Определение полного языка
+822
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил определение сложного языка
+570
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Нет описания правки
м+114
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил теорему о транзитивности
+1830
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил пример сведения
+2447
Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи
Добавил определение
4 апреля 2012
Теория сложности
Добавлены темы первой волны
+1356
Заглавная страница
Разделены старая и новая версия «теории сложности»
м+181
Теория сложности
Убран редирект
-112
Теория сложности
переименовал Теория сложности в Теория сложности (старая трешовая версия): Мы создаём свой конспект. Хороший, красивый и ясный.
Теория сложности (старая трешовая версия)
переименовал Теория сложности в Теория сложности (старая трешовая версия): Мы создаём свой конспект. Хороший, красивый и ясный.
м
24 января 2012
Автоматы с магазинной памятью
Недетерминированный автомат с магазинной памятью
м-1
Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
Идиотский баг
мНеукорачивающие и контекстно-зависимые грамматики, эквивалентность
Бысрый фикс
м+1
Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
Эквивалентность двухстековой машины трёхсчётчикой машине
м+44
Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
Эквивалентность двухстековой машины трёхсчётчикой машине
м+18
Лемма о разрастании для КС-грамматик
Лемма о разрастании для КС-грамматик
м+27
Лемма о разрастании для КС-грамматик
Нет описания правки
мТеорема Райса-Шапиро
Тире
м+10
Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
Некоторое пояснение
+165
23 января 2012
Лемма о разрастании для КС-грамматик
Нет описания правки
м-27
Лемма о разрастании для КС-грамматик
Идиотский фиск
м-2
Вычислимые функции
Мелкий фикс (всё-таки на питоноподобном языке пишем)
мВычислимые функции
«утверждение» → «лемма»
м-7
Удаление eps-правил из грамматики
Алгоритм удаления ε-правил из грамматики
м+2
Удаление eps-правил из грамматики
Доказательство корректности
м+34
Удаление eps-правил из грамматики
Алгоритм удаления ε-правил из грамматики
м-2
Удаление eps-правил из грамматики
Алгоритм удаления ε-правил из грамматики
м-2
Удаление бесполезных символов из грамматики
Фикс русского
м+23
Удаление бесполезных символов из грамматики
«т.к.» → «так как»
м+6
Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
Фикс
м+40
Иерархия Хомского формальных грамматик
Доубирал нелепое слово «те»
м-15
Иерархия Хомского формальных грамматик
Класс 2
м-5
21 января 2012
Автоматы с eps-переходами. Eps-замыкание
Эквивалентность автоматов с переходами по строкам и НКА. Eps-замыкание
м-151
Автоматы с eps-переходами. Eps-замыкание
«Определение» эквивалентности
м+306
Существенно неоднозначные языки
И снова русский язык
м+6
Существенно неоднозначные языки
Фикс русского
м+11
Интерпретация булевых формул с кванторами как игр для двух игроков
Быстрое исправление тупой баги
м-2
Интерпретация булевых формул с кванторами как игр для двух игроков
Убрано много-премного бреееееда
+391
Регулярные языки: два определения и их эквивалентность
Переработка первой части доказательства (суровая такая)
+644
Регулярные языки: два определения и их эквивалентность
Пофикшены определения
+167
17 января 2012
Регулярные языки: два определения и их эквивалентность
Изменение форматирования
м+6
Доказательство нерегулярности языков: лемма о разрастании
Нет описания правки
м+19
Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчёт числа слов)
Алгоритм проверки на включение
м-2
Эквивалентность состояний ДКА
Нет описания правки
м+31
Автоматы с eps-переходами. Eps-замыкание
Совпадение множеств языков, допускаемых eps-НКА и ДКА
м+108
Автоматы с eps-переходами. Eps-замыкание
Совпадение множеств языков, допускаемых eps-НКА и ДКА
м+54
Построение по НКА эквивалентного ДКА, алгоритм Томпсона
Добавил ссылочки на ДКА и НКА
м+150
Недетерминированные конечные автоматы
Пропущенная запятая
м+1
Интерпретация булевых формул с кванторами как игр для двух игроков
Переформулировка теоремы. Теперь она, кажется, нормальная
+162
