Изменения

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

Очевидно, что если и только если все нетерминальные символы Вначале для всех нетерминалов в <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># Если на шаге 2 множество изменилось, повторить шаг 2.# Получено множество всех порождающих Каждый из нетерминалов грамматикипопадёт в очередь только один раз, а все нетерминалыследовательно мы пройдем по списку правил, не попавшие в негоправой части которых он встречается, один раз. Таким образом, являются непорождающимисуммарно получаем <tex>O(\left| \Gamma \right|)</tex>.

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

Очевидно=== Время работы алгоритма ===Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, что если нетерминал однако используя [[Обход_в_глубину,_цвета_вершин|обход в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы глубину]] можно с помощью следующей процедурыускорить его до <tex>O(\left| \Gamma \right|)</tex>. === Пример ===Рассмотрим следующую грамматику:<br> :<tex> S\rightarrow AB|CD\\ A\rightarrow EF\\ G\rightarrow AD\\ C\rightarrow c</tex>Применяя описанный алгоритм:

# Если найдено правилоИз <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в левой части которого стоит нетерминалмножество и получим <tex>\lbrace S, A, B, C, содержащийся в множествеD \rbrace</tex>.# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавить добавим их в множество все нетерминалы из правой части.# Если на шаге 2 множество изменилосьСнова переберём правила. Из <tex>C</tex> можно вывести только терминал, повторить шаг 2а <tex>G</tex> нет в множестве.# Получено После последнего обхода правил грамматики множество всех достижимых нетерминаловне изменилось, а значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, не попавшие F \rbrace</tex>.# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в неголевой части нетерминал, являются недостижимымикоторого нет в полученном множестве.

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

Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов <tex>\Leftrightarrow</tex> тогда и только тогда, когда грамматика <tex>\Gamma</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=th2th1

Пусть После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы.|proof=Допустим, что в грамматике появился непорождающий нетерминал <tex>\GammaA</tex> {{---}} КС-грамматика, и . Так как до удаления недостижимых нетерминалов существовал вывод из <tex>L(\Gamma)\ne\varnothingA</tex>. Пусть некоторой конечной цепочки терминалов <tex>\Gamma_1omega</tex> , то было удалено хотя бы какое- грамматика, полученная с помощью следующих двух шагов:то одно правило из этого вывода.

1) Удаляются непорождающие символы и все продукции, содержащие один или несколько таких символов. Пусть <tex>B\Gamma_2rightarrow\alpha</tex> {{---}} полученная правило, первым из удалённых применяемое в результате грамматикавыводе <tex>A \Rightarrow ^* \omega</tex>.Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.}}

Тогда <tex>\Gamma_1</tex> не имеет бесполезных символов и <tex>L(\Gamma_1)=L(\Gamma)</tex>1.|proof=Пусть нам дана грамматика: <tex>X</texbr> {{---}} оставшийся символ. Известно, что <tex>X\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex> для некоторой цепочки <tex>w</tex> из терминалов. Кроме того, каждый символ, использованный в этом порождении, достижим, поэтому <tex>S\overset{*}{\underset{\Gamma_2}{\Rightarrow}}w</tex>.

Поскольку <tex>X</tex> не был удален на втором шаге, известно, что существует такие :<tex> S\rightarrow AS|BS|s \\alpha</tex> и <tex> E\beta</tex>, для которых <tex>Srightarrow EF|FF \overset{*}{\underset{ A\Gamma_2}{rightarrow a \Rightarrow}} \alpha X F\betarightarrow f</tex><br>2. Кроме того, каждый символ, использованный в этом порождении, достижимУдалим правила, поэтому содержащие непорождающие нетерминалы: <texbr>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} \alpha X\beta</tex>.

Также известно, что каждый символ в цепочке :<tex> S\rightarrow AS|s \alpha X\beta</tex> достижим, поэтому каждый из них является порождающим в <tex> E\Gamma_2</tex>. Порождение некоторой терминальной цепочки, например, <tex>rightarrow EF|FF \alpha X\beta A\overset{*}{rightarrow a \underset{\Gamma_2}{ F\Rightarrow}} xwy</tex>, содержит только символы, достижимые из <tex>Srightarrow f</tex>, поскольку они достижимы из символов в цепочке <tex>\alpha X\beta</texbr>3. Таким образом, это порождение есть также порождение в <tex>\Gamma_1</tex>, то есть <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} \alpha X\beta\overset{*}{\underset{\Gamma_1}{\Rightarrow}} xwyТеперь удалим недостижимые нетерминалы:</texbr>.

Итак, :<tex>X</tex> полезен в <tex>\Gamma_1</tex>. Ввиду произвольности <tex>X</tex> в <tex>\Gamma_1</tex> можно заключить, что <tex>\Gamma_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{*}{rightarrow AS|s \underset{\Gamma}{ A\Rightarrow}} w</tex>. Каждый символ в этом порождении является как достижимым, так и порождающим, поэтому порождение в <tex>\Gamma_1</tex> его также содержит. Таким образом, <tex>S\overset{*}{\underset{\Gamma_1}{\Rightarrow}} wrightarrow a</tex>, <tex>w\in L(\Gamma_1)</tex> и <tex>L(\Gamma)=L(\Gamma_1)</tex>.}}

Эти шаги нельзя менять местами. Рассмотрим следующую грамматику:<br>

:<tex> S\rightarrow AB|a\\ A\rightarrow b</tex>

Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A\rightarrow b</tex>станет недостижимым.== См. также ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]

Если начать == Источники информации ==* [[wikipedia:Formal_grammar | Wikipedia {{---}} Formal grammar]]* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia {{---}} Chomsky normal form]* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с проверки достижимостиангл. — Москва, Издательский дом «Вильямс», то все символы грамматики оказываются достижимыми2002. Если затем удалить <tex>B</tex> как непорождающий символ, то останется грамматика — 528 с бесполезными символами <tex>A</tex> и <tex>b</tex>.: ISBN 5-8459-0261-4 (рус.)

== Литература ==[[Категория: Теория формальных языков]]* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2[[Категория: Контекстно-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. свободные грамматики]][[Категория: ISBN 5-8459-0261Нормальные формы КС-4 (рус.)грамматик]]