Изменения

|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\Gamma'=\langle N,\Sigma, P', S' \rangle</tex> без <tex>\varepsilon</tex>-правил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил); <tex>L(G\Gamma') = L(G\Gamma)</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>G\Gamma</tex> выводилось <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>.

|statement = Если грамматика <tex>G\Gamma'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G\Gamma</tex>, то <tex>L(G\Gamma') = L(G\Gamma)</tex>.

Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G\Gamma' : L(G\Gamma') = L(G\Gamma) \setminus \lbrace \varepsilon \rbrace </tex>.<br/>

<tex>A \underset{G\Gamma'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G\Gamma}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).

Пусть <tex>A \underset{G\Gamma'}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/>Докажем индукцией по длине порождения в грамматике <tex>G\Gamma'</tex>, что <tex>A \underset{G\Gamma}{\Rightarrow}^*w</tex>.<br/> '''База'''. <tex>A \underset{G\Gamma'}{\Rightarrow} w</tex>.<br/>В этом случае в <tex>G\Gamma'</tex> есть правило <tex>A \rightarrow w</tex>. По построению <tex>G\Gamma'</tex> в <tex>G\Gamma</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, элементы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G\Gamma</tex> есть порождения <tex>A \underset{G\Gamma}{\Rightarrow} \alpha \underset{G\Gamma}{\Rightarrow}^*w</tex>.<br/>'''Предположение индукции'''. Пусть из <tex>A \underset{G\Gamma'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G\Gamma}{\Rightarrow}^*w</tex>.<br/>

Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G\Gamma'}{\Rightarrow}X_1 X_2...X_k \underset{G\Gamma'}{\Rightarrow}^*w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу грамматики <tex>G\Gamma</tex> <tex>A \rightarrow Y_1 Y_2...Y_m</tex>, где последовательность <tex>Y_1 Y_2...Y_m</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\Gamma'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G\Gamma'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{G\Gamma}{\Rightarrow}^*w_i</tex>, значит <tex>A \underset {G\Gamma}{\Rightarrow} Y_1 Y_2...Y_m \underset{G\Gamma}{\Rightarrow}^* X_1 X_2...X_k \underset{G\Gamma}{\Rightarrow}^* w_1 w_2...w_k = w</tex>.

Пусть <tex>A \underset{G\Gamma}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/> Докажем индукцией по длине порождения в грамматике <tex>G\Gamma</tex>, что <tex>A \underset{G\Gamma'}{\Rightarrow}^*w</tex>.<br/> '''База'''. <tex>A \underset{G\Gamma}{\Rightarrow} w</tex>.<br/>Правило <tex>A \rightarrow w</tex> присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G\Gamma'</tex>, поэтому <tex>A \underset{G\Gamma'}{\Rightarrow}^*w</tex>.<br/>'''Предположение индукции'''. Пусть из <tex>A \underset{G\Gamma}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G\Gamma'}{\Rightarrow}^*w </tex>.<br/>'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G\Gamma}{\Rightarrow}Y_1 Y_2...Y_m \underset{G\Gamma}{\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 \underset{G\Gamma}{\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\Gamma}{\Rightarrow}^*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\Gamma'</tex> по построению <tex>G\Gamma'</tex>.<br/>Так как каждое из порождений <tex>Y_i \underset{G\Gamma}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>, то <tex>Y_i \underset{G\Gamma'}{\Rightarrow}^*w_i</tex>.<br/>Таким образом, <tex>A \underset{G\Gamma'}{\Rightarrow} Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G\Gamma'}{\Rightarrow}^* w</tex>.

Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G\Gamma)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G\Gamma')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G\Gamma'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС -грамматикой <tex>G\Gamma'</tex>, совпадает с языком, задаваемым КС -грамматикой <tex>G\Gamma</tex>.

Рассмотрим грамматику:<tex> \Gamma = </tex>:\begin{array}{l l} :<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\end{array}</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>\begin{array}{l l} S\rightarrow ABCd\\</tex> :<tex>A\rightarrow a|\varepsilon\\</tex> :<tex>B\rightarrow AC\\</tex> :<tex>C\rightarrow c|\varepsilon\end{array}</tex>, в которой  В ней <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются <tex>\varepsilon</tex>-порождающими нетерминалами.

В результате мы получим новую грамматику без <tex>\varepsilon</tex>-правил::<tex>\begin{array}{l l} S\rightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d\\ A\rightarrow a\\ B\rightarrow A|AC|C\\ C\rightarrow c\end{array}</tex> == Алгоритм поиска &epsilon;-порождающих нетерминалов =='''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>.<br/>'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов. # Найти все <tex>\varepsilon</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.# Перебираем правила грамматики <tex>G</tex>. Если найдено правило <tex>A \rightarrow C_1C_2...C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>Aa</tex> в множество.# Если на шаге 2 множество изменилось, то повторить шаг 2. === Доказательство корректности ==={{Теорема|statement = Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>G</tex>.|proof = Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-порождающие нетерминалы. Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило :<tex>B \rightarrow C_1C_2...C_k</tex>, где каждый нетерминал <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.}} === Время работы алгоритма ===Данный алгоритм работает за <tex>O(\leftA| \Gamma \rightAC| ^ 2)C</tex>, однако используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>. === Пример ===Рассмотрим грамматику:<tex>\begin{array}{l l} S\rightarrow ABC|DS\\ A\rightarrow \varepsilon\\ B\rightarrow AC\\ C\rightarrow \varepsilon\\ D\rightarrow d\end{array}</tex># Возьмём множество состоящее из <tex>\varepsilon</tex>-порождающих нетерминалов <tex>\lbrace A, C \rbracec</tex>.# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.# Повторим второй пункт для правила <tex>S\rightarrow ABC</tex> и получим множество <tex>\lbrace A, B, C, S \rbrace</tex>.# Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.

== Литература Источники ==