Вклад участника
24 января 2012
Лемма о разрастании для КС-грамматик
Нет описания правки
мТеорема Райса-Шапиро
Тире
м+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
Интерпретация булевых формул с кванторами как игр для двух игроков
Интерпретация булевых формул с кванторами как игр для двух игроков
м-7
Интерпретация булевых формул с кванторами как игр для двух игроков
Фиксы в формулировках и русском языке
+182
Интерпретация булевых формул с кванторами как игр для двух игроков
ой, забыл))
м-41
Интерпретация булевых формул с кванторами как игр для двух игроков
Полностью переделано оформление + исправлено много чего в тексте
+348
Регулярные языки: два определения и их эквивалентность
Мелкие фиксы
м+12
5 января 2012
Обсуждение:Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
ToDo
Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
Нет описания правки
м
20 декабря 2011
19 декабря 2011
Обсуждение:Вычислимые функции
ToDo
Вычислимые функции
Нет описания правки
м+2
Обсуждение:Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
ToDoAndDoAndDo
Обсуждение:Перечислимые языки
ToDo
14 декабря 2011
9 декабря 2011
5 декабря 2011
26 ноября 2011
Обсуждение:Существенно неоднозначные языки
ToDo2
+953
Существенно неоднозначные языки
Нет описания правки
м+6