Изменения

Символ '''[[Формальные_грамматики|Нетерминал]] <tex>A</tex>называется ''' называется порождающим'''(англ. 'непорождающим'generating''), если из него не может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.}}Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части. {{Лемма|statement=После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.|proof=Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.

Рассматривая ===Алгоритм==='''Шаг 0'''. Множество порождающих нетерминалов пустое.<br>'''Шаг 1'''. Находим правила грамматики, можно сделать вывод, что если не содержащие нетерминалов в правых частях и только если все нетерминальные символы правой части являются порождающимидобавляем нетерминалы, то порождающим является и символвстречающихся в левых частях таких правил, стоящий в левой частимножество. Последнее утверждение позволяет написать процедуру обнаружения непорождающих символов в следующем виде: <br># Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов'''Шаг 2'''. # Если найдено такое правило, что все нетерминалы, стоящие в его правой части , уже занесены входят в списокмножество, то добавить добавим в список нетерминалмножество нетерминалы, стоящий стоящие в его левой части. <br># Если на шаге 2 список больше не пополняется'''Шаг 3'''. Повторим предыдущий шаг, то получен список если множество порождающих нетерминалов изменилось.<br>В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

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

Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так:<tex> S\rightarrow AB|CD\\ A\rightarrow EF\\ G\rightarrow AD\\ C\rightarrow c</tex>Применяя описанный алгоритм: # Образовать одноэлементный списокВозьмём множество, состоящий состоящее из начального символа единственного элемента: <tex>\lbrace S \rbrace</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> можно вывести только терминал, а <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'').}} {{Теорема|id=th1|statement=Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.|proof=<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> {{---}} не бесполезный.

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

Допустим, что в грамматике появился непорождающий нетерминал <tex>\RightarrowA</tex> Очевидно, т.к. недостижимые и непорождающие символы являются бесполезными.Так как до удаления недостижимых нетерминалов существовал вывод из <tex>\LeftarrowA</tex> Рассмотрим любой нетерминал некоторой конечной цепочки терминалов <tex>A\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода. Так как он достижимый, существуют  Пусть <tex>B\rightarrow\alpha</tex> и <tex>\beta</tex>{{---}} правило, такие, что первым из удалённых применяемое в выводе <tex>S A \Rightarrow ^* \alpha A \betaomega</tex>. Из того, что любой сивол является порождающим, следует, что из любой строки можно вывести строку из терминалов. ЗначитОно могло быть удалено только в том случае, существует если в <tex>\omega \in \Sigma ^ *alpha</tex>: присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omegaB</tex>— достижим, следовательно достижимы и все нетерминалы из <tex>A\alpha</tex> - . Значит, это правило не бесполезныймогло быть удалено.

== Литература =Пример === 1. Пусть нам дана грамматика: <br> :<tex> S\rightarrow AS|BS|s \\ E\rightarrow EF|FF \\ A\rightarrow a \\ F\rightarrow f</tex><br>2. Удалим правила, содержащие непорождающие нетерминалы: <br> :<tex> S\rightarrow AS|s \\ E\rightarrow EF|FF \\ A\rightarrow a \\ F\rightarrow f</tex><br>3. Теперь удалим недостижимые нетерминалы:<br> :<tex> S\rightarrow AS|s \\ A\rightarrow a</tex> === Замечание ===Шаги алгоритма нельзя менять местами.  Рассмотрим следующую грамматику: <br> :<tex> S\rightarrow AB|a \\ A\rightarrow b</tex> Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.== См. также ==* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]] == Источники информации ==* [[wikipedia:Formal_grammar | Wikipedia {{---}} Formal grammar]]* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia {{---}} Chomsky normal form]* Джон ''ХопкрофтД., Раджив МотваниР., Джеффри УльманД. '' {{---}} Введение в теорию автоматов, языков и вычислений, 2-е изд.: Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.) [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Нормальные формы КС-грамматик]]