Изменения

Тикеты индексируются как "X-Y", где X — номер раздела, а Y — номер конспекта в разделе

== 1. Автоматы и регулярные языки ==

## Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их [[Замкнутость регулярных языков относительно различных операций|отсюда]], оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать

## В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.

# [[Прямое произведение ДКА]]

## Вообще зачем такой короткий конспект нужен, не знаю, надо придумать, куда его запихать.

## Английские термины

## Англоязычные источники (хотя бы википедия)

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

# [[Автоматы с eps-переходами. Eps-замыкание]]

## Опять классы языков курсивом

## Внутренние ссылки на автоматные и регулярные языки

# [[Замкнутость регулярных языков относительно различных операций]]

#: см. 1

## <tex>paths</tex> выглядит мерзко, такие штуки надо оборачивать в какой-нибудь \mathrm

# [[Интерпретация булевых формул с кванторами как игр для двух игроков]]

## добавить ссылок на англоязычные источники, добавить в статью англоязычные термины

# [[Решение уравнений в регулярных выражениях]]

#: фиг знает что это, но надо написать, видимо

# [[Эквивалентность состояний ДКА]]

# [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]

# [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]

## доказательство последнего утверждения

== 2. Контекстно-свободные грамматики ==

## примеры неинтересные, хотя бы какую-нибудь контекстно-зависимую грамматику надо. Станкевич рассказывал клевый пример с грамматикой 0^n 1^n 2^n, вот его надо запилить

## определение выводимости за 0 или более шагов немного неправильное, надо бы потребовать, чтобы альфа было равно первому гамма, а бета — последнему гамма. Ну и написать что это рефлексивно-транзитивное замыкание.

## Источник бесполезен без конкретного указания, где искать

## Внутреннюю ссылку на ДКА

## нормально оформить уже существующий источник

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

## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>) и в выводе (надо <tex>\Rightarrow</tex>)

## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.

## Че за --? Заменить на —

## Half некрасивый, в \mathrm его

## побольше внутренних ссылок, на МП-автомат там, например

## проставить категории

# [[Устранение левой рекурсии]]

# [[Приведение грамматики к ослабленной нормальной форме Грейбах]]

# [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]

# [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]

# [[Лемма о разрастании для КС-грамматик]]

# [[Лемма Огдена]]

# [[Автоматы с магазинной памятью]]

# [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]

# [[Детерминированные автоматы с магазинной памятью]]

# [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]

# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]