Изменения

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

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

Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако где <tex>\left| \Gamma \right|</tex> {{---}} размер грамматики. Однако используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>. ===Модификация алгоритма с очередью===Для реализации алгоритма поиска непорождающих нетерминалов будем использовать следующие структуры:*<tex>\mathrm{isGenerating[nonterm_i]}</tex> {{---}} является ли нетерминал <tex>\mathrm{nonterm_i}</tex> порождающим или нет,*<tex>\mathrm{counter[rule_i]}</tex> {{---}} счетчик количества нетерминалов, которые ещё не помечены порождающими, для каждого из правил,*<tex>\mathrm{concernedRules[nonterm_i]}</tex> {{---}} для каждого нетерминала <tex>\mathrm{nonterm_i}</tex> список номеров правил, в правой части которых он встречается,*<tex>\mathrm{Q}</tex> {{---}} очередь нетерминалов, помеченных порождающими, но ещё не обработанных. Вначале для всех нетерминалов в <tex>\mathrm{isGenerating}</tex> поставим <tex>false</tex>. В <tex>\mathrm{counter}</tex> поставим количество нетерминалов в правой части. Нетерминалы, у которых счётчик <tex>\mathrm{counter}</tex> нулевой, добавим в очередь и отметим их порождающими.<br>Пока в очереди есть элементы, достаём очередной нетерминал и уменьшаем <tex>\mathrm{counter}</tex> для всех правил из <tex>\mathrm{concernedRules}</tex> для данного нетерминала. Если счётчик количества порождающих терминалов обнулился, то добавим нетерминал, стоящий в левой части данного правила в очередь и пометим его порождающим.<br>Каждый из нетерминалов попадёт в очередь только один раз, следовательно мы пройдем по списку правил, в правой части которых он встречается, один раз. Таким образом, суммарно получаем <tex>O(\left| \Gamma \right|)</tex>.

Рассмотрим следующую грамматику:<br> :<tex>\begin{array}{l l} S\rightarrow Ac\\ A\rightarrow SD\\ D\rightarrow aD\\ A\rightarrow a \end{array}

# Теперь удалим правила <tex>A\rightarrow SD</tex> и <tex>D\rightarrow aD</tex>, так как они содержит содержат нетерминалы, которых нет в полученном множестве.

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

 Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.# Если на шаге 2 множество изменилось, повторить шаг 2.# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми. 

Рассмотрим следующую грамматику:<br> :<tex>\begin{array}{l l}

# Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нету нет в множестве.

''Необходимость.'' <tex>\Leftarrow</tex><br/>:Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

''Достаточность.'' <tex>\Rightarrow</tex><br/>:Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.

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

Докажем{{Теорема|id=th1|statement=После удаления из грамматики правил, содержащих недостижимые нетерминалы, что после выполнения второго шага не могут появиться появятся новые непорождающие нетерминалы.|proof=

1. Пусть нам дана грамматика:<br> :<tex>\begin{array}{l l}

\end{array}:</tex>.<br>Удалим правила, содержащие непорождающие нетерминалы и получим грамматику<tex>\begin{array}{l l}

\end{array}:</tex>.<br>Теперь удалим недостижимые нетерминалы и получим грамматику<tex>\begin{array}{l l}

\end{array}</tex>.

Рассмотрим следующую грамматику:<br> :<tex>\begin{array}{l l}

== Литература Источники информации ==* [[wikipedia:Formal_grammar | Wikipedia {{---}} Formal grammar]]* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia {{---}} Chomsky normal form]