Изменения

|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>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 \le leqslant j \le leqslant k)</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>\Rightarrow)</tex><br\>Пусть <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...\ldots 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...\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{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...\ldots Y_m \underset{G\Gamma}{\Rightarrow}^* X_1 X_2...\ldots X_k \underset{G\Gamma}{\Rightarrow}^* w_1 w_2...\ldots w_k = w</tex>.

<tex>\Leftarrow)</tex><br/>Пусть <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\Gamma</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...\ldots Y_m \underset{G\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{G\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{G\Gamma}{\Rightarrow}^*w</tex>. <tex>p \ge geqslant 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2} ... \ldots 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} ... \ldots 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>.

== Алгоритм поиска &epsilon;-порождающих нетерминалов = Время работы алгоритма ==='''ВходРассмотрим грамматику <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> GT_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 \langle Nright|})</tex>.<br>Рассмотрим теперь грамматику с устраненными [[Удаление_длинных_правил_из_грамматики|длинными правилами]]. После применения данного алгоритма,который работает за <tex>O(\left| \Gamma \Sigmaright|)</tex>, Pв грамматике станет на <tex>O(\left| \Gamma \right|)</tex> больше правил, S \rangleно при этом все они будут размером <tex>O(1)</tex>.Итого по-прежнему <tex>\left| \Gamma \right| = O(n)<br/tex>'''Выход:''' множество . Однако алгоритм удаления <tex>\varepsilon</tex>-порождающих правил будет работать за <tex>O(\left| \Gamma \right|)</tex>, поскольку для каждого правила можно будет добавить только <tex>O(1)</tex> сочетаний нетерминалов.

# Найти все === Пример ===Рассмотрим грамматику::<tex>S\varepsilonrightarrow ABCd</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.# Перебираем правила грамматики <tex>G</tex>. Если найдено правило :<tex>A \rightarrow C_1C_2...C_ka|\varepsilon</tex>, для которого верно, что каждый :<tex>C_iB\rightarrow AC</tex> принадлежит множеству, то добавить :<tex>AC\rightarrow c|\varepsilon</tex> в множество.# Если на шаге 2 множество изменилось, то повторить шаг 2.

=== Доказательство корректности ===В ней <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются <tex>\varepsilon</tex>-порождающими нетерминалами.{{Теорема# Переберём для каждого правила все возможные сочетания &epsilon;-порождающих нетерминалов и добавим новые правила:#* <tex>S\rightarrow Ad|statement = Описанный выше алгоритм находит все ABd|ACd|Bd|BCd|Cd|d</tex> для <tex>S \rightarrow ABCd</tex>#* <tex>B \rightarrow A|C</tex> для <tex>B \rightarrow AC</tex># Удалим праила <tex>A\rightarrow \varepsilon</tex>-порождающие нетерминалы грамматики и <tex>GC\rightarrow \varepsilon</tex>.|proof =

Для доказательства корректности алгоритма достаточно показать, что, если множество В результате мы получим новую грамматику без <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все правил: :<tex>S\varepsilonrightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d</tex>:<tex>A\rightarrow a</tex>:<tex>B\rightarrow A|AC|C</tex>:<tex>C\rightarrow c</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>_дерево_разбора|Контекстно-порождающие нетерминалы.свободные грамматики]]}}* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]

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