Удаление бесполезных символов из грамматики — различия между версиями
Строка 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>\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> - не бесполезный. | |
− | |||
}} | }} |
Версия 21:30, 14 октября 2010
Эта статья находится в разработке!
Определение: |
Символ | называется непорождающим, если из него не может быть выведена конечная терминальная цепочка.
Рассматривая правила грамматики, можно сделать вывод, что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде:
- Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов.
- Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части.
- Если на шаге 2 список больше не пополняется, то получен список всех порождающих нетерминалов грамматики, а все нетерминалы не попавшие в него являются непорождающими.
Определение: |
Символ | называется недостижимым в КС-грамматике , если не появляется ни в одной выводимой цепочке.
Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так:
- Образовать одноэлементный список, состоящий из начального символа
- Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части.
- Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми.
Определение: |
Символ | называется бесполезным в КС-грамматике , если он не может встретиться в выводе слова из терминалов.
Теорема: |
Грамматика не содержит бесполезных символов тогда и только тогда, когда она не содержит ни недостижимых символов, ни непорождающих. |
Доказательство: |
Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными. Рассмотрим любой нетерминал . Так как он достижимый, существуют и , такие, что . Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует : , и - не бесполезный. |