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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 40: Строка 40:
 
|id=th2
 
|id=th2
 
|statement=
 
|statement=
Пусть <tex>G</tex> {{---}} КС-грамматика, и <tex>L(G)\ne\varnothing</tex>. Пусть <tex>G_1</tex> - грамматика, полученная с помощью следующих двух шагов:
+
Пусть <tex>\Gamma</tex> {{---}} КС-грамматика, и <tex>L(\Gamma)\ne\varnothing</tex>. Пусть <tex>\Gamma_1</tex> - грамматика, полученная с помощью следующих двух шагов:
  
1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть <tex>G_2</tex> {{---}} полученная в результате грамматика.
+
1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть <tex>\Gamma_2</tex> {{---}} полученная в результате грамматика.
  
2) Удаляются все символы, недостижимые из <tex>G_2</tex>.
+
2) Удаляются все символы, недостижимые из <tex>\Gamma_2</tex>.
  
Тогда <tex>G_1</tex> не имеет бесполезных символов и <tex>L(G_1)=L(G)</tex>.
+
Тогда <tex>\Gamma_1</tex> не имеет бесполезных символов и <tex>L(\Gamma_1)=L(\Gamma)</tex>.
 
|proof=
 
|proof=
Пусть <tex>X</tex> {{---}} оставшийся символ. Известно, что <tex>X\Rightarrow _G^* w</tex> для некоторой цепочки <tex>w</tex> из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\Rightarrow _{G_2}^* w</tex>.
+
Пусть <tex>X</tex> {{---}} оставшийся символ. Известно, что <tex>X\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex> для некоторой цепочки <tex>w</tex> из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\overset{*}{\underset{\Gamma_2}{\Rightarrow}}w</tex>.
  
Поскольку <tex>X</tex> не был удален на втором шаге, известно, что существует такие <tex>\alpha</tex> и <tex>\beta</tex>, для которых <tex>S\Rightarrow _{G_2}^* \alpha X\beta</tex>. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\Rightarrow _{G_1}^* \alpha X\beta</tex>.
+
Поскольку <tex>X</tex> не был удален на втором шаге, известно, что существует такие <tex>\alpha</tex> и <tex>\beta</tex>, для которых <tex>S\overset{*}{\underset{\Gamma_2}{\Rightarrow}} \alpha X\beta</tex>. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} \alpha X\beta</tex>.
  
Также известно, что каждый символ в цепочке <tex>\alpha X\beta</tex> достижим, поэтому каждый из них является порождающим в <tex>G_2</tex>. Порождение некоторой терминальной цепочки, например, <tex>\alpha X\beta\Rightarrow _{G_2}^* xwy</tex>, содержит только символы, достижимые из <tex>S</tex>, поскольку они достижимы из символов в цепочке <tex>\alpha X\beta</tex>. Таким образом, это порождение есть также порождение в <tex>G_1</tex>, то есть <tex>S\Rightarrow _{G_1}^* \alpha X\beta\Rightarrow _{G_1}^* xwy</tex>.
+
Также известно, что каждый символ в цепочке <tex>\alpha X\beta</tex> достижим, поэтому каждый из них является порождающим в <tex>\Gamma_2</tex>. Порождение некоторой терминальной цепочки, например, <tex>\alpha X\beta\overset{*}{\underset{\Gamma_2}{\Rightarrow}} xwy</tex>, содержит только символы, достижимые из <tex>S</tex>, поскольку они достижимы из символов в цепочке <tex>\alpha X\beta</tex>. Таким образом, это порождение есть также порождение в <tex>\Gamma_1</tex>, то есть <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} \alpha X\beta\overset{*}{\underset{\Gamma_1}{\Rightarrow}} xwy</tex>.
  
Итак, <tex>X</tex> полезен в <tex>G_1</tex>. Ввиду произвольности <tex>X</tex> в <tex>G_1</tex> можно заключить, что <tex>G_1</tex> не имеет бесполезных символов.
+
Итак, <tex>X</tex> полезен в <tex>\Gamma_1</tex>. Ввиду произвольности <tex>X</tex> в <tex>\Gamma_1</tex> можно заключить, что <tex>\Gamma_1</tex> не имеет бесполезных символов.
  
<tex>L(G_1)\subseteq L(G)</tex>, так как при построении <tex>G_1</tex> из <tex>G</tex> символы и продукции только убирались. Докажем, что <tex>L(G_1)\supseteq L(G)</tex>. Если <tex>w\in L(G)</tex>, то <tex>S\Rightarrow _{G}^* w</tex>. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в <tex>G_1</tex> его также содержит. Таким образом, <tex>S\Rightarrow _{G_1}^* w</tex>, <tex>w\in L(G_1)</tex> и <tex>L(G)=L(G_1)</tex>.
+
<tex>L(\Gamma_1)\subseteq L(\Gamma)</tex>, так как при построении <tex>\Gamma_1</tex> из <tex>\Gamma</tex> символы и продукции только убирались. Докажем, что <tex>L(\Gamma_1)\supseteq L(\Gamma)</tex>. Если <tex>w\in L(\Gamma)</tex>, то <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex>. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в <tex>\Gamma_1</tex> его также содержит. Таким образом, <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} w</tex>, <tex>w\in L(\Gamma_1)</tex> и <tex>L(\Gamma)=L(\Gamma_1)</tex>.
 
}}
 
}}
  

Версия 00:38, 8 ноября 2011

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


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

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


Определение:
Нетерминал [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]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]


Теорема:
Пусть [math]\Gamma[/math] — КС-грамматика, и [math]L(\Gamma)\ne\varnothing[/math]. Пусть [math]\Gamma_1[/math] - грамматика, полученная с помощью следующих двух шагов:

1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть [math]\Gamma_2[/math] — полученная в результате грамматика.

2) Удаляются все символы, недостижимые из [math]\Gamma_2[/math].

Тогда [math]\Gamma_1[/math] не имеет бесполезных символов и [math]L(\Gamma_1)=L(\Gamma)[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]X[/math] — оставшийся символ. Известно, что [math]X\overset{*}{\underset{\Gamma}{\Rightarrow}} w[/math] для некоторой цепочки [math]w[/math] из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому [math]S\overset{*}{\underset{\Gamma_2}{\Rightarrow}}w[/math].

Поскольку [math]X[/math] не был удален на втором шаге, известно, что существует такие [math]\alpha[/math] и [math]\beta[/math], для которых [math]S\overset{*}{\underset{\Gamma_2}{\Rightarrow}} \alpha X\beta[/math]. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому [math]S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} \alpha X\beta[/math].

Также известно, что каждый символ в цепочке [math]\alpha X\beta[/math] достижим, поэтому каждый из них является порождающим в [math]\Gamma_2[/math]. Порождение некоторой терминальной цепочки, например, [math]\alpha X\beta\overset{*}{\underset{\Gamma_2}{\Rightarrow}} xwy[/math], содержит только символы, достижимые из [math]S[/math], поскольку они достижимы из символов в цепочке [math]\alpha X\beta[/math]. Таким образом, это порождение есть также порождение в [math]\Gamma_1[/math], то есть [math]S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} \alpha X\beta\overset{*}{\underset{\Gamma_1}{\Rightarrow}} xwy[/math].

Итак, [math]X[/math] полезен в [math]\Gamma_1[/math]. Ввиду произвольности [math]X[/math] в [math]\Gamma_1[/math] можно заключить, что [math]\Gamma_1[/math] не имеет бесполезных символов.

[math]L(\Gamma_1)\subseteq L(\Gamma)[/math], так как при построении [math]\Gamma_1[/math] из [math]\Gamma[/math] символы и продукции только убирались. Докажем, что [math]L(\Gamma_1)\supseteq L(\Gamma)[/math]. Если [math]w\in L(\Gamma)[/math], то [math]S\overset{*}{\underset{\Gamma}{\Rightarrow}} w[/math]. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в [math]\Gamma_1[/math] его также содержит. Таким образом, [math]S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} w[/math], [math]w\in L(\Gamma_1)[/math] и [math]L(\Gamma)=L(\Gamma_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 (рус.)