Изменения

Перейти к: навигация, поиск

Участник:Dgerasimov/Тикеты по конспектам year2011

1196 байт добавлено, 19:59, 5 ноября 2013
2. Контекстно-свободные грамматики
## побольше внутренних ссылок, на МП-автомат там, например
## проставить категории
# '''Взяли !!!''' [[Удаление бесполезных символов из грамматики]]
## запилить пример
## англоязычных терминов где можно
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
# [[Удаление eps-правил из грамматики]]
## запилить пример
## англоязычных терминов где можно
## если есть, ссылок на википедию.
## почти нет внутренних ссылок, надо бы добавить
## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. также
## асимптотики какие-нибудь нужны. Вроде для произвольной грамматики это сложно посчитать, но можно: 1. сослаться куда-нибудь на оценки асимптотики. 2. привести пример, на котором будет экспоненциальное время работы (вроде тут так можно) 3. написать, что обычно этот алгоритм запускается после удаления длинных правил, и там все полиномиально (сослаться на НФХ)
## для алгоритма поиска eps-порождающих точно можно асимптотику написать
# [[Удаление цепных правил из грамматики]]
# [[Удаление длинных правил из грамматики]]

Навигация