3622
правки
Изменения
м
→Опровержение контекстно-свободности языка
# Оформить таблички покрасивей и marked на что-нибудь заменить
# Сделать О-красивое
<li> ''fixed'' [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] (2.5) </li>
# Отформатировать комментарии и добавить их побольше
# Оформить правильно декларации функций
# Отформатировать по правилам
<li> '''fixed''' [[Алгоритм Бржозовского]] (5) </li>
# Добавить доказательство
<li> '''fixed''' [[Замкнутость регулярных языков относительно различных операций]] (6) </li>
# Добавить примеров различных языков (half, cycle, см. ХМУ) с доказательствами их регулярности
<li> '''взялиfixed''' [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] (5) </li>
# Добавить ещё свойств (проверка на тривиальность, равенство замыканию Клини, какие-нибудь ещё {{---}} для уточнения куратору написать)
# Оформить нормально источники информации
=== Другие автоматы ===
<ol>
<li value="20"> '''взялиfixed''' [[Локальные автоматы]] (5) </li>
# Где это нужно и зачем применяется
<li> [[Двусторонний детерминированный конечный автомат]] </li>
<ol>
<li value="16"> [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] </li>
<li> '''!!!взяли''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (710) </li>
# Расписать подробней и формальней
# А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать
# Добавить см. также на варианты леммы
# Категория
<li> '''!!!fixed''' [[Лемма Огдена]] (710) </li>
# Источники информации добавить
# Добавить пример не КС-языка, который удовлетворяет условию этой леммы
# ''fixed'' [[Перечислимые языки]] (2)
## Добавить содержательный пример коперечислимого языка
# ''fixed'' [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] (02.5)
## Убрать лишние знаки препинания из списков в теоремах
## Заменить литературу на источники информации
## Категории
## Отформатировать по правилам
# [[Вычислимые функции]]
# ''fixed'' [[Вычислимые числа]] (2)
## Подробней расписать доказательства
## Ссылки на леммы внутри конспекта
# '''взялиfixed''' [[Теорема о рекурсии]] (8)
## дать ссылки на английские источники и термины
## Неформальное пояснение к теореме
# названия функций надо в \mathrm
# Помёрджить с конспектом математической логики [[Рекурсивные функции, представимость в формальной арифметике]]
<li> ''взялиfixed'' [[Частично рекурсивные функции]] (2) </li>
# Замечание про взаимную рекурсию в обсуждениях
<li> [[Стековые машины, эквивалентность двухстековой машины МТ]] </li>
<li> [[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]] </li>
<li> [[Неразрешимость задачи об эквивалентности КС-грамматик]]</li>
<li> '''взялиfixed''' [[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]] (6) </li>
# Оформить правильно англоязычные термины
# Написать более подробное и понятное доказательство
<li> [[Игра «Жизнь»]] </li>
<li> [[Неразрешимость игры Braid]] </li>
<li> '''взялиfixed''' [[Теорема Райса-Шапиро]] (8) </li>
# Англоязычные термины
# Отформатировать псевдокоды
