Удаление бесполезных символов из грамматики

Определение:

Символ [math]A[/math] называется непорождающим, если из него не может быть выведена конечная терминальная цепочка.

Рассматривая правила грамматики, можно сделать вывод, что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде:

1. Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов.
2. Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части.
3. Если на шаге 2 список больше не пополняется, то получен список всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

Определение:

Символ [math]A[/math] называется недостижимым в КС-грамматике [math]\Gamma[/math], если строку, содержащую [math]A[/math], нельзя вывести из стартового нетерминала.

Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так:

1. Образовать одноэлементный список, состоящий из начального символа
2. Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части.
3. Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми.

Определение:

Символ [math]A[/math] называется бесполезным в КС-грамматике [math]\Gamma[/math], если он не может встретиться в выводе слова из терминалов.

Теорема:

Грамматика [math]\Gamma[/math] не содержит бесполезных символов тогда и только тогда, когда она не содержит ни недостижимых символов, ни непорождающих.

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math] Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными. [math]\Leftarrow[/math] Рассмотрим любой нетерминал [math]A[/math]. Так как он достижимый, существуют [math]\alpha[/math] и [math]\beta[/math], такие, что [math]S \Rightarrow ^* \alpha A \beta[/math]. Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует [math]\omega \in \Sigma ^ *[/math]: [math]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega[/math], и [math]A[/math] - не бесполезный.

[math]\triangleleft[/math]

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.