1632
правки
Изменения
м
Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace </tex>.<br/>
Для этого достаточно доказать, что
<tex>A \underset{G'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).
<tex>\Leftarrow</tex><br/>=== Модификация с очередью ===Заведем несколько структур:Пусть *<tex>A \undersetmathtt{GisEpsilon[nonterm_i]}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/> Докажем индукцией по длине порождения в грамматике <tex>G</tex>, что <tex>A \underset{G'}{\Rightarrow---}^*w</tex>.<br/> '''База'''. <tex>A \underset{G}{\Rightarrow} w</tex>.<br/>Правило для каждого нетерминала будем хранить пометку, является он <tex>A \rightarrow w</tex> присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>-порождающим или нет.<br/>'''Предположение индукции'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \undersetmathtt{G'concernedRules[nonterm_i]}{\Rightarrow}^*w </tex>.<br/>'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow---}Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^для каждого нетерминала будем хранить список номеров тех правил, в правой части которых он встречается;*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \undersetmathtt{Gcounter[rule_i]}{\Rightarrow}^*w_i</tex>.<br/>Пусть <tex>Y_{i_1}, Y_{i_2---}, ..., Y_{i_p}</tex> — подпоследовательностьдля каждого правила будем хранить счетчик количества нетерминалов в правой части, состоящая из всех элементов, таких, что которые еще не помечены <tex>w_{i_k} \ne \varepsilon</tex>, то есть -порождающими;*<tex>Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G}mathtt{\RightarrowQ}^*w</tex>. <tex>p \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2---} ... Y_{i_p}</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>.<br/>Так как каждое из порождений <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, чтоочередь нетерминалов, если помеченных <tex>w_i \ne \varepsilon</tex>-порождающими, то <tex>Y_i \underset{G'}{\Rightarrow}^*w_i</tex>.<br/>Таким образом, <tex>A \underset{G'}{\Rightarrow} Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G'}{\Rightarrow}^* w</tex>но еще не обработанных.
Подставив Сначала проставим <tex>S\mathtt{false}</tex> вместо в <tex>A\mathtt{isEpsilon} \ </tex> для всех нетерминалов, а в утверждение (*)<tex>\mathtt{counter} \ </tex> для каждого правила запишем количество нетерминалов справа от него. Те правила, видимдля которых <tex>\mathtt{counter} \ </tex> сразу же оказался нулевым, что добавим в <tex>w \in L(G)mathtt{Q}</tex> для и объявим истинным соответствующий <tex>w \ne mathtt{isEpsilon}</tex>, так как это <tex>\varepsilon</tex> тогда и только тогда-правила. Теперь будем доставать из очереди по одному нетерминалу, когда смотреть на список <tex>w \in L(G')mathtt{concernedRules} \ </tex>. Так как после выполнения шага 5 алгоритма в для него и уменьшать <tex>G'\mathtt{counter}</tex> могло добавиться только пустое слово для всех правил оттуда. Если <tex>\varepsilonmathtt{counter} \ </tex>какого-то правила в этот момент обнулился, то язык, задаваемый КС грамматикой нетерминал из левой части этого правила помечается <tex>G'\varepsilon</tex>-порождающим, совпадает с языкомесли еще не был помечен до этого, задаваемым КС грамматикой и добавляется в <tex>G\mathtt{Q}</tex>.}}Продолжаем, пока очередь не станет пустой.
Рассмотрим грамматику:<tex> \Gamma = \begin{array}{l l} S\rightarrow T_1 T_2 T_3 ... T_n\\ T_1\rightarrow t_1|\varepsilon\\ T_2\rightarrow t_2|\varepsilon\\ ...\\ T_n\rightarrow t_n|\varepsilon\end{array}</tex>.<br><tex>\left| \Gamma \right| = O(n)</tex>. Из нетерминала <tex>S</tex> можно вывести <tex>2^n</tex> сочетаний нетерминалов <tex>T_i</tex>. Таким образом в худшем случае Базовый алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>.<br>Однако если В алгоритме с модификацией нетерминал попадает в грамматике устранены [[Удаление_длинных_правил_из_грамматики|длинные правила]]очередь ровно один раз, соответственно ровно один раз мы пройдемся по списку правил, то алгоритм будет работать за <tex>O(\left| \Gamma \right|)</tex> и добавит в грамматику правой части которых он лежит. Суммарно получается <tex>O(\left| \Gamma \right|)</tex> новых правил длинны <tex>O(1)</tex>.
В результате мы получим новую грамматику без Таким образом <tex>\varepsilon</tex>-правил:порождающими нетерминалами являются <tex>\begin{array}{l l} S\rightarrow Ad|ABd|ABCd|Bd|BCd|Cd|d\\ A\rightarrow a\\ </tex>, <tex>B\rightarrow A|AC|</tex>, <tex>C\\ C\rightarrow c\end{array}</tex>и <tex>S</tex>.
Для доказательства корректности алгоритма достаточно показать<tex>\Leftarrow</tex><br/>Пусть <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/> Докажем индукцией по длине порождения в грамматике <tex>\Gamma</tex>, что<tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex>.<br/> '''База'''. <tex>A \underset{\Gamma}{\Rightarrow} w</tex>.<br/>Правило <tex>A \rightarrow w</tex> присутствует в <tex>\Gamma</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>\Gamma'</tex>, если множество поэтому <tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex>.<br/>'''Предположение индукции'''. Пусть из <tex>A \underset{\Gamma}{\Rightarrow}^*w \ne \varepsilon</tex>-порождающих нетерминалов менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{\Gamma'}{\Rightarrow}^*w </tex>.<br/>'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{\Gamma}{\Rightarrow}Y_1 Y_2 \ldots Y_m \underset{\Gamma}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на очередной итерации алгоритма не изменялось<tex>w_1 w_2 \ldots w_m</tex>, где <tex>Y_i \underset{\Gamma}{\Rightarrow}^*w_i</tex>.<br/>Пусть <tex>Y_{i_1}, Y_{i_2}, \ldots, Y_{i_p}</tex> — подпоследовательность, состоящая из всех элементов, таких, что <tex>w_{i_k} \ne \varepsilon</tex>, то алгоритм нашел все есть <tex>Y_{i_1} Y_{i_2} \ldots Y_{i_p} \underset{\Gamma}{\Rightarrow}^*w</tex>. <tex>p \geqslant 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2} \ldots Y_{i_p}</tex> является правилом в <tex>\Gamma'</tex> по построению <tex>\Gamma'</tex>.<br/>Так как каждое из порождений <tex>Y_i \underset{\Gamma}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>-порождающие нетерминалы, то <tex>Y_i \underset{\Gamma'}{\Rightarrow}^*w_i</tex>.<br/>Таким образом, <tex>A \underset{\Gamma'}{\Rightarrow} Y_{i_1} Y_{i_2} \ldots Y_{i_p} \underset{\Gamma'}{\Rightarrow}^* w</tex>.
Пусть после завершения алгоритма существуют нетерминалы такие, что они являются Подставив <tex>\varepsilonS</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал вместо <tex>BA</tex>в утверждение (*), из которого выводится видим, что <tex>w \varepsilonin L(\Gamma)</tex> за наименьшее число шагов. Тогда в грамматике есть правило для <tex>B w \ne \rightarrow C_1C_2...C_kvarepsilon</tex>тогда и только тогда, где каждый нетерминал <tex>C_i</tex> — когда <tex>w \in L(\varepsilonGamma')</tex>-порождающий. Каждый Так как после выполнения шага 5 алгоритма в <tex>C_i\Gamma'</tex> входит в множество могло добавиться только пустое слово <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательното язык, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество задаваемый КС-грамматикой <tex>\varepsilonGamma'</tex>, совпадает с языком, задаваемым КС-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все грамматикой <tex>\varepsilonGamma</tex>-порождающие нетерминалы.
Данный Рассмотрим грамматику <tex>\Gamma</tex>::<tex>S\rightarrow T_1 T_2 T_3 \ldots T_n</tex>:<tex>T_1\rightarrow t_1|\varepsilon</tex>:<tex>T_2\rightarrow t_2|\varepsilon</tex>:<tex>\ldots\</tex>:<tex>T_n\rightarrow t_n|\varepsilon</tex> <tex>\left| \Gamma \right| = O(n)</tex>. Из нетерминала <tex>S</tex> можно вывести <tex>2^n</tex> сочетаний нетерминалов <tex>T_i</tex>. Таким образом в худшем случае алгоритм работает за <tex>O(2^{\left| \Gamma \right| ^ 2})</tex>, однако используя .<br>Рассмотрим теперь грамматику с устраненными [[ОчередьУдаление_длинных_правил_из_грамматики|очередьдлинными правилами]] можно ускорить его до . После применения данного алгоритма, который работает за <tex>O(\left| \Gamma \right|)</tex>, в грамматике станет на <tex>O(\left| \Gamma \right|)</tex> больше правил, но при этом все они будут размером <tex>O(1)</tex>. Итого по-прежнему <tex>\left| \Gamma \right| = O(n)</tex>. Однако алгоритм удаления <tex>\varepsilon</tex>-правил будет работать за <tex>O(\left| \Gamma \right|)</tex>, поскольку для каждого правила можно будет добавить только <tex>O(1)</tex> сочетаний нетерминалов.
Таким образом В результате мы получим новую грамматику без <tex>\varepsilon</tex>-порождающими нетерминалами являются правил: :<tex>AS\rightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d</tex>, :<tex>BA\rightarrow a</tex>, :<tex>B\rightarrow A|AC|C</tex> и :<tex>SC\rightarrow c</tex>.
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]
rollbackEdits.php mass rollback
== Используемые определения ==
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами''' (англ. ''<tex>\varepsilon</tex> -rule'').
}}
{{Определение
|definition = Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим''' (англ. ''<tex>\varepsilon</tex>-generating''), если <tex>A \Rightarrow^* \varepsilon</tex>.
}}
== Алгоритм удаления поиска ε-правил из грамматики порождающих нетерминалов =='''Вход:''' КС -грамматика <tex> G\Gamma=\langle N,\Sigma, P, S \rangle</tex>.<br/>'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S' \rangle</tex> без множество <tex>\varepsilon</tex>-правил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил); <tex>L(G') = L(G)</tex>порождающих нетерминалов.
# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.# [[#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0_.CE.B5-.D0.BF.D0.BE.D1.80.D0.BE.D0.B6.D0.B4.D0.B0.D1.8E.D1.89.D0.B8.D1.85_.D0.BD.D0.B5.D1.82.D0.B5.D1.80.D0.BC.D0.B8.D0.BD.D0.B0.D0.BB.D0.BE.D0.B2 | Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].# Для каждого правила вида <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex> (где <tex>\alpha_i</tex> — последовательности Составить множество, состоящее из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы) добавить входящих в <tex>P'</tex> все возможные варианты левые части таких правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \le j \le k)</tex>.# Удалить все Перебираем правила грамматики <tex>\varepsilon</tex>-правила из <tex>P'Gamma</tex>.# Если в исходной грамматике найдено правило <tex>GA \rightarrow C_1C_2 \ldots C_k</tex> выводилось , для которого верно, что каждый <tex>\varepsilonC_i</tex>принадлежит множеству, то необходимо добавить новый нетерминал <tex>S'A</tex>в множество.# Если на шаге 2 множество изменилось, сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>то повторить шаг 2.
=== Доказательство корректности ===
{{Теорема
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного Описанный выше алгоритма по грамматике алгоритм находит все <tex>G\varepsilon</tex>, то -порождающие нетерминалы грамматики <tex>L(G') = L(G)\Gamma</tex>.
|proof =
Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\Rightarrowvarepsilon</tex><br\>Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex> и -порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>w \ne \varepsilon</tex>-порождающие нетерминалы.<br/>Докажем индукцией по длине порождения в грамматике <tex>G'</tex>Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>A \underset{G}{\Rightarrow}^*wvarepsilon</tex>-порождающими, но не были найдены алгоритмом.<br/> '''База'''. Выберем из этих нетерминалов нетерминал <tex>A \underset{G'}{\Rightarrow} wB</tex>.<br/>В этом случае в , из которого выводится <tex>G'</tex> есть правило <tex>A \rightarrow wvarepsilon</tex>за наименьшее число шагов. По построению <tex>G'</tex> Тогда в <tex>G</tex> грамматике есть правило <tex>A B \rightarrow C_1C_2 \alphaldots C_k</tex>, причем где каждый нетерминал <tex>\alphaC_i</tex> — цепочка <tex>w</tex>, элементы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G---}{\Rightarrow}^*w</tex>.<br/>'''Предположение индукции'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что -порождающий. Каждый <tex>A \underset{G}{\Rightarrow}^*wC_i</tex>.<br/>'''Переход'''.Пусть входит в порождении множество <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k \underset{G'}{\Rightarrow}^*wvarepsilon</tex>-порождающих нетерминалов, где так как иначе вместо <tex>X_i \in N \cup \Sigma B</tex>. Первое использованное правило должно быть построено по правилу грамматики необходимо было взять <tex>GC_i</tex> <tex>A \rightarrow Y_1 Y_2...Y_m</tex>Следовательно, где последовательность на одной из итераций алгоритма <tex>Y_1 Y_2...Y_mB</tex> совпадает с последовательностью <tex>X_1 X_2...X_k</tex>, символы которой, возможно, перемежаются уже добавился в множество <tex>\varepsilon</tex>-порождающими нетерминалами.<br/>Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2.порождающих нетерминалов.Противоречие.w_k</tex>, где <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминалСледовательно, то алгоритм находит все <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G'}{\Rightarrow}^*w_ivarepsilon</tex> содержит менее <tex>n</tex> шагов-порождающие нетерминалы. По предположению <tex>X_i \underset{G}{\Rightarrow}^*w_i</tex>, значит <tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^* X_1 X_2...X_k \underset{G}{\Rightarrow}^* w_1 w_2...w_k = w</tex>.
=== Время работы алгоритма ===
=== Пример ===
Рассмотрим грамматику, причем сразу пронумеруем правила:#<tex>S\rightarrow ABC</tex>#<tex>S\rightarrow DS </tex>#<tex>A\rightarrow \varepsilon</tex>#<tex>B\rightarrow AC</tex>#<tex>C\rightarrow \varepsilon</tex>#<tex>D\rightarrow d</tex> ''Поскольку правило 6 содержит справа терминалы, оно заведомо не будет влиять на ответ, поэтому мы не будем его учитывать.'' Построим массив списков <tex>\beginmathtt{arrayconcernedRules}</tex>.{l l| class="wikitable"| colspan=5 |<tex>\mathtt{concernedRules} </tex> |-!<tex>S</tex>!<tex>A</tex>!<tex>B</tex>!<tex>C</tex>!<tex>D</tex>|-|2|1, 4|1|1, 4|2|} {| class="wikitable" style="border:solid 2px gray"!style="border-right:solid 2px gray"|<tex>\rightarrow ABCdmathtt{Q}</tex>!style="border-right:solid 2px gray" colspan=5| <tex>\mathtt{isEpsilon}</tex>!style="border-right:solid 2px gray" colspan=5| <tex>\mathtt{counter}</tex> A!Комментарий|-!style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\rightarrow a|left \varepsilon{ \right \}</tex> !style="border-top:solid 2px gray"|<tex>S</tex>!style="border-top:solid 2px gray"|<tex>A</tex>!style="border-top:solid 2px gray"|<tex>B</tex>!style="border-top:solid 2px gray"|<tex>C</tex>!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>!style="border-top:solid 2px gray"|1!style="border-top:solid 2px gray"|2!style="border-top:solid 2px gray"|3!style="border-top:solid 2px gray"|4!style="border-top:solid 2px gray; border-right:solid 2px gray"|5|style="border-top:solid 2px gray" rowspan=2|Зададим начальные значения массивам <tex>\rightarrow ACmathtt{counter} \</tex> и <tex>\mathtt{isEpsilon}</tex>.|-|0|0|0|0|style="border-right:solid 2px gray"|0|3|2|0 |2|style="border-right:solid 2px gray"|0|-|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left \{A,C\rightarrow cright \}</tex>!style="border-top:solid 2px gray"|<tex>S</tex>!style="border-top:solid 2px gray"|<tex>A</tex>!style="border-top:solid 2px gray"|<tex>B</tex>!style="border-top:solid 2px gray"|<tex>C</tex>!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>!style="border-top:solid 2px gray"|1!style="border-top:solid 2px gray"|2!style="border-top:solid 2px gray"|3!style="border-top:solid 2px gray"|4!style="border-top:solid 2px gray; border-right:solid 2px gray"|5|style="border-top:solid 2px gray" rowspan=2 |Заметим, что правила 3 и 5 являются <tex>\varepsilon</tex>-правилами. Пометим левые нетерминалы из этих правил и добавим их в очередь. После этого в <tex>\mathtt{Q}</tex> лежит <tex>A</tex> и <tex>C</tex>, а <tex>\mathtt{counter} \ </tex> остался без изменений.|-|0|1|0|1|style="border-right:solid 2px gray"|0|3|2|0|2|style="border-right:solid 2px gray"|0|-|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left\end{arrayC \right\}</tex>!style="border-top:solid 2px gray"|<tex>S</tex>!style="border-top:solid 2px gray"|<tex>A</tex>!style="border-top:solid 2px gray"|<tex>B</tex>!style="border-top:solid 2px gray"|<tex>C</tex>!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>!style="border-top:solid 2px gray"|1!style="border-top:solid 2px gray"|2!style="border-top:solid 2px gray"|3!style="border-top:solid 2px gray"|4!style="border-top:solid 2px gray; border-right:solid 2px gray"|5|style="border-top:solid 2px gray" rowspan=2|Достанем из очереди <tex>A</tex>, декрементируем те счетчики, которые относятся к связанным с ним правилам. К очереди ничего не добавится.|-|0|1|0|1|style="border-right:solid 2px gray"|0|2|2|0|1|style="border-right:solid 2px gray"|0|-|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left\{B \right\}</tex>!style="border-top:solid 2px gray"|<tex>S</tex>!style="border-top:solid 2px gray"|<tex>A</tex>!style="border-top:solid 2px gray"|<tex>B</tex>!style="border-top:solid 2px gray"|<tex>C</tex>!style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>D</tex>!style="border-top:solid 2px gray"|1!style="border-top:solid 2px gray"|2!style="border-top:solid 2px gray"|3!style="border-top:solid 2px gray"|4!style="border-top:solid 2px gray; border-right:solid 2px gray"|5|style="border-top:solid 2px gray" rowspan=2|Достанем из очереди <tex>C</tex>. После проведения действий из алгоритма в которой очередь добавится <tex>B</tex>.|-|0|1|1|1|style="border-right:solid 2px gray"|0|1|2|0|0|style="border-right:solid 2px gray"|0|-|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left\{S \right\}</tex>!style="border-top:solid 2px gray"|<tex>S</tex>!style="border-top:solid 2px gray"|<tex>A</tex>, !style="border-top:solid 2px gray"|<tex>B</tex> и !style="border-top:solid 2px gray"|<tex>C</tex> являются !style="border-top:solid 2px gray; border-right:solid 2px gray"|<tex>\varepsilonD</tex>!style="border-top:solid 2px gray"|1!style="border-порождающими нетерминалами.top:solid 2px gray"|2!style="border-top:solid 2px gray"|3!style="border-top:solid 2px gray"|4# Переберём для каждого правила все возможные сочетания &epsilon!style="border-top:solid 2px gray;border-порождающих нетерминалов и добавим новые правилаright:solid 2px gray"|5#* |style="border-top:solid 2px gray" rowspan=2|Достанем из очереди <tex>B</tex>. После действий алгоритма в очередь добавится <tex>S</tex>.|-|1|1|1|1|style="border-right:solid 2px gray"|0|0|2|0|0|style="border-right:solid 2px gray"|0|-|style="border-top:solid 2px gray; border-right:solid 2px gray" rowspan=2|<tex>\left\{ \rightarrow Adright\}</tex>!style="border-top:solid 2px gray"|ABd<tex>S</tex>!style="border-top:solid 2px gray"|Bd<tex>A</tex>!style="border-top:solid 2px gray"|BCd<tex>B</tex>!style="border-top:solid 2px gray"|Cd<tex>C</tex>!style="border-top:solid 2px gray; border-right:solid 2px gray"|d<tex>D</tex> для !style="border-top:solid 2px gray"|1!style="border-top:solid 2px gray"|2!style="border-top:solid 2px gray"|3!style="border-top:solid 2px gray"|4!style="border-top:solid 2px gray; border-right:solid 2px gray"|5|style="border-top:solid 2px gray" rowspan=2|Достанем из очереди <tex>S </tex>. Ничего не добавится в очередь и она останется пустой. Алгоритм закончил свое выполнение. Итого в множество <tex>\rightarrow ABCdvarepsilon</tex>-правил входят все нетерминалы, кроме <tex>D</tex>.|-|1|1|1|1|style="border-right:solid 2px gray"|0|0|1|0|0|style="border-right:solid 2px gray"|0|} Если применять алгоритм без модификации с очередью, то действия будут следующие:#* Возьмём множество состоящее из <tex>\varepsilon</tex>-порождающих нетерминалов <tex>B \rightarrow lbrace A|, C\rbrace</tex> для .# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B \rightarrow AC</tex>состоит только из нетерминалов из множества.# Удалим праила Повторим второй пункт для правила <tex>AS\rightarrow \varepsilonABC</tex> и получим множество <tex>\lbrace A, B, C, S \rightarrow \varepsilonrbrace</tex>.# Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.
== Алгоритм поиска удаления ε-порождающих нетерминалов правил из грамматики =='''Вход:''' КС -грамматика <tex> G\Gamma=\langle N,\Sigma, P, S \rangle</tex>.<br/>'''Выход:''' множество КС-грамматика <tex> \Gamma'=\langle N,\Sigma, P', S' \rangle</tex> без <tex>\varepsilon</tex>-порождающих нетерминаловправил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил); <tex>L(\Gamma') = L(\Gamma)</tex>.
# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.# Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы.# Для каждого правила. Составить множество, состоящее вида <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 \ldots B_k \alpha_k \ </tex> (где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, входящих <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы) добавить в левые части таких <tex>P'</tex> все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \leqslant j \leqslant k)</tex>.# Перебираем Удалить все <tex>\varepsilon</tex>-правила грамматики из <tex>GP'</tex>. # Если найдено правило в исходной грамматике <tex>A \rightarrow C_1C_2...C_kGamma</tex>, для которого верно, что каждый выводилось <tex>C_i\varepsilon</tex> принадлежит множеству, то необходимо добавить новый нетерминал <tex>AS'</tex> в множество.# Если на шаге 2 множество изменилось, то повторить шаг 2сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>.
=== Доказательство корректности ===
{{Теорема
|statement = Описанный Если грамматика <tex>\Gamma'</tex> была построена с помощью описанного выше алгоритм находит все алгоритма по грамматике <tex>\varepsilonGamma</tex>-порождающие нетерминалы грамматики , то <tex>GL(\Gamma') = L(\Gamma)</tex>.
|proof =
Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>\Gamma' : L(\Gamma') = L(\Gamma) \setminus \lbrace \varepsilon \rbrace </tex>.<br/>
Для этого достаточно доказать, что
<tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).
<tex>\Rightarrow</tex>
Пусть <tex>A \underset{\Gamma'}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порождения в грамматике <tex>\Gamma'</tex>, что <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex>.<br/>
'''База'''. <tex>A \underset{\Gamma'}{\Rightarrow} w</tex>.<br/>
В этом случае в <tex>\Gamma'</tex> есть правило <tex>A \rightarrow w</tex>. По построению <tex>\Gamma'</tex> в <tex>\Gamma</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, элементы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>\Gamma</tex> есть порождения <tex>A \underset{\Gamma}{\Rightarrow} \alpha \underset{\Gamma}{\Rightarrow}^*w</tex>.<br/>
'''Предположение индукции'''. Пусть из <tex>A \underset{\Gamma'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex>.<br/>
'''Переход'''.
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{\Gamma'}{\Rightarrow}X_1 X_2 \ldots X_k \underset{\Gamma'}{\Rightarrow}^*w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу грамматики <tex>\Gamma</tex> <tex>A \rightarrow Y_1 Y_2 \ldots Y_m</tex>, где последовательность <tex>Y_1 Y_2 \ldots Y_m</tex> совпадает с последовательностью <tex>X_1 X_2 \ldots X_k</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами.<br/>
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2 \ldots w_k</tex>, где <tex>X_i \underset{\Gamma'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{\Gamma'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{\Gamma}{\Rightarrow}^*w_i</tex>, значит <tex>A \underset {\Gamma}{\Rightarrow} Y_1 Y_2 \ldots Y_m \underset{\Gamma}{\Rightarrow}^* X_1 X_2 \ldots X_k \underset{\Gamma}{\Rightarrow}^* w_1 w_2 \ldots w_k = w</tex>.
}}
=== Время работы алгоритма ===
=== Пример ===
Рассмотрим грамматику:
:<tex>\begin{array}{l l} S\rightarrow ABC|DS\\ABCd</tex> :<tex>A\rightarrow a|\varepsilon\\</tex> :<tex>B\rightarrow AC\\</tex> :<tex>C\rightarrow c|\varepsilon\\</tex> D\rightarrow d\end{array}В ней <tex>A</tex>, <tex>B</tex> и <tex>C</tex># Возьмём множество состоящее из являются <tex>\varepsilon</tex>-порождающими нетерминалами.# Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:#* <tex>S\lbrace A, C rightarrow Ad|ABd|ACd|Bd|BCd|Cd|d</tex> для <tex>S \rbracerightarrow ABCd</tex>.# Добавим * <tex>B\rightarrow A|C</tex> в множество, так как правая часть правила для <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.# Повторим второй пункт для правила Удалим праила <tex>SA\rightarrow ABC\varepsilon</tex> и получим множество <tex>C\lbrace A, B, C, S rightarrow \rbracevarepsilon</tex>.# Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
== Литература Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Wikipedia — Chomsky normal form]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Нормальные формы КС-грамматик]]
