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

Порождающие и непорождающие нетерминалы

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

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

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

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

Лемма:

После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.

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

[math]\triangleright[/math]

Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.

[math]\triangleleft[/math]

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math], однако используя очередь можно ускорить его до [math]O(\left| \Gamma \right|)[/math].

Пример

Рассмотрим грамматику: [math] \begin{array}{l l} S\rightarrow Ac\\ A\rightarrow SD\\ D\rightarrow aD\\ A\rightarrow a \end{array} [/math]

1. Изначально множество порождающих нетерминалов состоит из одного элемента [math]A[/math].
2. Добавим в множество нетерминал [math]S[/math], так как существует правило [math]S\rightarrow Ac[/math], в правой части которого стоят нетерминал [math]A[/math], который есть в множестве, и терминал [math]c[/math].
3. После следующего обхода правил из грамматики множество не изменится.
4. Теперь удалим правила [math]A\rightarrow SD[/math] и [math]D\rightarrow aD[/math], так как они содержит нетерминалы, которых нет в полученном множестве.

Достижимые и недостижимые нетерминалы

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

Нетерминал [math]A[/math] называется достижимым (англ. reachable) в КС-грамматике [math]\Gamma[/math], если существует порождение [math]S \Rightarrow^* \alpha A \beta[/math]. Иначе он называется недостижимым (англ. unreachable).

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.

1. Возьмём множество, состоящее из единственного элемента: [math]\lbrace S \rbrace[/math].
2. Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
3. Если на шаге 2 множество изменилось, повторить шаг 2.
4. Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

Лемма:

После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.

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

[math]\triangleright[/math]

Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.

[math]\triangleleft[/math]

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math], однако используя обход в глубину можно ускорить его до [math]O(\left| \Gamma \right|)[/math].

Пример

Рассмотрим грамматику: [math] \begin{array}{l l} S\rightarrow AB|CD\\ A\rightarrow EF\\ G\rightarrow AD\\ C\rightarrow c \end{array} [/math]

1. Возьмём множество, состоящее из единственного элемента: [math]\lbrace S \rbrace[/math].
2. Из [math]S[/math] достижимы нетерминалы [math]A[/math], [math]B[/math], [math]C[/math] и [math]D[/math]. Добавим их в множество и получим [math]\lbrace S, A, B, C, D \rbrace[/math].
3. Множество изменилось. Переберём заново правила из грамматики. Из [math]A[/math] можно вывести [math]E[/math] и [math]F[/math], добавим их в множество.
4. Снова переберём правила. Из [math]C[/math] можно вывести только терминал, а [math]G[/math] нету в множестве.
5. После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: [math]\lbrace S, A, B, C, D, E, F \rbrace[/math].
6. Теперь удалим правило [math]G\rightarrow AD[/math], так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

Полезные и бесполезные нетерминалы

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

Нетерминал [math]A[/math] называется полезным (англ. useful) в КС-грамматике [math]\Gamma[/math], если он может участвовать в выводе, то есть существует порождение вида [math]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w[/math]. Иначе он называется бесполезным (англ. useless).

Теорема:

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

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

[math]\triangleright[/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]

Алгоритм удаления бесполезных нетерминалов

1. Удалить из грамматики правила, содержащие непорождающие нетерминалы.
2. Удалить из грамматики правила, содержащие недостижимые нетерминалы.

Корректность алгоритма

Достаточность данных действий следует из доказанной выше теоремы.

Докажем, что после выполнения второго шага не могут появиться новые непорождающие нетерминалы.

Допустим, что в грамматике появился непорождающий нетерминал [math]A[/math]. Так как до удаления недостижимых нетерминалов существовал вывод из [math]A[/math] некоторой конечной цепочки терминалов [math]\omega[/math], то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть [math]B\rightarrow\alpha[/math] — правило, первым из удалённых применяемое в выводе [math]A \Rightarrow ^* \omega[/math]. Оно могло быть удалено только в том случае, если в [math]\alpha[/math] присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то [math]B[/math] — достижим, следовательно достижимы и все нетерминалы из [math]\alpha[/math]. Значит, это правило не могло быть удалено.

Пример

Пусть нам дана грамматика: [math] \begin{array}{l l} S\rightarrow AS|BS|s \\ E\rightarrow EF|FF \\ A\rightarrow a \\ F\rightarrow f \end{array} [/math].
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику [math] \begin{array}{l l} S\rightarrow AS|s \\ E\rightarrow EF|FF \\ A\rightarrow a \\ F\rightarrow f \end{array} [/math].
Теперь удалим недостижимые нетерминалы и получим грамматику [math] \begin{array}{l l} S\rightarrow AS|s \\ A\rightarrow a \end{array} [/math].

Замечание

Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику: [math] \begin{array}{l l} S\rightarrow AB|a \\ A\rightarrow b \end{array}. [/math] Все нетерминалы в этой грамматике достижимы. Однако, если удалить [math]B[/math] как непорождающий, то нетерминал [math]A[/math] станет недостижимым.

См. также

• Контекстно-свободные грамматики
• Нормальная форма Хомского
• Chomsky normal form

Литература

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