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

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

Символ [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]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w[/math], где [math]w[/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]

Теорема:

Пусть [math]G[/math] — КС-грамматика, и [math]L(G)\ne\varnothing[/math]. Пусть [math]G_1[/math] - грамматика, полученная с помощью следующих двух шагов: 1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть [math]G_2[/math] — полученная в результате грамматика. 2) Удаляются все символы, недостижимые из [math]G_2[/math]. Тогда [math]G_1[/math] не имеет бесполезных символов и [math]L(G_1)=L(G)[/math].

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

[math]\triangleright[/math]

Пусть [math]X[/math] — оставшийся символ. Известно, что [math]X\Rightarrow _G^* w[/math] для некоторой цепочки [math]w[/math] из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому [math]S\Rightarrow _{G_2}^* w[/math]. Поскольку [math]X[/math] не был удален на втором шаге, известно, что существует такие [math]\alpha[/math] и [math]\beta[/math], для которых [math]S\Rightarrow _{G_2}^* \alpha X\beta[/math]. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому [math]S\Rightarrow _{G_1}^* \alpha X\beta[/math]. Также известно, что каждый символ в цепочке [math]\alpha X\beta[/math] достижим, поэтому каждый из них является порождающим в [math]G_2[/math]. Порождение некоторой терминальной цепочки, например, [math]\alpha X\beta\Rightarrow _{G_2}^* xwy[/math], содержит только символы, достижимые из [math]S[/math], поскольку они достижимы из символов в цепочке [math]\alpha X\beta[/math]. Таким образом, это порождение есть также порождение в [math]G_1[/math], то есть [math]S\Rightarrow _{G_1}^* \alpha X\beta\Rightarrow _{G_1}^* xwy[/math]. Итак, [math]X[/math] полезен в [math]G_1[/math]. Ввиду произвольности [math]X[/math] в [math]G_1[/math] можно заключить, что [math]G_1[/math] не имеет бесполезных символов. [math]L(G_1)\subseteq L(G)[/math], так как при построении [math]G_1[/math] из [math]G[/math] символы и продукции только убирались. Докажем, что [math]L(G_1)\supseteq L(G)[/math]. Если [math]w\in L(G)[/math], то [math]S\Rightarrow _{G}^* w[/math]. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в [math]G_1[/math] его также содержит. Таким образом, [math]S\Rightarrow _{G_1}^* w[/math], [math]w\in L(G_1)[/math] и [math]L(G)=L(G_1)[/math].

[math]\triangleleft[/math]

Примечание:

Эти шаги нельзя менять местами. Рассмотрим следующую грамматику:

[math]S\rightarrow AB|a[/math]

[math]A\rightarrow b[/math]

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

Литература

• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)