Нормальная форма Хомского — различия между версиями
| Строка 1: | Строка 1: | ||
| − | Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex>\Gamma</tex>, из которой удалены [[Удаление бесполезных символов из грамматики|бесполезные символы]], [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]]. | + | Рассмотрим [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободную грамматику]] <tex>\Gamma</tex>, из которой удалены [[Удаление бесполезных символов из грамматики|бесполезные символы]], [[Удаление eps-правил из грамматики|<tex>\varepsilon</tex>-правила]], [[Удаление длинных правил из грамматики|длинные правила]] и [[Удаление цепных правил из грамматики|цепные правила]]. Такая грамматика содержит только правила следующего вида: |
| + | *<tex>A \rightarrow BC</tex> | ||
| + | *<tex>A \rightarrow Bc</tex> | ||
| + | *<tex>A \rightarrow bc</tex> | ||
| + | *<tex>A \rightarrow a</tex> | ||
| + | *<tex>S \rightarrow \varepsilon</tex> (при условии, что <tex>S</tex> не содержится в правых частях правил) | ||
Версия 20:09, 11 октября 2010
Рассмотрим контекстно-свободную грамматику , из которой удалены бесполезные символы, -правила, длинные правила и цепные правила. Такая грамматика содержит только правила следующего вида:
- (при условии, что не содержится в правых частях правил)
