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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Символ '''<tex>A</tex>''' называется '''непроизводящим''', если из него не может быть выведена конечная терминальная цепочка.
+
Символ '''<tex>A</tex>''' называется '''непорождающим''', если из него не может быть выведена конечная терминальная цепочка.
 
}}
 
}}
  
Рассматривая правила грамматики,  можно сделать  вывод,  что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде:  
+
Рассматривая правила грамматики,  можно сделать  вывод,  что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде:  
 
# Составить список нетерминалов,  для которых найдется хотя  бы одно правило, правая часть которого не содержит нетерминалов.  
 
# Составить список нетерминалов,  для которых найдется хотя  бы одно правило, правая часть которого не содержит нетерминалов.  
 
# Если найдено такое правило,  что все нетерминалы, стоящие  в его правой части уже занесены в список,  то добавить  в  список  нетерминал, стоящий в его левой части.  
 
# Если найдено такое правило,  что все нетерминалы, стоящие  в его правой части уже занесены в список,  то добавить  в  список  нетерминал, стоящий в его левой части.  
# Если на шаге 2 список больше не пополняется,  то  получен  список всех производящих нетерминалов грамматики,  а все нетерминалы не попавшие в него являются непроизводящими.
+
# Если на шаге 2 список больше не пополняется,  то  получен  список всех порождающих нетерминалов грамматики,  а все нетерминалы не попавшие в него являются непорождающими.
  
 
{{Определение
 
{{Определение
Строка 24: Строка 24:
 
|definition=
 
|definition=
 
Символ '''<tex>A</tex>''' называется '''бесполезным''' в   
 
Символ '''<tex>A</tex>''' называется '''бесполезным''' в   
КС-грамматике '''<tex>\Gamma</tex>''', если он является недостижимым или непроизводящим.
+
КС-грамматике '''<tex>\Gamma</tex>''', если он не может встретиться в выводе слова из терминалов.
 
}}
 
}}
 
 
{{Теорема
 
{{Теорема
 
|id=th1
 
|id=th1
 
|statement=
 
|statement=
Исключить бесполезные символы из грамматики можно удаляя правила, содержащие вначале непроизводящие, а затем недостижимые символы.
+
Грамматика <tex>\Gamma</tex> не содержит бесполезных символов '''тогда и только тогда, когда''' она не содержит ни недостижимых символов, ни непорождающих.
 
|proof=
 
|proof=
Любой терминальный символ является генерирующим.
+
<tex>\Rightarrow</tex> Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными.
Пусть <tex>A \rightarrow \alpha</tex> и известно, что <tex>\alpha</tex> состоит только из генерирующих символов, тогда <tex>A</tex> - генерирующий символ.
+
<tex>\Leftarrow</tex> Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижимый, существуют <tex>\alpha</tex> и <tex>\beta</tex>, такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\theta \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \theta</tex>, и <tex>A</tex> - не бесполезный.
Если <tex>\alpha = \epsilon</tex>, тогда <tex>A</tex> также генерирующий символ.
 
 
}}
 
}}

Версия 21:30, 14 октября 2010

Эта статья находится в разработке!


Определение:
Символ [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]\theta \in \Sigma ^ *[/math]: [math]S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \theta[/math], и [math]A[/math] - не бесполезный.
[math]\triangleleft[/math]