chapter-6.tex

\chapter{Контекстно"/свободные языки}
\label{cfg-intro}

\section{Деревья выводов в КС"/грамматиках}
\label{Chapter6-trees}

В грамматике может быть несколько выводов, эквивалентных в том смысле, что во всех них применяются одни и те же правила в одних и тех же местах, но в различном порядке, в случае КС-грамматик можно ввести удобное графическое представление класса эквивалентных выводов, называемое деревом вывода.

Далее мы будем использовать некоторые стандартные понятия теории графов: (ориентированное!) дерево, поддерево, корень, доминирование, помеченное дерево, упорядоченное дерево и~т.~п. Предполагается, что читателю эти понятия известны.

Сечением дерева $D$ назовем такое множество $C$ вершин дерева $D$. что выполняются следующие свойства: 
\begin{enumerate}
\item никакие две вершины из $C$ не лежат на одном пути из корня в дереве $D$; 
\item ни одну вершину дерева $D$ нельзя добавить к $C$, не нарушив первого свойства. 
\end{enumerate}

Множество вершин дерева $D$, состоящее из одного корня, является сечением; листья тоже образуют сечение; остальные сечения можно расположить как бы между этими крайними сечениями.

Помеченное упорядоченное дерево $D$ называется
\mydef{деревом вывода} в КС"/грамматике $G(A)=(N,\Sigma,P,A)$,
если выполнены следующие условия.
\begin{enumerate}

\item Корень дерева $D$ помечен $A$.

\item Если корень дерева имеет единственного потомка, помеченного $\eps$, то этот потомок образует дерево, состоящее из единственной вершины, и $A\to\eps$ --- продукция из множества $P$.

\item Если $D_1, \ldots ,D_k$ --- поддеревья, над которыми доминируют прямые потомки корня дерева, и корень дерева $D_i$ помечен $X_i$, то $A\to X_1 \ldots X_k$ --- продукция из множества $P$. Если при этом $X_i$ --- нетерминал, то дерево $D$ должно быть деревом вывода в грамматике $G(X_i)=(N,\Sigma,P,X_i)$, а если $X_i$ --- терминал, то дерево $D_i$ состоит из единственной вершины, помеченной $X_i$.
\end{enumerate}

Далее будем рассматривать естественное упорядочение листьев упорядоченного дерева --- <<слева направо>>. Кроной дерева вывода назовем слово, которое получится, если выписать слева направо метки листьев. Определим крону $\omega$ сечения $C$ дерева $D$ как слово, которое получается конкатенацией (в порядке слева направо) меток вершин, образующих сечение $C$.

\begin{mylemma}
\label{lemma-oSech}
Пусть $S=\alpha_0\To\alpha_1\To \ldots \To \alpha_n$ --- вывод слова $\alpha_n$ в КС"/грамматике $G=(N,\Sigma,P,S)$. Тогда в $G$ можно построить дерево вывода $D$, для которого $\alpha_n$ --- крона, а $\alpha_0,\alpha_1,\ldots ,\alpha_{n-1}$ --- набор крон некоторых сечений.
\end{mylemma}

\begin{myproof}
Построим такую последовательность деревьев выводов $D_i$, где $0\le i\le n$, что --- крона дерева $D_i$.

Пусть $D_0$ --- дерево, состоящее из единственной вершины, помеченной начальным нетерминалом $S$.

Предположим теперь, что дерево $D_i$ с нужными свойствами уже построено, и по нему построим дерево $D_{i+1}$. Допустим, что $\alpha_i=\beta_iA\gamma_i$ и после применения продукции $A\to X_1X_2 \ldots X_k$ получается слово $\alpha_{i+1}=\beta_iX_1X_2 \ldots X_k\gamma_i$. Дерево $D_{i+1}$ построим при помощи $D_i$ добавлением к листу, помеченному выделенным вхождением $A$ (он является ($|\beta_i|+1$)-м символом кроны дерева $D_i$), $k$ прямых потомков, которые помечаются $X_1, X_2, \ldots , X_k$. Ясно, что $\alpha_{i+1}$ --- крона дерева $D_{i+1}$.

Итак, $D_n=D$ --- искомое дерево вывода, a $\alpha_0,\alpha_1, \ldots , \alpha_{n-1}$ --- набор крон сечений этого дерева.
\end{myproof}

\begin{mylemma}
\label{lemma-oKrone}
Пусть $G=(N,\Sigma,P,S)$ --- КС-грамматика, a $D$ --- дерево вывода в $G$ с кроной $\alpha$. Тогда $\alpha\in L(G)$.
\end{mylemma}

\begin{myproof}
Пусть $C_0,C_1,C_2, \ldots , C_n$ --- такая последовательность сечений дерева $D$, что выполняются следующие условия:

\begin{enumerate}
\item $C$ содержит только корень дерева $D$;

\item $C_{i+1}$ для $0\le i<n$ получается из $C_i$ заменой одной нетерминальной вершины ее прямыми потомками;

\item $C_n$ --- множество листьев дерева $D$.
\end{enumerate}

Ясно, что хотя бы одна такая последовательность существует. Если $\alpha_i$ --- крона сечения $C_i$, то $S=\alpha_0\To \alpha_1\To \ldots \To \alpha_n=a$ --- вывод слова $\alpha$ из $S$ в $G$. Поэтому $\alpha\in L(G)$.
\end{myproof}

Непосредственным следствием лемм~\ref{lemma-oSech} и~\ref{lemma-oKrone} является

\begin{mytheorem}
\label{theorem-SechKrona}
Пусть $G=(N,\Sigma,P,S)$ --- КС-грамматика. $S\To^*\alpha$ тогда и только тогда, когда в $G$ существует дерево вывода с кроной $\alpha$.
\end{mytheorem}

По одному дереву вывода с кроной $\alpha$ можно построить разные выводы в грамматике, для которых $S\To^*\alpha$; среди всех таких выводов два вызывают особый интерес. Именно, если в доказательстве леммы~\ref{lemma-oKrone} сечение $C_{i+1}$ получается из $C_i$ заменой самой левой нетерминальной вершины в $C_i$ ее прямыми потомками, то соответствующий вывод $S=\alpha_0$, $\alpha_1, \ldots , \alpha_n$ называется левым выводом слова $\alpha_n$ из $\alpha_0$ в грамматике $G$. Правый вывод определяется аналогично. Заметим, что и левый и правый выводы определяются по дереву однозначно.

Если $S=\alpha_0,\alpha_1, \ldots , \alpha_n=\omega$ --- левый вывод терминального слова $\omega$ и $\alpha_i$ $(0\le i<n)$ имеет вид $x_iA_i\beta_i$, где $x_i\in\Sigma^*$, $A_i\in N$, $\beta_i\in(N\cup\Sigma)^*$, то каждое следующее слово $\alpha_{i+1}$ левого вывода получается из предыдущего слова $\alpha_i$ заменой самого левого нетерминала $A_i$ правой частью некоторой продукции. В правом выводе заменяется самый правый нетерминал.

\begin{myproblem}
Рассмотрим грамматику $G$ из примера~\ref{exampleArithmGrammar}:
\[G_0=(\{E;T;F\}, \{a;+;*;(;)\},P,E),\]
где $P$ состоит из продукций
\[
    E \to E+T \mid T, \qquad
    T \to T*F \mid F, \qquad
    F \to (E) \mid a.
\]
Постройте такое дерево вывода в этой грамматике, кроной которого является слово $a+a$. Укажите левый и правый выводы.
\end{myproblem}

Слово $\alpha$ будем называть левовыводимым в грамматике $G$ и писать $S\To_l^*\alpha$, если существует левый вывод $S=\alpha_0,\alpha_1, \ldots , \alpha_n=\alpha$. Аналогично, слово $\alpha$ будем называть правовыводимым и писать $S\To_r^*\alpha$, если существует правый вывод $S=\alpha_0,\alpha_1, \ldots , \alpha_n=\alpha$. Один шаг левого вывода обозначается через $\To_l$ , а шаг правого вывода --- через $\To_r$.

Если дан вывод $S\To^*\alpha$ в КС"/грамматике $G$, то не всегда можно найти единственное дерево вывода с кроной $\alpha$. Причина этого заключается в том, что есть КС"/грамматики, у которых может быть несколько различных деревьев выводов с одной и той же кроной.

\begin{myproblem}
Пусть $G=(\{S\},\{a,b\},\{S\to aSbS\mid bSaS\mid\eps\},S)$. Постройте разные деревья выводов в этой грамматике, у которых кроной является слово $abab$.
\end{myproblem}

КС-грамматику $G$ называют \mydef{неоднозначной}, если существует хотя бы одно слово $\omega\in L(G)$, которое является кроной двух или более различных деревьев выводов в $G$. В противном случае КС"/грамматика $G$ называется однозначной. Неоднозначность КС"/грамматики можно связать с существованием различных левых и (или) правых выводов.

\begin{myproblem}
Рассмотрим КС-грамматику $G$. Пусть $\omega\in L(G)$, докажите, что следующие утверждения эквивалентны:
\begin{enumerate}
\item $\omega$ --- крона двух различных деревьев выводов в $G$;
\item $\omega$ имеет два различных левых вывода в $G$;
\item $\omega$ имеет два различных правых вывода в $G$.
\end{enumerate}
\end{myproblem}

\section{Проблема непустоты и устранение бесполезных символов}
\label{Chapter6-problemEmptyLang}

Грамматика может, вообще говоря, содержать бесполезные символы и продукции. Например, в грамматике $G=(\{S,A\},\{a,b\},P,S)$, где $P=\{S\to a;A\to b\}$, нетерминал $A$ и терминал $b$ не могут появиться ни в каком выводимом слове. Таким образом, и эти символы, и продукцию $(A\to b)$ можно устранить из грамматики $G$, не изменив языка $L(G)$.

Дадим точное определение. Назовем символ $X\in N\cup\Sigma$ бесполезным в КС"/грамматике $G=(N,\Sigma,P,S)$, если в ней невозможен вывод вида $S\To^*\omega Xy\To^*\omega xy$, где $\omega,x,y\in\Sigma^*$.

Ясно, что если язык $L(G)$ пуст, то все символы бесполезны. Построим алгоритм~\ref{algo-KS-NonEmptyLang}, выясняющий, может ли нетерминал порождать какие-нибудь терминальные слова. Далее будет доказано, что этот алгоритм годится для проверки на непустоту произвольных КС-языков. Таким образом, проблема непустоты для КС"/языков разрешима.

\Algo{Проверка на непустоту}
{\label{algo-KS-NonEmptyLang} КС"/грамматика $G=(N,\Sigma,P,S)$.}
{<<ДА>>, если $L(G)\neq\es$, <<НЕТ>>, если $L(G)=\es$.}
{Рекурсивное построение расширяющейся последовательности специального вида множества $N$.}
{
\item Положить $N_0=\es$, $i=1$.

\item Положить $N_i=\{A\mid A\to\alpha\in P, \alpha\in(N_{i-1}\cup\Sigma)^*)\cup N_{i-1}$.

\item Если $N_i\neq N_{i-1}$, то положить $i=i+1$ и перейти к шагу 2, в противном случае положить $N_\Sigma = N_l$.

\item Если $S\in N_\Sigma$, выдать на печать <<ДА>>, в противном случае --- <<НЕТ>>.
}

Так как $N_\Sigma\subseteq N$, то алгоритм~\ref{algo-KS-NonEmptyLang} должен остановиться самое большее после $|N|+1$ повторений шага~2.

Алгоритм~\ref{algo-KS-NonEmptyLang} строит множество <<стабилизации>> $N_\Sigma$, соответствующее алфавиту $\Sigma$. Аналог этого множества можно определить и для произвольного подмножества $\Omega$ множества $\Sigma\cup\{\eps\}$:
\[
    N_\Omega=\{A\mid A\in N, A\To_G^*\alpha, \alpha\in\Omega^*\}.
\]
Множества такого типа встречаются в различных алгоритмах, поэтому выделим ту часть алгоритма~\ref{algo-KS-NonEmptyLang}, которая позволяет построить $N_\Omega$ (см. алгоритм~\ref{algo-KS-NonEmptyLang-Stab}).

\Algo{Построение множества $N_\Omega$}
{\label{algo-KS-NonEmptyLang-Stab}КС-грамматика $G=(M,\Sigma,P,S)$, $\Omega$ --- подмножество множества $\Sigma\cup\{\eps\}$.}
{Множество $N_\Omega$.}
{Рекурсивное построение расширяющейся последовательности подмножеств специального вида множества $N$.}
{
\item Положить $N_0=\es$, $i=1$.

\item Положить $N_i=\{A\mid A\to\alpha\in P, \alpha\in(N_{i-1}\cup \Omega)^*\}\cup N_{i-1}$.

\item Если $N_i\neq N_{i-1}$, то положить $i=i+1$ и перейти к
шагу~2, в противном случае положить $N_\Omega=N_i.$.
}

Рассмотрим КС-грамматику $G=(N,\Sigma,P,S)$ и займемся теперь обоснованием алгоритма~\ref{algo-KS-NonEmptyLang}.

\begin{mylemma}
\label{lemma-NonEmptyAlgoCorr-1}
Пусть $i\in\{0;1;2;\ldots \}$. Если $A\in N_i$, то $A\To_G^*\omega$ для некоторого слова $\omega=\Sigma^*$.
\end{mylemma}

\begin{myproof}
Применим метод математической индукции по $i$.

Случай $i=0$ не нуждается в доказательстве, так как $N_0=\es$.

Предположим, что утверждение верно для $i=k$, и докажем его для $i=k+1$ Рассмотрим $A\in N_{k+1}$. Если $A$ принадлежит также и $N_k$,то $A\To_G^*\omega$ для некоторого слова $\omega\in\Sigma^*$ в силу индуктивного предположения. Если же $A\in N_{k+1}-N_k$, то существует такая продукция $A\to X_1\ldots X_m$, в которой $X\in\Sigma\cup N_k$. Тогда для каждого $X_j$, можно найти такое слово $\omega_j$, что $X_j\To_G^*\omega_j$: если $X_j\in\Sigma$, то $\omega_j=X_j$, в противном случае существование $\omega_j$ следует из индуктивного предположения. Итак, $A \To X_1\ldots X_m \To_G^*\omega_1X_2\ldots X_m \To_G^* \ldots \To_G^* \omega_1\ldots \omega_m$. (Подчеркнем, что случай $m=0$ на первом шаге, т. е. продукция $A\to \eps$, не составляет исключения.)

Таким образом, лемма верна для произвольного $i$.
\end{myproof}

\begin{mylemma}
\label{lemma-NonEmptyAlgoCorr-2}
Пусть $n\in\{1;2;\ldots\}$. Если $A\To_G^n\omega$ для некоторого слова $\omega\in\Sigma^*$, то существует такое $i\in\{0;1;2;\ldots\}$, что $A\in N_i$.
\end{mylemma}

\begin{myproof}
Применим метод математической индукции по $n$.

В случае $n=1$, очевидно, $i=1$.

Допустим, что утверждение верно для $n=k$, и докажем его для $n=k+1$. Пусть $A\To_g^{k+1}\omega$. Тогда $A\To X_1\ldots X_m\To_G^k\omega$, где слово $\omega=\omega_1\ldots \omega_m$ таково, что $X_j\To_G^{n_j}\omega$ для каждого $j$ и $n_j\le k$ (в дереве вывода $A\To_G^{k+1}\omega$ слово $\omega_j$ является кроной поддерева с корнем $X_j$). В силу индуктивного предположения, если $X_j\in N$, то $X_j\in N_{i_j}$ для некоторого $i_j$, а если $X_j\in\Sigma$, то определим $i_j=0$. Пусть $i=1+max(i_1, \ldots , i_k)$. Тогда $A\in N_i$.

Итак, лемма верна для произвольного $n$.
\end{myproof}

\begin{mytheorem}
Алгоритм~\ref{algo-KS-NonEmptyLang} говорит <<Да>> тогда и только тогда, когда $S\To_G^*\omega$ для некоторого слова $\omega$ из $\Sigma^*$.
\end{mytheorem}

\begin{myproof}
Согласно алгоритму~\ref{algo-KS-NonEmptyLang} <<Да>> выводится тогда и только тогда, когда $S\in N_\Sigma$. Для завершения доказательства теоремы теперь достаточно воспользоваться леммами~\ref{lemma-NonEmptyAlgoCorr-1} и~\ref{lemma-NonEmptyAlgoCorr-2} при $A=S$, так как $N_\Sigma=\bigcup_iN_i$.
\end{myproof}

Символ $X\in N\cup\Sigma$ назовем \mydef{недостижимым} в КС"/грамматике $G=(N,\Sigma,P,S)$, если $X$ не появляется ни в одной выводимой цепочке. Иначе говоря, символ $X\in N\cup\Sigma$ достижим, если для него существуют такие слова $\alpha$, $\beta$ из $(N\cup\Sigma)^*$, что $S\To_G^*\alpha X\beta$. Недостижимые символы являются примерами бесполезных символов; их можно устранить из КС"/грамматики с помощью алгоритма~\ref{algo-DelNonAvailSybmbols}.

\Algo{Устранение недостижимых символов}
{\label{algo-DelNonAvailSybmbols}КС"/грамматика $G=(N,\Sigma,P,S)$.}
{КС"/грамматика $G'=(N,\Sigma,P,S)$, у которой $L(G')=L(G)$ и нет недостижимых символов.}
{Рекурсивное построение расширяющейся последовательности подмножеств специального вида множества $N\cup\Sigma$.}
{
\item Положить $V_0=\{S\}$, $i=1$.

\item  Положить $V_i=\{X\mid (A\to\alpha X\beta)\in P$, $A\in V_{i-1} \}\cup V_{i-1}$.

\item  Если $V_i\neq V_{i-1}$, то положить $i=i+1$ перейти к шагу 2, в противном случае положить $V^S=V_i$.

\item  Построить грамматику $G'=(N,\Sigma,P,S)$, где $N'=V^S\cap N$, $\Sigma '=V^S\cap\Sigma$, а в $P'$ включены те и только те продукции из $P$, которые содержат только символы из $V^S$.
}

Так как $V^S\subseteq N\cup\Sigma$, то алгоритм~\ref{algo-DelNonAvailSybmbols} должен остановиться самое большее после $|N| + |\Sigma|+1$ повторений шага 2. Алгоритмы~\ref{algo-KS-NonEmptyLang} и~\ref{algo-DelNonAvailSybmbols} очень похожи; более того, обосновываются они тоже сходным образом.

\begin{myproblem}
Используя метод математической индукции по $i$, докажите, что существует вывод $S\To_{G'}^i\alpha X\beta$ тогда и только тогда, когда $X\in V_i$
\end{myproblem}

\begin{myproblem}
\label{problem-eqOfLangsWithoutUselessSymbols}
Докажите, что алгоритм~\ref{algo-DelNonAvailSybmbols} по КС-грамматике $G=(N,\Sigma,P,S)$ строит такую КС-грамматику $G'=(N' ,\Sigma',P',S)$, у которой $L(G')=L(G)$ и для всех $X\in N'\cup\Sigma'$ существуют такие слова $\alpha$, $\beta$ из $(N'\cup\Sigma')^*$, что $S\To_{G'}^*\alpha X\beta$. (Другими словами, алгоритм~\ref{algo-DelNonAvailSybmbols} строит новую КС-грамматику $G'=(N',\Sigma',P',S)$ без недостижимых символов, для которой $L(G')=L(G)$.)
\end{myproblem}

\Algo{Устранение бесполезных символов}
{\label{algo-DelUselessSybmbols}КС"/грамматика $G=(N,\Sigma,P,S)$, у которой $L(G)\neq\es$.}
{КС"/грамматика $G'=(N',\Sigma',P',S)$. У которой $L(G')=L(G)$ и в $N'\cup\Sigma'$ нет бесполезных символов.}
{Последовательное применение алгоритма~\ref{algo-KS-NonEmptyLang-Stab} для $\Omega=\Sigma$ и алгоритма~\ref{algo-DelNonAvailSybmbols}.}
{
\item К грамматике $G=(N,\Sigma,P,S)$ применить алгоритм~\ref{algo-KS-NonEmptyLang-Stab} и найти множество $N_\Sigma$; построить грамматику $G_1=(N\cap N_\Sigma,\Sigma,P_1,S)$, где в $P_1$ включены те и только те продукции из $P$, которые содержат только символы из $N\cap N_\Sigma$.

\item К грамматике $G_1=(N\cap N_\Sigma,\Sigma,P_1,S)$ применить алгоритм~\ref{algo-DelNonAvailSybmbols} и построить грамматику $G'=(N',\Sigma',P',S)$.
}

Дадим пояснения к алгоритму~\ref{algo-DelUselessSybmbols} (с.~\pageref{algo-DelUselessSybmbols}) устранения бесполезных символов. На шаге 1 из $G$ устраняются все нетерминалы, которые не могут порождать терминальных слов. Затем на шаге 2 устраняются все недостижимые символы. Каждый символ $X$ результирующей грамматики должен появиться хотя бы в одном выводе вида $S\To^*\omega Xy\To^*\omega xy$. В примере~\ref{example-algosteps} показано, что если сначала применить алгоритм~\ref{algo-DelNonAvailSybmbols}, а потом алгоритм~\ref{algo-KS-NonEmptyLang-Stab}, то в результате может получиться грамматика, содержащая бесполезные символы.

\begin{mytheorem}
\label{theorem-AlgoDelUselessSymbolsCorrectness}
Грамматика $G'$, которую строит алгоритм~\ref{algo-DelUselessSybmbols}, является не содержащей бесполезных символов КС"/грамматикой, и $L(G)=L(G')$.
\end{mytheorem}

\begin{myproof}
При переходе от грамматики $G$ к грамматике $G_1$, исключаются только те нетерминалы и продукции, которые не участвуют в выводах терминальных слов, поэтому $L(G)=L(G_1)$. Равенство $L(G_1)=L(G')$ обсуждалось выше (см. упражнение~\ref{problem-eqOfLangsWithoutUselessSymbols}). Следовательно, $L(G)=L(G')$.

Покажем теперь, что в $G'$ нет бесполезных символов. Предположим, что $A\in N'$ --- бесполезный символ. Тогда по определению бесполезности символа могут представиться два случая:

\begin{enumerate}
\item Вывод $S\To_{G'}^*\alpha A\beta$ ни для каких $\alpha$ и $\beta$ невозможен. Но в этом случае символ $A$ должен был быть устраненным на шаге 2 алгоритма~\ref{algo-DelUselessSybmbols}, что приводит к противоречию.

\item Вывод $S\To_{G'}^*\alpha A\beta$ для некоторых $\alpha$ и $\beta$ возможен, но вывода $A\To_{G'}^*\omega$ для $\omega\in\Sigma'^*$ не существует. Ясно, что если символ $A$ <<проскочил>> шаг 1, то на шаге 2 в рассматриваемой ситуации его уже не устранить. Кроме того, если в этом случае $A\To_G^*\gamma B\delta$, то и символ $B$ не устраним на шаге 2. Итак, предположим, что символ $A$ не устранен на первом шаге, т. е. $A\To_G^*\omega$ для $\omega\in\Sigma^*$. Если возможен вывод $A\To_G^*\gamma B\delta\To_G^*\omega$ то в силу сказанного выше символ $B$ не устраним на шаге 2, это означает, что $A\To_{G'}^*\omega$. Полученное противоречие показывает, что в действительности $A$ устраняется на шаге~1.
\end{enumerate}

Доказательство того, что ни один терминал в $G'$ не может быть бесполезным, проводится аналогично.
\end{myproof}

\begin{myexample}
\label{example-algosteps}
Рассмотрим грамматику $G=(\{S;A;B\},\{a:b\},P,S)$, где $P$ состоит из продукций
\[
S\to a \mid A; \quad A\to AB; \quad B\to b.
\]
Применим к $G$ алгоритм~\ref{algo-DelUselessSybmbols}. На шаге 1 этого алгоритма получим: $N_\eps\{S;B\}$ и $G=(\{S;B\},\{a;b\},\{S\to a;B\to b\},S)$. На втором шаге, применив алгоритм~\ref{algo-DelNonAvailSybmbols}, получим: $V_2=V_1=\{S,a\}$. Итак, $G'=(\{S\},\{a\},\{S\to a\},S)$.

Теперь в алгоритме~\ref{algo-DelUselessSybmbols} поменяем местами шаги 1 и 2. После применения к $G$ алгоритма~\ref{algo-DelNonAvailSybmbols} грамматика не изменится в силу того, что все символы достижимы. Последующее применение алгоритма~\ref{algo-KS-NonEmptyLang-Stab} дает $N_\eps=\{S;B\}$. Следовательно, результирующей будет грамматика $G$ , отличная от $G'$ .
\end{myexample}

\section{Построение приведенной КС"/грамматики}
\label{Chapter6-normalizeGrammar}

В пункте~\ref{Chapter6-problemEmptyLang} было показано, как, не меняя языка, устранить из КС"/грамматики все бесполезные символы. Целью этого пункта является устранение из КС-грамматики <<нехороших>> продукций.

Назовем КС-грамматику $G=(N,\Sigma,P,S)$ \mydef{неукорачивающейся грамматикой}, если либо $P$ вовсе не содержит $\eps$-продукции типа $A\to\eps$, либо в $P$ есть точно одна $\eps$-продукция $S\to\eps$ и $S$, при этом не встречается в правых частях остальных продукций.

\Algo{Преобразование КС"/грамматики в неукорачивающуюся форму}
{\label{algo-GrammarToEpsFreeGrammar}КС-грамматика $G=(N,\Sigma,P,S)$.}
{Неукорачивающаяся КС"/грамматика $G'=(N',\Sigma,P',S')$, у которой \[L(G')=L(G).\]}
{«Устранение перегородок».}
{
\item Применить алгоритм~\ref{algo-KS-NonEmptyLang-Stab} для $\Omega=\{\eps\}$ и построить множество
\[
    N_\eps=\{A\mid A\in N, A\To_G^*\eps\}.
\]

\item Если
\[
    (A\to\alpha_0B_1\alpha_1B_2\alpha_2 \ldots B_k\alpha_k)\in P,
\]
где $k\ge 0$, $B_i\in N_\eps$ и ни один символ в словах $\alpha_j$ не принадлежит $N_\eps$, то включить в $P'$ все продукции вида $A\to\alpha_0X_1\alpha_1X_2 \ldots \alpha_{k-1}X_k\alpha_k$, где $X_i$ --- либо $B_i$, либо $\eps$, исключая продукцию $A\to\eps$ (это могло бы произойти в случаe, если все $\alpha_i$, равны $\eps$).

\item Если $S\in N_\eps$ , то ввести новый нетерминал $S'$ и дополнительно включить в $P'$ продукции $(S'\to S|\eps)$, в противном случае положить $N'=N, S'=S$.

\item Положить $G'=(N',\Sigma,P',S')$.
}

\begin{mytheorem}
\label{theorem-AlgoDelEpsProductionsCorrectness}
Грамматика $G'$, которую строит алгоритм~\ref{algo-GrammarToEpsFreeGrammar} по КС"/грамматике $G$, является неукорачивающейся КС"/грамматикой и $L(G)=L(G')$.
\end{mytheorem}

\begin{myproof}
Тот факт, что грамматика $G'$ является неукорачивающейся, вытекает из простого анализа алгоритма.

Применяя метод математической индукции по длине слова $\omega$, можно доказать следующее вспомогательное утверждение: для произвольного слова $\omega$ из $\Sigma^*\backslash\{\eps\}$ и буквы $A$ из $N$ вывод $A\To_{G'}^*$ возможен тогда и только тогда, когда $A\To_G^*\omega$. Применим это утверждение для $S=A$ и $\omega\in\Sigma^*\backslash\{\eps\}$ получим: $\omega\in L(G)$ тогда и только тогда, когда $\omega\in L(G')$. Заметим теперь, что $\eps\in L(G)$ тогда и только тогда, когда $\eps\in L(G')$. Таким образом, $L(G)=L(G')$.
\end{myproof}

\begin{myproblem}
\label{problem-GrammarToEpsFreeGrammarWOUselessSymbols}
Докажите, что если на вход алгоритма~\ref{algo-GrammarToEpsFreeGrammar} подается КС"/грамматика без бесполезных символов, то и на выходе алгоритма получается такая же грамматика.
\end{myproblem}

\begin{myexample}
Рассмотрим контекстно"/свободную грамматику
\[
    G=(\{S;A;B\},\{0;1\},P,S),
\]
где $P$ состоит из продукций
\[
	S \to 0A \mid 1B \mid \eps, \qquad
    A \to AB \mid 0 \mid \eps, \qquad
    B \to 0 \mid A.
\]
Применим к грамматике $G$ алгоритм~\ref{algo-GrammarToEpsFreeGrammar} и получим неукорачивающуюся КС-грамматику $G'=(\{S';S;A;B\},\{0;1\},P,S)$, где $P'$ состоит из продукций
\begin{align*}
    S' &\to S \mid \eps, &
    S  &\to 0A \mid 0 \mid 1B \mid 1, \\
    A  &\to AB \mid A \mid B \mid 0, &
    B  &\to 0 \mid A.
\end{align*}
\end{myexample}

Другое полезное преобразование грамматик --- устранение продукций вида $A\to B$, где $A$ и $B$ --- нетерминалы: такие продукции далее будем называть \mydef{цепными}.

\Algo{Устранение цепных продукций}
{\label{algo-DelCyclicProductions}Неукорачивающаяся КС"/грамматика $G=(N,\Sigma,P,S)$.}
{Неукорачивающаяся КС"/грамматика $G'=(N',\Sigma',P',S')$ без цепных продукций, у которой $L(G')=L(G)$.}
{Для каждого $A$ из $N$ строится подмножество $N^A=\{B\mid A\To^*B)\}$ множества $N$, и на основе этого конструируется новая грамматика.}
{
\item
Для каждого $A$ из $N$ построить $N^A=\{B\mid A\To^*B\}$ следующим образом.
\begin{enumerate}[leftmargin=1cm]
\item Положить $N_0=\{A\}$ и $i=1$.

\item Положить $N_i=\{C\mid (B\to C)\in P$ и $B\in N_{i-1}\}\cup N_{i-1}$.

\item Если $N_i\neq N_{i-1}$, то положить $i=i+1$ и повторить шаг 1.2, в противном случае положить $N^A=N_i$.
\end{enumerate}

\item
Построить $P'$ так: если продукция $B\to\alpha$ принадлежит $P$ и не является цепной, то включить в $P'$ продукцию $(A\to\alpha)$ для всех таких $A$, что $B\in N^A$.

\item
Положить $G'=(N,\Sigma,P',S)$.
}
\begin{mytheorem}
\label{theorem-AlgoDelEpsProductionsCorrectnessWOEpsProducts}
Грамматика $G'$, которую строит алгоритм~\ref{algo-DelCyclicProductions} по неукорачивающейся КС"/грамматике $G$, является неукорачивающейся КС"/грамматикой без цепных продукций и $L(G)=L(G')$.
\end{mytheorem}

\begin{myproof}
Тот факт, что грамматика $G'$ является неукорачивающейся и не имеет цепных продукций, вытекает из простого анализа алгоритма.

Покажем, что $L(G')\subseteq L(G)$. Пусть $\omega\in L(G')$. Тогда в грамматике $G'$ существует вывод $S\To^1\alpha_0 \To^1 \alpha_1 \To^1 \ldots \To^1 \alpha_n = \omega$. Если при переходе от некоторого $\alpha_i$ к $\alpha_{i+1}$ применяется продукция $A\to\beta$ из $P'$, то тогда существует такой символ $B\in N$ (не исключено, что $B=A$), что $A\To_G^*B\To_G\beta$. Таким образом, $A\To_G^*\beta$ и, следовательно, $\alpha_i\To_G^*\alpha_{i+1}$. Отсюда следует, что $S\To_G^*\omega\in L(G)$, так что $L(G')\subseteq L(G)$.

Теперь покажем, что $L(G)\subseteq L(G')$; причем далее мы будем пользоваться понятиями, которые обсуждались в конце раздела~\ref{Chapter6-trees}. Пусть $\omega\in L(G)$ и $S=\alpha_0\To_l\alpha_1\To_l\ldots\To_l\alpha_n=\omega$ --- левый вывод слова $\omega$ в грамматике $G$. Рассмотрим подпоследовательность $i_1, i_2, \ldots , i_k$ последовательности $1, 2, \ldots , n$, состоящую в точности из тех номеров $j$, для которых на шаге $\alpha j_{j-1}\To_l\alpha_j$ вывода $S=\alpha_0\To_l\alpha_1\To_l\ldots\To_l\alpha_n=\omega$ применяется нецепная продукция. В частности, $i_k=n$, так как вывод терминального слова не может оканчиваться цепной продукцией. Так как мы рассматриваем левый вывод, то последовательные применения нескольких исключительно цепных продукций заменяют нетерминальный символ, занимающий одну и ту же позицию в левовыводимых словах. Используя конструкцию $P$, отсюда получаем:
\[
S\To_{G'}\alpha_{i_1}\To_{G'}\alpha_{i_2}\To_{G'}\ldots \To_{G'} \alpha_{i_k}=\omega.
\]
Таким образом, $\omega\in L(G')$ и, следовательно, $L(G)\subseteq L(G')$.

В итоге получаем: $L(G')=L(G)$.
\end{myproof}

С точки зрения анализа бесполезности символов алгоритм~\ref{algo-DelCyclicProductions}
является <<плохим>>.

\begin{myexample}
Рассмотрим неукорачивающуюся КС"/грамматику 
\[G=(\{S;A\},\{a\},\{S\to A;A\to a\},S),\]
у которой нет бесполезных символов. Применяя к ней алгоритм~\ref{algo-DelCyclicProductions}, получаем грамматику $G=(\{S;A\},\{a\},\{S\to a;A\to a\},S)$ с бесполезным символом $A$.
\end{myexample}

\begin{myexample}
Рассмотрим неукорачивающуюся КС"/грамматику
\[
    G'=(\{W;S;A;B\},\{0;1\},P',W).
\]
где $P'$ состоит из продукций
\begin{align*}
	W & \to S \mid \eps, &
	S &\to 0A \mid 0 \mid 1B \mid 1, \\
    A &\to AB \mid A \mid B \mid 0, &
	B &\to 0.
\end{align*}
Применим к грамматике $G$ алгоритм~\ref{algo-DelCyclicProductions}  и получим неукорачивающуюся КС"/грамматику $G'=(\{W;S;A;B\},\{0;1\},P',W)$, где $P'$ состоит из продукций
\begin{align*}
	W &\to \eps \mid 0A \mid 0 \mid 1B \mid 1, &
    S &\to 0A \mid 0 \mid 1B \mid 1, \\
    A &\to AB \mid 0, &
    B &\to 0,
\end{align*}
среди которых нет цепных.

Легко обнаружить, что построенная грамматика $G'$ имеет бесполезные символы. Применим к грамматике $G'$ алгоритм~\ref{algo-DelUselessSybmbols} и получим неукорачивающуюся КС"/грамматику $G=(\{W;S;A;B\},\{0;1\},P',W)$, где $P'$ состоит из продукций
\begin{align*}
	W &\to \eps \mid 0A \mid 0 \mid 1B \mid 1, &
    A &\to 0, &
    B &\to 0.
\end{align*}
У нее нет ни цепных продукций, ни бесполезных символов.
\end{myexample}

\begin{myproblem}
\label{problem-GrammarToEpsFreeGrammarWOCyclicSymbols}
Докажите, что если на вход алгоритма~\ref{algo-DelUselessSybmbols} подается неукорачивающаяся КС"/грамматика без цепных продукций, то на выходе алгоритма получится неукорачивающаяся КС"/грамматика без бесполезных символов и цепных продукций.

КС"/грамматика $G=(N,\Sigma,P,S)$ называется грамматикой без циклов, если в ней нет выводов $A\To^*A$ для $A\in N$.
\end{myproblem}

\begin{myproblem}
Докажите, что если неукорачивающаяся КС"/грамматика $G=(N,\Sigma,P,S)$ не имеет цепных продукций, то в ней нет циклов. Существуют ли КС"/грамматики с циклами, но без цепных продукций?
\end{myproblem}

КС"/грамматика $G$ называется \mydef{приведенной}, если она не имеет бесполезных символов, циклов и является неукорачивающейся.

\Algo{Преобразование произвольной КС"/грамматики в приведенную}
{\label{algo-NormalGrammar}КС"/грамматика $G$.}
{Приведенная КС"/грамматика $G'$, для которой $L(G')=L(G)$.}
{Применение алгоритмов~\ref{algo-DelUselessSybmbols},~\ref{algo-GrammarToEpsFreeGrammar}, ~\ref{algo-DelCyclicProductions}.}
{
\item Применить алгоритм~\ref{algo-DelUselessSybmbols} и по КС"/грамматике $G$ построить КС"/грамматику без бесполезных символов $G_1$, для которой $L(G_1)=L(G)$.

\item Применить алгоритм ~\ref{algo-GrammarToEpsFreeGrammar} и по КС"/грамматике $G_1$ построить неукорачивающуюся КС"/грамматику без бесполезных символов $G_2$, для которой $L(G_2)=L(G_1)$.

\item Применить алгоритм~\ref{algo-DelCyclicProductions} и по КС"/грамматике $G_2$ построить неукорачивающуюся КС"/грамматику без цепных продукций $G_3$, для которой $L(G_3)=L(G_2)$.

\item Применить алгоритм~\ref{algo-DelUselessSybmbols} и по КС"/грамматике $G_3$ построить искомую КС"/грамматику $G'$, для которой $L(G_3)=L(G')$.
}

\begin{mytheorem}
\label{theorem-NormalGrammarAlgoCorrectness}
Грамматика $G'$, которую строит алгоритм~\ref{algo-NormalGrammar} (с.~\pageref{algo-NormalGrammar}) по произвольной КС"/грамматике $G$, является приведенной КС"/грамматикой, и $L(G)=L(G')$.
\end{mytheorem}

\begin{myproof}
Для доказательства этой теоремы достаточно последовательно воспользоваться теоремой~\ref{theorem-AlgoDelUselessSymbolsCorrectness}, теоремой~\ref{theorem-AlgoDelEpsProductionsCorrectness}, упражнением~\ref{problem-GrammarToEpsFreeGrammarWOUselessSymbols}, теоремой~\ref{theorem-AlgoDelEpsProductionsCorrectnessWOEpsProducts}, теоремой~\ref{theorem-AlgoDelUselessSymbolsCorrectness} и упражнением~\ref{problem-GrammarToEpsFreeGrammarWOCyclicSymbols}.
\end{myproof}

\section{Упражнения}
\label{Chapter6Exs}
\subsection*{Построение КС"/грамматик}

Построить КС"/грамматики для следующих языков:
\begin{itemize}
    \item $\{ a^n b^n c^m d^m \mid n, m \in \N \}$;
    \item $\{a^i b^j c^j d^i \mid i, j \in \N\}$;
    \item $\{ a^n b^n c^m d^m \mid n, m \in \N \} \cup \{a^i b^j c^j d^i \mid i, j \in \N\}$.
\end{itemize}


\subsection*{Неоднозначность в КС"/грамматиках}

\begin{enumerate}
    \item Найдите, если это возможно, грамматику без
    неоднозначности для каждого языка из предыдущего упражнения.

    \item Докажите или опровергните контрпримером, что если
     $L_1$ и $L_2$ это КС"/языки,
    не обладающие неоднозначностью, то язык $L_1 \cup L_2$
    тоже не обладает этим свойством.
\end{enumerate}


\subsection*{Алгоритмы для КС-грамматик}

Удалить бесполезные символы в грамматиках с продукциями:
\begin{align*}
    \text{(1) }&
        \begin{aligned}%{l}
            S &\to 0 \mid A,\\
            A &\to AB,\\
            B &\to 1;
        \end{aligned}
        \qquad\qquad
    &
    \text{(2) }&
        \begin{aligned}%{l}
            S &\to AB \mid CA,\\
            A &\to a,\\
            B &\to BC \mid AB,\\
            C &\to aB \mid \varepsilon.
        \end{aligned}
\end{align*}

Преобразовать следующую грамматику к неукорачивающейся:
\[
            S \to  AB,\qquad
            A \to aAA \mid \eps,\qquad
            B \to bBB \mid \eps;
\]

Удалить цепные продукции из грамматики с продукциями:
\begin{align*}
            E &\to T \mid E+T,\\
            T &\to F \mid T*F,\\
            F &\to I \mid (E),\\
            I &\to a \mid b \mid Ia \mid Ib \mid I0 \mid I1.\\
\end{align*}