1632
правки
Изменения
м
\end{array}
''Необходимость.'' <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=
\end{array}:</tex>.<br>Удалим правила, содержащие непорождающие нетерминалы и получим грамматику<tex>\begin{array}{l l}
\end{array}:</tex>.<br>Теперь удалим недостижимые нетерминалы и получим грамматику<tex>\begin{array}{l l}
\end{array}</tex>.
\end{array}.
rollbackEdits.php mass rollback
== Порождающие и непорождающие нетерминалы ==
===Описание===
{{Определение
|definition=
[[Формальные_грамматики|Нетерминал ]] <tex>A</tex> называется '''порождающим'''(англ. ''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.# Если на шаге 2 множество изменилось, повторить шаг 2.# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
{{Лемма
|statement=
}}
===Алгоритм===
'''Шаг 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>.
# После следующего обхода правил из грамматики множество не изменится.
# Теперь удалим правила <tex>A\rightarrow SD</tex> и <tex>D\rightarrow aD</tex>, так как они содержат нетерминалы, которых нет в полученном множестве.
== Достижимые и недостижимые нетерминалы ==
===Описание===
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' (англ. ''reachable'') в [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|КС-грамматике ]] <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым'''(англ. ''unreachable'').
}}
Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.# Если на шаге 2 множество изменилось, повторить шаг 2.# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
{{Лемма
|statement=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}
===Алгоритм===
'''Шаг 0.''' Множество достижимых нетерминалов состоит из единственного элемента: <tex>\lbrace S \rbrace</tex>.<br>
'''Шаг 1.''' Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавим в множество все нетерминалы из правой части.<br>
'''Шаг 2.''' Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.<br>
Получаем множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.
=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Обход_в_глубину,_цвета_вершин|обход в глубину]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.
=== Пример ===
Рассмотрим следующую грамматику:<br> :<tex>\begin{array}{l l}
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>BA</tex>, можно вывести <tex>CE</tex> и <tex>DF</tex> нельзя вывести нетермиалы, а из добавим их в множество.# Снова переберём правила. Из <tex>AC</tex> можно вывести только терминал, а <tex>E</tex> и <tex>FG</tex>нет в множестве.# Полученное После последнего обхода правил грамматики множество нетерминалов будет такимне изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>. Больше оно меняться не будет.
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.
== Полезные и бесполезные нетерминалы ==
===Описание===
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' (англ. ''useful'') в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным'''(англ. ''useless'').
}}
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
|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>\begin{array}{l l}
S\rightarrow AS|BS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f
</tex><br>
2. Удалим правила, содержащие непорождающие нетерминалы: <br>
S\rightarrow AS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f
</tex><br>
3. Теперь удалим недостижимые нетерминалы:<br>
S\rightarrow AS|s \\
A\rightarrow a
=== Замечание ===
Шаги алгоритма нельзя менять местами.
Рассмотрим следующую грамматику:<br> :<tex>\begin{array}{l l}
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 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Нормальные формы КС-грамматик]]
