Изменения

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

Рассматривая ===Алгоритм==='''Шаг 0'''. Множество порождающих нетерминалов пустое.<br>'''Шаг 1'''. Находим правила грамматики, можно сделать выводне содержащие нетерминалов в правых частях и добавляем нетерминалы, встречающихся в левых частях таких правил, в множество.<br>'''Шаг 2'''. Если найдено такое правило, что если все символы нетерминалы, стоящие в его правой части являются производящими, уже входят в множество, то производящим является и символдобавим в множество нетерминалы, стоящий стоящие в его левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов <br>'''Шаг 3'''. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.<br>В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в следующем виденего, являются непорождающими. === Время работы алгоритма ===Данный алгоритм работает за <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> то добавить S\rightarrow Ac\\ в A\rightarrow SD\\ список D\rightarrow aD\\ A\rightarrow a </tex>Применяя описанный алгоритм:# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.# Добавим в множество нетерминал<tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, стоящий в его левой правой частикоторого стоят нетерминал <tex>A</tex>, который есть в множестве, и терминал <tex>c</tex>. # Если на шаге 2 список больше После следующего обхода правил из грамматики множество не пополняетсяизменится.# Теперь удалим правила <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'').}}Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. {{Лемма|statement=После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не появляется ни изменится.|proof=Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в одной выводимой цепочкевыводе какого-либо слова.

Рассматривая правила грамматики, можно заметить , что если нетерминал в левой части правила является достижимым , то и все символы правой части являются достижимыми. Это свойство правил является основой процедуры выявления недостижимых символов, которую можно записать так:<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> {{---}} не бесполезный.}} ===Алгоритм===Алгоритм состоит из двух этапов:# Удалить из грамматики правила, содержащие непорождающие нетерминалы.# Удалить из грамматики правила, содержащие недостижимые нетерминалы. === Корректность алгоритма ===Достаточность данных действий следует из доказанной выше теоремы. {{Теорема|id=th1|statement=После удаления из грамматики правил, содержащих недостижимые нетерминалы, не появятся новые непорождающие нетерминалы.|proof=Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода. Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\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 (рус.) [[Категория: Теория формальных языков]][[Категория: Контекстно-свободные грамматики]][[Категория: Нормальные формы КС-грамматик]]