Изменения

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

Рассматривая правила грамматики, можно сделать вывод, что если и только если все нетерминальные символы правой части являются порождающими, то порождающим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде: === Время работы алгоритма ===# Составить список нетерминаловДанный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминаловгде <tex>\left| \Gamma \right|</tex> {{---}} размер грамматики. # Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в Однако используя [[Очередь|очередь]] можно ускорить его левой части. # Если на шаге 2 список больше не пополняется, то получен список всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающимидо <tex>O(\left| \Gamma \right|)</tex>.

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

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

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

Грамматика <tex>\Gamma</tex> не содержит бесполезных символов '''нетерминалов тогда и только тогда, когда''' она грамматика <tex>\Gamma</tex> не содержит ни недостижимых символовнетерминалов, ни непорождающих.

<tex>\RightarrowLeftarrow</tex> <br/>:Очевидно, т.к. так как недостижимые и непорождающие символы нетерминалы являются бесполезными. <tex>\LeftarrowRightarrow</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>GA</tex> {{---}} КС-грамматика, и . Так как до удаления недостижимых нетерминалов существовал вывод из <tex>L(G)\ne\varnothingA</tex>. Пусть некоторой конечной цепочки терминалов <tex>G_1\omega</tex> , то было удалено хотя бы какое- грамматика, полученная с помощью следующих двух шагов:то одно правило из этого вывода.

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

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

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

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

Итак, :<tex>X</tex> полезен в <tex>G_1</tex>. Ввиду произвольности <tex>X</tex> в <tex>G_1</tex> можно заключить, что <tex>G_1</tex> не имеет бесполезных символов. <tex>L(G_1) S\subseteq L(G)</tex>, так как при построении <tex>G_1</tex> из <tex>G</tex> символы и продукции только убирались. Докажем, что <tex>L(G_1)rightarrow AS|s \supseteq L(G)</tex>. Если <tex>w\in L(G)</tex>, то <tex>S A\Rightarrow _{G}^* wrightarrow a</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>.}}

Эти шаги нельзя менять местами. Рассмотрим следующую грамматику:<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 (рус.)грамматик]]