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

Материал из Викиконспекты
Версия от 04:58, 9 ноября 2011; Байдаров Андрей (обсуждение | вклад) (Полезные и бесполезные нетерминалы)
Перейти к: навигация, поиск

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

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


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

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


Лемма:
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
Доказательство:
[math]\triangleright[/math]
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
[math]\triangleleft[/math]

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

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


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

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


Лемма:
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
Доказательство:
[math]\triangleright[/math]
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
[math]\triangleleft[/math]


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

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


Теорема:
Грамматика [math]\Gamma[/math] не содержит бесполезных нетерминалов [math]\Leftrightarrow[/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]\triangleright[/math]

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

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

Допустим, что в грамматике появился непорождающий нетерминал [math]A[/math]. Так как до удаления недостижимых нетерминалов существовал вывод из [math]A[/math] конечной цепочки терминалов, то было удалено хотя бы какое-то одно правило из этого вывода. Возьмем первое удалённое правило [math]B\rightarrow\alpha[/math]. Оно могло быть удалено только в том случае, если в [math]\alpha[/math] присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то [math]B[/math] — достижим, следовательно достижимы и все нетерминалы из [math]\alpha[/math]. Значит, это правило не могло быть удалено.
[math]\triangleleft[/math]

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

Литература

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