Изменения

== Основные Используемые определения == 

|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами''' (англ. ''<tex>\varepsilon</tex>-rule'').

|definition = Назовем КС-грамматику Нетерминал <tex>G=(N,\Sigma, P, S)A</tex> грамматикой без называется '''<tex>\varepsilon</tex>-правил порождающим''' (или неукорачивающей), если либо<br/>:(1) <tex>P</tex> не содержит англ. ''<tex>\varepsilon</tex>-правилgenerating''), либо :(2) есть точно одно если <tex>A \varepsilon</tex>-правило <tex>S \to Rightarrow^* \varepsilon</tex> и <tex>S</tex> не встречается в правых частях остальных правил из <tex>P</tex>.

 == Алгоритм поиска &epsilon;-порождающих нетерминалов =='''Вход:''' КС-грамматика <tex> \Gamma=\langle N,\Sigma, P, S \rangle</tex>.<br/>'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов. # Найти все <tex>\varepsilon</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.# Перебираем правила грамматики <tex>\Gamma</tex>. Если найдено правило <tex>A \rightarrow C_1C_2 \ldots C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>A</tex> в множество.# Если на шаге 2 множество изменилось, то повторить шаг 2. === Доказательство корректности ==={{ОпределениеТеорема|definition statement = Нетерминал Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>\Gamma</tex>A.|proof = Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-порождающие нетерминалы. Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2 \ldots 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>A \Rightarrow^* varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.

=== Поиск &epsilon;-порождающих нетерминалов ===''Схема алгоритма'Вход:'':1) Если ' КС-грамматика <tex>A \rightarrow Gamma=\langle N,\Sigma, P, S \varepsilonrangle</tex> — правило грамматики .<texbr/>G'''Выход:''' КС-грамматика </tex>\Gamma'=\langle N, то <tex>A\Sigma, P', S' \rangle</tex> —без <tex>\varepsilon</tex>-порождающий нетерминал.:2) Если правил (может присутствовать правило <tex>B S \rightarrow C_1C_2...C_k</tex> — правило грамматики <tex>G</tex>, где каждый <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий нетерминал, то но в этом случае <tex>BS</tex> — не встречается в правых частях правил); <tex>L(\varepsilonGamma') = L(\Gamma)</tex>-порождающий нетерминал.

|statement = Нетерминал Если грамматика <tex>A\Gamma'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>\Gamma</tex>, то <tex>L(\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>&nbsp; и&nbsp; <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/>|proof Цепочку <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>\Leftarrow</tex><br/>Пусть <tex>A \underset{\Gamma}{\Rightarrow}^*w</tex>&nbsp; и&nbsp; <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 \rightarrowY_{i_1} Y_{i_2} \ldots Y_{i_p}</tex> является правилом в <tex>\varepsilonGamma'</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>A \Rightarrow^*\varepsilonS</tex> за вместо <tex>nA</tex> шагов. Тогда первых шаг порождения в утверждение (*), видим, что <tex>A w \in L(\rightarrow C_1C_2...C_kGamma)</tex>, где для <tex>C_i w \Rightarrow^* ne \varepsilon</tex> за менеетогда и только тогда, чем когда <tex>nw \in L(\Gamma')</tex> шагов. По индукционному предположению каждый нетерминал Так как после выполнения шага 5 алгоритма в <tex>C_i\Gamma'</tex> обнарудивается как могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС-порождающий. Тогда нетерминал грамматикой <tex>A\Gamma'</tex> обнаружиться вторым пунктом алгоритма как , совпадает с языком, задаваемым КС-грамматикой <tex>\varepsilonGamma</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>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> G=. Таким образом в худшем случае алгоритм работает за <tex>O(2^{\left| \Gamma \right|})</tex>.<br>Рассмотрим теперь грамматику с устраненными [[Удаление_длинных_правил_из_грамматики|длинными правилами]]. После применения данного алгоритма, который работает за <tex>O(N\left| \Gamma \right|)</tex>,в грамматике станет на <tex>O(\left| \Gamma \Sigmaright|)</tex> больше правил, Pно при этом все они будут размером <tex>O(1)</tex>. Итого по-прежнему <tex>\left| \Gamma \right| = O(n)</tex>. Однако алгоритм удаления <tex>\varepsilon</tex>-правил будет работать за <tex>O(\left| \Gamma \right|)</tex>, Sпоскольку для каждого правила можно будет добавить только <tex>O(1)</tex>сочетаний нетерминалов.

''Выход.'' КС грамматика === Пример ===Рассмотрим грамматику::<tex>S\rightarrow ABCd</tex>:<tex>A\rightarrow a|\varepsilon</tex>:<tex> G'=(N,B\Sigma, P', S) rightarrow AC</tex>: L(G) = L(G') - {<tex>C\rightarrow c|\varepsilon}</tex>.

''Схема алгоритма:'':1) Найти все В ней <tex>\varepsilonA</tex>-порождаюшие нетерминалы.:2) Удалить все , <tex>\varepsilonB</tex>-правила из и <tex>PC</tex>.:3) Рассмотрим правила вида (*)являются <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_kvarepsilon</tex>, где -порождающими нетерминалами.# Переберём для каждого правила все возможные сочетания &epsilon;-порождающих нетерминалов и добавим новые правила:#* <tex>S\alpha_irightarrow Ad|ABd|ACd|Bd|BCd|Cd|d</tex> — последовательности из терминалов и нетерминалов, для <tex>B_jS \rightarrow ABCd</tex> — #* <tex>B \varepsilonrightarrow A|C</tex>-порождающие нетерминалы. Добавить все возможные правила вида (*), в которых либо присутствует, либо отсутствует для <tex>B_jB \rightarrow AC</tex>, кроме правила # Удалим праила <tex>A \rightarrow \varepsilon</tex>. Такое правило может возникнуть, если все и <tex>C\alpha_i = rightarrow \varepsilon</tex>.

== Доказательство корректности алгоритма =={{Утверждение|statement= <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> <tex>(A \ne S')</tex>&nbsp; тогда и только тогда, когда <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>|proof=<tex>\Rightarrow</tex><br\>Пусть <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>. Несомненно, <tex>w \ne \varepsilon</tex>, поскольку <tex>G'</tex> - грамматика В результате мы получим новую грамматику без <tex>\varepsilon</tex>-правил и <tex>A \ne S'</tex>.<br/>Докажем индукцией по длине порождения, что <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>.<br/> Обозначим длину порождения за <tex>p</tex>.:'''Базис'''. <tex>p = 1</tex><br/>В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. Согласно конструкции <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha-</tex> это <tex>w</tex>, символы которой, возможно, перемежаются <tex>\varepsilon-</tex> порождающими переменными. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \overset{*}{\underset{G}{\Rightarrow}}w</tex>, где на шагах после первого, из всех переменных в цепочке <tex>\alpha</tex> выводиться <tex>\varepsilon</tex>.<br/>:'''Предположение'''. Пусть <tex>[A \overset{*}{\underset{G'}{\Rightarrow}}w</tex> <tex>(A \ne S')]</tex>&nbsp; <tex>\Rightarrow [A \overset{*}{\underset{G}{\Rightarrow}}w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon]</tex> верно для <tex>p < nrightarrow Ad|ABd|ACd|ABCd|Bd|BCd|Cd|d</tex>.<br/>:'''Переход'''. <tex>p = n</tex><br/>Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k\overset{*}{\underset{G'}{\Rightarrow}}w</tex>, где <tex>X_i \in N \cup \Sigma </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>Y_1 Y_2...Y_m</tex>, возможно, перемежаются <tex>\varepsilon-</tex> порождающими переменными.<br/>Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex>. Если <tex>X_i</tex> есть терминал, то <tex>w = X_i</tex>, a если переменная, то порождение <tex>X_i \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex> содержит менее <tex>n</tex> шагов.<br/> По предположению <tex>X_i \overset{*}{\underset{G}{\Rightarrow}}w_i</tex>.<br/>Теперь построим соответствующее порождение в <tex>G</tex>.<br/>:<tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \overset{*}{\underset{G}{\Rightarrow}} X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}} w_1 w_2...w_k = w</tex><br/>Ч.т.д.<br/><tex>\Leftarrow</tex><br/>Пусть <tex>A \overset{*}{\underset{G}{\Rightarrow}}w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon</tex>.<br/> Докажем индукцией по длине порождения, что <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>.<br/> Обозначим длину порождения за <tex>p</tex>.<br/>:'''Базис'''. <tex>p = 1</tex><br/><tex>A B\rightarrow w</tex> является правилом в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, эта же правило будет и в <tex>G'</tex>, поэтому <tex>A \overset{*}{\underset{G'}{\Rightarrow}}w</tex>.:'''Предположение'''. Пусть <tex>[A \overset{*}{\underset{G}{\Rightarrow}}w</tex>&nbsp; и&nbsp; <tex>w \ne \varepsilon] \Rightarrow [A \overset{*}{\underset{G'}{\Rightarrow}}w (A \ne S')]|AC|C</tex>&nbsp; верно для <tex>p < n</tex>.<br/>:'''Переход'''. <tex>p = n</tex><br/>Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m\overset{*}{\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 \overset{*}{\underset{G'}{\Rightarrow}}w_i</tex>.<br/>Пусть <tex>X_1, X_2, ... X_k</tex> будут теми из <tex>Y_j</tex>(в порядке записи), для которых <tex>w_i \ne \varepsilon</tex>. <tex>k \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>.<br/> Таким образом <tex>A C\rightarrow X_1 X_2 ... X_kc</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>. Утверждаем, что <tex> X_1 X_2...X_k \overset{*}{\underset{G}{\Rightarrow}}w</tex>, поскольку только <tex>Y_j</tex>, которых нет среди <tex>X_1, X_2, ... X_k</tex>, использованы для порождения <tex>\varepsilon</tex> и не вносят ничего в порождение <tex>w</tex>.Так как каждое из порождений <tex>Y_j \overset{*}{\underset{G}{\Rightarrow}}w_j</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что если <tex>w_j \ne \varepsilon</tex>, то <tex>Y_j \overset{*}{\underset{G'}{\Rightarrow}}w_j</tex>.<br/>Таким образом <tex>A \underset{G'}{\rightarrow} X_1 X_2 ... X_k \overset{*}{\underset{G'}{\Rightarrow}} w</tex>.<br/>Ч.т.д.}}

Теперь можно доказать корректность:{{Утверждение|statement=Алгоритм корректен: <tex>L(G)=L(G')</tex>|proofИсточники информации ==Подставив <tex>S</tex> вместо <tex>A</tex> * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в утверждении выше, видимтеорию автоматов, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда языков и только тогдавычислений''', когда <tex>w \in L(G')</tex>2-е изд. : Пер. с англ.<br/> Очевидно— Москва, Издательский дом «Вильямс», что <tex>\varepsilon \in L2002. — С. 273: ISBN 5-8459-0261-4 (Gрус.)<* [http:/tex> тогда и только тогда, когда <tex>\varepsilon \in L(G')</tex>en.wikipedia.<brorg/> Таким образом, <tex>L(G)=L(G')<wiki/tex>. }}Chomsky_normal_form Wikipedia — Chomsky normal form]