Удаление длинных правил из грамматики — различия между версиями
Grechko (обсуждение | вклад) |
Grechko (обсуждение | вклад) |
||
Строка 7: | Строка 7: | ||
}} | }} | ||
− | + | == Постановка задачи == | |
− | Пусть | + | Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил |
− | + | == Алгоритм == | |
− | Требуется | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Версия 22:33, 26 октября 2011
Задача удаления длинных правил из грамматики возникает при попытке ее приведения к нормальной форме Хомского.
Определение: |
Пусть контекстно-свободная грамматика. Правило называется длинным если | —
Постановка задачи
Пусть контекстно-свободная грамматика, содержащая длинные правила. Требуется построить эквивалентную грамматику , не содержащую длинных правил
—