Изменения

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

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

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

Навигация