chapter-7.tex

\chapter{Нормальные формы КС"/грамматик}
\label{normal-cfg}

В предыдущем параграфе было показано, как, не меняя языка, устранить из
КС"/грамматики все бесполезные символы, циклы и сделать ее неукорачивающейся.
В этом параграфе процесс упрощения формы записи грамматик для КС"/языков
будет продолжен. Мы рассмотрим две нормальные формы КС"/грамматик,
каждая из которых используется для решения определенной
практической задачи. Эти задачи будут рассмотрены, соответственно,
в конце этой и следующей главы.


\section{Нормальная форма Хомского}
\label{Chapter7NFH}

Говорят, что КС"/грамматика $G=(N,\Sigma,P,S)$ представлена в
\mydef{нормальной форме Хомского}, если продукции из $P$
имеют один из следующих видов:
\begin{enumerate}
    \item $A\to BC$, где $A,B,C\in N$,

    \item $A\to a$, где $A\in N$, $a\in\Sigma$,

    \item $S\to\eps$, если $\eps\in L(G)$,
\end{enumerate}
причем $S$ не встречается в правых частях продукций.

Для обоснования алгоритма преобразования КС"/грамматики к нормальной форме Хом\-ско\-го (см.~алгоритм~\ref{algo-Homsky}, с.~\pageref{algo-Homsky}) нам понадобится вспомогательное утверждение, которое позволит без изменения языка удалять из грамматики продукции вида $A\to\alpha$. Продукции вида $A\to\alpha$ будем называть \mydef{нетерминальными $A$"/продукциями}.

\begin{mylemma}
\label{lemma-proofOfHomskyMod}
Пусть $G=(N,\Sigma,P,S)$ --- КС"/грамматика и $P$ содержит продукцию $A\to\alpha B\beta$, где $B\in N$, $\alpha,\beta\in(N\cup\Sigma)^*$. Рассмотрим все нетерминальные $B$"/про\-дук\-ции этой грамматики
\[
    B \to \gamma_1 \mid \gamma_2 \mid \ldots \mid \gamma_k |.
\]
Пусть $G'=(N,\Sigma,P',S)$, где
\[
    P' = (P - \{A\to\alpha B\beta\}) \cup
        \{A \to \alpha\gamma_1\beta
            \mid \alpha\gamma_2\beta
            \mid \ldots
            \mid \alpha\gamma_k\beta\}.
\]
Тогда $L(G)=L(G')$.
\end{mylemma}

\begin{myproblem}
Доказать лемму~\ref{lemma-proofOfHomskyMod}.
\end{myproblem}

\begin{mytheorem}
\label{theorem-AlgoHomskyProof}
Пусть $G$ --- произвольная КС"/грамматика. Алгоритм~\ref{algo-Homsky} строит по $G$ такую КС"/грамматику $G'$ в нормальной форме Хомского, что $L(G)=L(G')$.
\end{mytheorem}

\input{img/chap7/algo-1.tex}

\begin{myproof}
Применим к КС"/грамматике $G$ алгоритм~\ref{algo-Homsky}. В силу теоремы~\ref{theorem-NormalGrammarAlgoCorrectness} на шаге 1 этого алгоритма строится приведенная КС"/грамматика $G_1=(N_1,\Sigma, P_1, S_1)$, в продукциях которой $S_1$ не встречается в правых частях и для которой $L(G)=L(G_1)$. Шаги 2--8 алгоритма~\ref{algo-Homsky} позволяют построить по $G_1$ грамматику $G'$, которая, очевидно, имеет нормальную форму Хомского. Чтобы показать, что $L(G_1)=L(G')$, достаточно применить лемму~\ref{lemma-proofOfHomskyMod} к каждой продукции грамматики $G'$, в правую часть которой входит $a'$, а затем применить эту лемму к продукциям с нетерминалами вида $\la X_i\ldots X_j \ra$.
\end{myproof}

Иногда вместо нормальной формы Хомского рассматривают другую, слегка
измененную, каноническую форму. Будем говорить, что КС"/грамматика
$G=(N,\Sigma,P,S)$ представлена в \mydef{модифицированной нормальной
форме Хомского}, если продукции из $P$ имеют один из следующих видов:
\begin{enumerate}
    \item $A\to BC$, где $A,B,C\in N$;
    \item $A\to a$, где $A\in N$, $a\in\Sigma$;
    \item $S\to\eps$, если $\eps\in L(G)$, причем в этом случае
    $S$ не встречается в правых частях продукций.
\end{enumerate}

Чтобы преобразовать произвольную КС"/грамматику к модифицированной нормальной форме Хомского достаточно слегка подправить алгоритм~\ref{algo-Homsky}.

\begin{Algo}
{Преобразование КС-грамматики к модифицированной нормальной форме Хомского}
{\label{algo-Homsky-Mod}КС"/грамматика $G=(N,\Sigma,P,S)$.}
{КС"/грамматика $G'$ в модифицированной нормальной форме Хомского, у которой $L(G')=L(G)$.}
{Модификация одного шага алгоритма~\ref{algo-Homsky}.}
{
\item
 Применить к грамматике $G=(N,\Sigma,P,S)$ алгоритм~\ref{algo-NormalGrammar} и построить тем самым приведенную КС"/грамматику $G_1=(N_1,\Sigma,P_1,S_1)$. Перейти на следующий шаг, где начинается построение искомой грамматики $G'=(N',\Sigma,P',S_1)$.

\item[\textit{Шаги 2--8}]
 повторяют соответствующие шаги алгоритма~\ref{algo-Homsky}.
}
\end{Algo}

\begin{myproblem}
Сформулировать и доказать аналог теоремы~\ref{theorem-AlgoHomskyProof} для обоснования алгоритма~\ref{algo-HomskyMod}.
\end{myproblem}

\begin{myexample}
\label{example-GramToHomsky}
Преобразуем КС"/грамматику
\[
G = (\{A;B;S\},\{a;b;c;d\},P,S)
\]
с продукциями
\[
	S \to \alpha AB \mid BA, \quad
	A \to BBB \mid a, \quad
	B \to AS \mid b,
\]
к нормальной форме Хомского. Для этого применим к грамматике $G$
алгоритм~\ref{algo-Homsky}. В соответствии с первым шагом алгоритма введем новый
стартовый нетерминал $S_1$ и добавим к $P$ одну продукцию $S_1\to S$.
Применим теперь к полученной грамматике алгоритм~\ref{algo-NormalGrammar} и построим
приведенную КС"/грамматику
\[
    G_1 = (\{A;B;S;S_1\},\{a;b;c;d\},P_1,S_1)
\]
с продукциями
\[
	S_1 \to aAB \mid BA, \quad
	S \to aAB \mid BA, \quad
    A \to BBB \mid a, \quad
    B \to AS \mid b
\]
(в продукциях стартовый нетерминал $S_1$ в правых частях не
встречается). Начнём преобразовывать грамматику $G_1$ к грамматике
$G'$
в нормальной форме Хомского. Из $P_1$ в $P'$ продукции $S_1\to BA$,
$S\to BA$, $A\to a$, $B\to AS$ и $B\to b$ переносим без изменения.
Заменяем продукцию $S_1\to aAB$ продукциями $S\to a' \la AB \ra$  и $
\la AB \ra \to AB$, $S\to aAB$~--- продукциями $S\to a' \la AB \ra$ и $
\la AB \ra \to AB$, а $A\to BBB$~--- продукциями $A\to B \la BB \ra$ и
$ \la BB \ra \to BB$. Наконец, добавляем к $P'$ продукцию $a'\to a$. В
результате получаем грамматику
\[
    G' = (\{A;B;S;S_1;\la AB \ra; \la BB \ra; a'\},\{a,b\},P',S_1),
\]
с продукциями
\begin{align*}
	S_1 &\to a' \la AB\ra \mid BA, &
    S   &\to a'\la AB\ra  \mid BA, \\
    A   &\to B \la BB\ra \mid a, &
    B   &\to AS \mid b, \\
    \la AB \ra &\to AB, &
    \la BB\ra  &\to BB, \\
    a' &\to a.
\end{align*}
Эта грамматика имеет нормальную форму Хомского. По теореме~\ref{theorem-AlgoHomskyProof}
\[
    L(G)=L(G'),
\]
и, следовательно, $G'$"--- искомая грамматика.
\end{myexample}

\begin{myproblem}
Преобразовать КС-грамматику из примера~\ref{example-GramToHomsky} к модифицированной нормальной форме Хомского.
\end{myproblem}

\section{Проблема принадлежности для КС"/языков}
\label{Chapter7ProblemB}

Нормальные формы, как правило, вводятся для удобства формулировки
алгоритмов, решающих конкретные задачи. Нормальная форма Хомского
позволяет, в частности, сформулировать алгоритм решения проблемы
принадлежности для КС"/языков, а именно, по данному слову и данному
КС"/языку, представленному в виде КС"/грамматики, его порождающей,
определить, принадлежит ли это слово языку. Описанию данного алгоритма 
посвящён настоящий раздел.

\Algo
{Алгоритм Кока—Янгера—Касами («CYK-алгоритм»)}
{\label{algo-CYK}КС-грамматика в нормальной форме Хомского $G=(N,\Sigma,P,S)$,
слово $w\in \Sigma^*$ длины $n$.}
{истина, если $w \in L(G)$, и ложь в противном случае.}
{последовательное определение нетерминалов, выводящих
всевозможные подстроки $w$ всё большей длины.}
{
\item Для всех $k\in [1,n]_\N$ положить $N_{kk} = \{ A \in N \mid
    A \to w_i \in P\}$. Таким образом учтены все подстроки $w$ длины
    единица.

\item Если $n=1$, завершить алгоритм и вернуть результат
    проверки $S \in N_{11}$. Иначе положить длину
    рассматриваемых подстрок $s = 2$.

\item Положить $i = 1$.

\item
    Положить $j = i + s - 1$. Положить
    \[
        N_{ij} = \{ A \in N \mid A \to BC \in P; \;
                \exists k \in [i, j-1]_\N \colon B \in N_{ik}, \;
                C \in N_{k+1 j} \}.
    \]

\item Увеличить $i$ на единицу. Если $ i < n - s$, перейти
    к шагу 4.

\item Если $s = n$, завершить алгоритм и вернуть результат
    проверки $S \in N_{1n}$. Иначе увеличить $s$ на единицу и
    перейти к шагу 3.
}

Для описания алгоритма~\ref{algo-CYK} (с.~\pageref{algo-CYK}) используется
одно важное обозначение. Пусть задана
КС"/грамматика $G=(N,\Sigma,P,S)$ и слово $w\in \Sigma^*$.
Для всех $1 \leqslant i \leqslant j \leqslant n$
определим множество
\[
    N_{ij}^w = \{ A \in N \mid A \Rightarrow^*_G w_i \ldots w_j \}.
\]
То есть $N_{ij}^w$ ---  это множество нетерминалов, которые порождают
подстроку $w_i \ldots w_j$ строки $w$ в грамматике $G$. Когда слово
$w$ фиксировано и ясно из контекста, будем опускать верхний индекс
в обозначении $N_{ij}^w$.


\begin{myproblem} Постройте модификацию CYK"/алгоритма, которая позволяет в случае $w \in
L(G)$ давать на выходе вывод слова $w$ в грамматике $G$.
\end{myproblem}

\begin{myremark}[о структуре CYK-алгоритма]
Заметим, что вычисление множеств $N_{ij}$ в алгоритме~\ref{algo-CYK} происходит
таким образом, что на более поздних итерациях (для больших значений $j-i$)
используются результаты более ранних. Такой подход к проектированию алгоритмов,
когда решение задачи определяется через решение нескольких таких же задач,
но меньшего размера,
называется \emph{динамическим программированием}. Отличие от более простого
подхода \emph{разделяй и властвуй}, обычно основанного на прямой рекурсии,
состоит в том, что подзадачи могут перекрываться. Более точно, результат
решения одной подзадачи может использоваться многократно. В такой ситуации
простая рекурсивная реализация будет заведомо неэффективной. Вместо этого
предлагается решать все подзадачи подряд, начиная с самых маленьких, а их
результаты записывать для дальнейшего использования при решении более
крупных подзадач.
\end{myremark}

Как это часто бывает в динамическом программировании, CYK"/алгоритм
удобно проводить с помощью заполнения некоторой таблицы
(см. рисунок~\ref{tab-cyk} на с.~\pageref{tab-cyk}).

\begin{figure}
\begin{center}
\begin{tabular}{|ccccc}
$N_{15}$ & & & &\\
$N_{14}$ & $N_{25}$ & & &\\
$N_{13}$ & $N_{24}$ & $N_{35}$ & &\\
$N_{12}$ & $N_{23}$ & $N_{34}$ & $N_{45}$ &\\
$N_{11}$ & $N_{22}$ & $N_{33}$ & $N_{44}$ & $N_{55}$\\
\hline
\end{tabular}
\end{center}
\caption{Пример таблицы CYK-алгоритма для $n=5$}
\label{tab-cyk}
\end{figure}

\noindent Таблица заполняется снизу вверх и
слева направо. При этом для подсчёта очередного множества будут
использоваться лишь клетки, расположенные ниже текущей.

Рассмотрим в качестве примера, какие пары множеств нетерминалов 
$N_{ij}$ потребуется просматривать, чтобы построить $N_{25}$. В 
соответствии с описанием алгоритма (шаг~4, формула для $N_{ij}$) это 
пары $N_{24}$ и $N_{55}$, $N_{23}$ и $N_{45}$,  $N_{22}$ и $N_{35}$. 
Они отмечены в таблице на рисунке~\ref{cyk-computeN25} 
(с.~\pageref{cyk-computeN25}) разными типами скобок (фигурными, 
квадратными и круглыми соответственно), чтобы подчеркнуть 
геометрическую последовательность работы алгоритма. Аналогичная 
треугольная форма будет появляться при расчете и всех других множеств, 
кроме $N_{ii}$, которые строятся непосредственно по грамматике.

\begin{figure}
\begin{center}
\begin{tabular}{|ccccc}
$N_{15}$ & & & &\\
$N_{14}$ & \fbox{$N_{25}$} & & &\\
$N_{13}$ & $\{N_{24}\}$ & $(N_{35})$ & &\\
$N_{12}$ & $[N_{23}]$ & $N_{34}$ & $[N_{45}]$ &\\
$N_{11}$ & $(N_{22})$ & $N_{33}$ & $N_{44}$ & $\{N_{55}\}$\\
\hline
\end{tabular}
\end{center}
\caption{Используемые для расчета $N_{25}$ множества}
\label{cyk-computeN25}
\end{figure}

\begin{myremark}[о сложности CYK-алгоритма]
Отметим, что с точки зрения теории син\-так\-сического анализа
CYK"/алгоритм проводит \emph{восходящий (bottom—up) анализ}, т. е.
восстанавливает дерево вывода, начиная с кроны, а не с корня.
Нетрудно видеть, что сложность CYK"/алгоритма может быть оценена как
$O(n^3 \cdot |P|)$, это ограничивает применение алгоритма на практике.
В теории компиляторов и приложениях чаще рассматривается подкласс КС"/грамматик,
\emph{детерминированные КС"/грамматики} (по-другому, $LL(k)$- и
$LR(k)$"/грамматики), для которых существуют линейные алгоритмы разбора
(сложность $O(n)$).
\end{myremark}


\section{Матричный метод перехода к нормальной форме Грейбах}
\label{Chapter7NFG-MT}

КС"/грамматика $G=(N,\Sigma,P,S)$ называется грамматикой в нормальной
форме Грейбах, если она является неукорачивающеися и каждая продукция
из $P$, отличная от $S\to\eps$, имеет вид $A\to a\alpha$, где
$a\in\Sigma$ и $\alpha\in N^*$. В $[1]$ описан алгоритм пребразования
произвольной КС"/грамматики к нормальной форме Грейбах, основанный на
предварительном устранении левой рекурсии.

Рассмотрим КС"/грамматику $G=(N,\Sigma,P,S)$, в которой нет цепных
правил и $\eps$"/продукций (даже вида $S\to\eps$), и схематично опишем
принадлежащий Розенкранцу матричный метод преобразования такой
грамматики к нормальной форме Грейбах. Этот метод использует технику,
напоминающую технику работы с регулярными выражениями из главы~\ref{Chapter2}.

Дадим необходимые определения. Пусть $\Delta$ и $\Sigma$ --- два
непересекающихся алфавита; алфавит $\Delta$ будем называть
нетерминальным, а алфавит $\Sigma$ --- терминальным. Системой
определяющих уравнений над конечными алфавитами $\Sigma$ и $\Delta$
назовем систему уравнений вида
\begin{equation}
\label{eq621}
A = \alpha_1 + \ldots + \alpha_k, %(6.2.1)
\end{equation}
где $A\in\Delta$ и $\alpha_i\in(\Delta\cup\Sigma)^*$; если $k=0$, то
уравнение имеет вид $A=\es$. Предполагается, что для каждого
$A\in\Delta$ в системе есть только одно уравнение с левой частью $A$.
Решением системы определяющих уравнений назовем такое отображение $f$
множества $\Delta$ в $P(\Sigma^*)$, что если вместо каждого
$A\in\Delta$ подставить $f(A)$ в уравнения системы, то эти уравнения
превратятся в равенства. Решение $f$ назовем наименьшей неподвижной
точкой, если $f(A)\subseteq g(A)$ для любого решения $g$ и любого
$A\in\Delta$. Стандартные системы линейных уравнений с регулярными
коэффициентами из главы~\ref{Chapter2} входят в класс систем определяющих уравнений.

Выделим в $\Delta$ символ $S$. Системе определяющих уравнений над
конечными алфавитами $\Delta$ и $\Sigma$ с выделенным символом
$S\in\Delta$ можно естественным образом сопоставить КС"/грамматику, в
которой $\Delta$ --- нетерминальный алфавит, $\Sigma$ --- терминальный
алфавит, $S$ --- начальные символ, а продукции определяются по каждому
уравнению~\eqref{eq621} исходной системы следующим образом:
\begin{equation}
\label{eq622}
    A \to  \alpha_1 \mid \alpha_2 \mid \ldots \mid \alpha_k.
\end{equation}
Ясно, что разным системам сопоставляются разные грамматики и
приведенная конструкция осуществляет взаимно однозначное соответствие
между множеством всех систем определяющих уравнений над конечными
алфавитами и множеством КС"/грамматик.

Приведем без доказательства несколько результатов о системах
определяющих уравнений, обобщающих результаты о стандартных системах
линейных уравнений с регулярными коэффициентами. Отметим прежде
всего, что при сделанных предположениях наименьшая неподвижная
точка системы определяющих уравнений над алфавитами $\Delta$
и $\Sigma$ существует, единственна и имеет вид
\[
    f(A) = \{\omega\mid A \To_G^* \omega, \; \omega\in\Sigma^*\},
\]
где $G$ --- соответствующая системе КС"/грамматика.

Мы будем пользоваться далее матричным представлением систем
определяющих уравнений. Именно пусть алфавит $\Delta$ состоит из
нетерминалов
\[
A_1, A_2, \ldots , A_n
\]
и
\begin{enumerate}
    \item $\Delta$ --- вектор"/строка $[A_1;A_2;\ldots ;A_n]$;

    \item $R$ --- квадратная матрица порядка $n$, элементами которой
    служат регулярные выражения над $N\cup\Sigma$: стоящий в $i$"/й
    строке и $j$"/м столбце элемент матрицы $R$ определяется равенством
    \[
        R_{ij} = \alpha_1 + \alpha_2 + \ldots + \alpha_k,
    \]
    где $A_i\alpha_1, A_i\alpha_2, \ldots , A_i\alpha_k$ --- все члены
    уравнения для $A_j$, первой буквой которых является $A_i$;

    \item $B$ --- вектор"/строка, состоящая из $n$ регулярных
    выражений над $N\cup\Sigma$: стоящий на $j$"/м месте элемент $B_j$
    определяется как сумма членов уравнения для $A_j$, которые
    начинаются буквой из $\Sigma$.
\end{enumerate}

Таким образом, $B_j$ и $R_{ij}$ --- такие выражения, что уравнение для $A_j$ можно записать в виде
\[
A_j = A_1R_{1j} + A_2R_{2j} + \ldots + A_iR_{ij} + \ldots + A_nR_{nj} + B_j.
\]

Сложение и умножение векторов и матриц определим как обычно, при этом в качестве <<умножения>> элементов матриц будем рассматривать конкатенацию, а в качестве <<сложения>> --- операцию объединения. Систему определяющих уравнений теперь будем представлять при помощи матриц:
\begin{equation}
\label{eqGeneralSOS}
\Delta=\Delta R+B.
\end{equation}

\begin{myexample}
\label{example-MatrView}
Рассмотрим грамматику $G=(\{A;B\},\{b;a;c;d\},P,A)$ с продукциями
\begin{align*}
    A &\to AaB \mid BB \mid b, \\
    B &\to aA \mid BAa \mid Bd \mid c.
\end{align*}
Построим систему определяющих уравнений для этой грамматики:
\begin{equation*}
\begin{cases}
	A = AaB + BB + b \\
	B = aA + BAa + Bd + c.
\end{cases}
\end{equation*}

При помощи матриц эту систему можно переписать так:
\begin{equation}
[A;B] = [A;B]
\begin{bmatrix}
aB & \es \\
B & Aa+d
\end{bmatrix} + [b;aA+C].
\end{equation}
\end{myexample}

Для системы~\eqref{eqGeneralSOS} можно найти такую равносильную ей систему определяющих уравнений, что все правые части продукций из КС"/грамматики, которая соответствует новой системе, начинаются терминальными буквами.

\begin{mytheorem}
Пусть~\eqref{eqGeneralSOS} --- записанная в матричном виде система определяющих уравнений над алфавитами $\Delta$ и $\Sigma$, $Q$ --- квадратная матрица порядка $b=|\Delta |$ с $n^2$ различными новыми элементами $q_{i,j}$. $\widetilde Q$ --- множество всех элементов $q_{i,j}$, $\widetilde\Delta = \Delta \cup \widetilde Q$. Тогда система определяющих уравнений

\begin{equation}
\label{eqGeneralWithAddQ}
\begin{cases}
	\Delta = BQ + B, \\
    Q = RQ + R
\end{cases}
\end{equation}
над алфавитами $\widetilde\Delta$ и $\Sigma$ имеет наименьшую неподвижную точку, которая совпадает на $\Delta$ с наименьшей неподвижной точкой системы~\eqref{eqGeneralSOS}.
\end{mytheorem}

Приведем алгоритм преобразования КС"/грамматики к нормальной форме Грейбах, основанный на конструкции из этой теоремы.

\AlgoNoMeth[H]{Преобразование к нормальной форме Грейбах}
{\label{algo-Greybah}приведенная КС"/грамматика $G=(N,\Sigma,P,S)$, не содержащая продукции $S\to\eps$.}
{КС"/грамматика $G'=(N',\Sigma,P',S)$ в нормальной форме Грейбах.}
{
\item По грамматике $G$ построить систему определяющих уравнений $\Delta=\Delta R+B$ над алфавитами $N$ и $\Sigma$.

\item Ввести $Q$ --- квадратную матрицу порядка $n=|N|$, состоящую из новых нетерминальных букв $q_{ij}$. Построить по $Q$ и исходной системе~\eqref{eqGeneralSOS} новую систему~\eqref{eqGeneralWithAddQ} и соответствующую новой системе КС"/грамматику $G_1$. (Так как в $B$ каждая компонента, отличная от $\es$, начинается терминалом, то для $A\in N$ все нетерминальные $A$"/продукции грамматики $G_1$ будут начинаться терминалами; наличие в $B$ ненулевых компонент вытекает из приведенности грамматики $G$.)

\item (Так как $G$ --- приведенная грамматика, то $\eps$ не встречается среди элементов матрицы $R$; поэтому для каждого элемента $q\in Q$ все нетерминальные $q$"/продукции грамматики $G_1$ начинаются символами из $N\cup\Sigma$.) Для каждого нетерминала $A$ из $N$ в тех правых частях нетерминальных $q$"/продукций грамматики $G_1$, которые начинаются буквой $A$, заменить этот нетерминал правыми частями всех $A$"/продукций. В результате получится грамматика, у которой правые части всех продукций начинаются терминалом.

\item Если в правой части продукции терминал $a$ встречается не на первом месте, заменить его новым нетерминалом $a'$ и добавить продукцию $a'\to a$. В итоге получим искомую КС"/грамматику $G'$.$\blacksquare$
}

\begin{mytheorem}
\label{theorem-AlgoGreybahCorrectness}
Алгоритм~\ref{algo-Greybah} строит грамматику $G'$ в нормальной форме Грейбах и $L(G)=L(G')$.
\end{mytheorem}

\begin{myexample}
Рассмотрим КС"/грамматику $G=(\{A;B\},\{b;a;c\},P,A)$ из примера~\ref{example-MatrView}, где реализован первый шаг алгоритма. На втором шаге введем нетерминальную матрицу
\[
    \begin{bmatrix}
        W & X \\
        Y & Z
    \end{bmatrix}
\]
и построим по этой матрице и системе~\ref{eqGeneralWithAddQ} новую систему
\begin{equation}
\label{eq625}
    \begin{cases}
        [A,B]
            = [b,aA+c]
            \begin{bmatrix}
                W & X \\
                Y & Z
            \end{bmatrix}
            + [b,aA+c], \\

        \begin{bmatrix}
            W & X \\
            Y & Z
        \end{bmatrix}
            =
            \begin{bmatrix}
                ab & \es \\
                B & Aa+d
            \end{bmatrix}
            \begin{bmatrix}
                W & X \\
                Y & Z
            \end{bmatrix}
            +
            \begin{bmatrix}
                aB & \es \\
                B & Aa+d
            \end{bmatrix}
            .
    \end{cases}
\end{equation}
Системе~\ref{eq625} соответствует КС"/грамматика с продукциями
\begin{align*}
	A &\to bW \mid aAY \mid cY \mid b, &
    B &\to bX \mid aAZ \mid cZ \mid aA \mid c, \\
    W &\to aBW \mid aB, &
    X &\to aBX, \\
    Y &\to BW \mid AaY \mid dY \mid B, &
    Z &\to BX \mid AaZ \mid dZ \mid Aa \mid d.
\end{align*}
Заметим, что $X$ --- бесполезный символ. Следовательно, полученные продукции можно упростить:
\begin{align*}
    A &\to bW \mid aAY \mid cY \mid b, &
    B &\to aAZ \mid cZ \mid aA \mid c, \\
    W &\to aBW \mid aB, &
    Y &\to BW~|AaY \mid dY \mid B, \\
    Z &\to AaZ \mid dZ \mid Aa \mid d.
\end{align*}
Итак, в результате второго шага алгоритма построена грамматика
\[
    G_1 = (\{A;B;W;Y;Z\},\{a;b;c;d\},P_1,A),
\]
где $P_1$ --- описанное выше множество.

На третьем шаге алгоритма в пяти <<нехороших>> продукциях
\begin{align*}
    Y &\to BW \mid AaY \mid B, \\
    Z &\to AaZ \mid Aa
\end{align*}
нетерминалы $A$ и $B$ надо заменить правыми частями
соответствующих нетерминальных $A$- и $B$"/продукций.
Например, из продукции $Y \to BW$ получаем:
\[
    Y \to aAZW \mid cZW \mid aAW \mid cW,
\]
а из продукции $Z \to AaZ$:
\[
    Z \to bWaZ \mid aAYaZ \mid cYaZ \mid baZ.
\]
В результате третьего шага алгоритма вместо пяти <<нехороших>> продукций мы построили двадцать новых:
\begin{align*}
    Y &\to aAZW \mid cZW \mid aAW \mid cW \mid bWaY \mid aAYaY
        \mid cYaY \mid baY \mid cAZ \mid cZ \mid aA \mid c, \\
    Z &\to bWaZ \mid aAYaZ \mid cYaZ \mid baZ \mid bWa \mid aAYa
        \mid cYa \mid ba.
\end{align*}
Теперь правые части всех продукций начинаются терминалами.

На четвертом шаге алгоритма в тех продукциях, у которых в правой части терминал $x$ встречается не на первом месте, надо заменить его новым нетерминалом $x'$: после этого надо добавить новую продукцию $x'\to x$. В итоге получаем КС"/грамматику $G' = (\{A;B;W;Y;Z;a'\},\{a;b;c;d\},P',A)$ с множеством продукций $P'$:
\begin{align*}
    A &\to bW \mid aAY \mid cY \mid b, \\
    B &\to aAZ \mid cZ \mid aA \mid c, \\
    W &\to aBW \mid aB, \\
    Y &\to aAZW \mid cZW \mid aAW \mid cW \mid bWa'Y \mid cYa'Y
        \mid ba'Y \mid aAZ \mid cZ \mid aA \mid c \mid dY, \\
    Z &\to bWa'Z \mid aAYa'Z \mid cYa'Z \mid ba'Z \mid bWa'
        \mid aAYa' \mid cYa' \mid ba' \mid dZ \mid d, \\
    a' &\to a.
\end{align*}
Эта грамматика имеет нормальную форму Грейбах. С другой стороны, по теореме~\ref{theorem-AlgoGreybahCorrectness} $L(G)=L(G')$.
\end{myexample}

\section{Упражнения}
\label{Chapter7Exs}

\subsection*{Получение нормальных форм}

Привести к нормальной форме Хомского, а также, к нормальной форме Грей\-бах, грамматики с продукциями:
%\begin{multicols}{2}
%\begin{enumerate}
%\begin{figure}
%\end{figure}
\begin{center}
\begin{tabular}{l@{\hskip 1cm}l}
        1)\ \ $\begin{aligned}%{l}
            S &\to ASB \mid \varepsilon,\\
            A &\to aAS \mid a,\\
            B &\to SbS \mid A \mid bb;
        \end{aligned}$
&        
        2)\ \ $\begin{aligned}%{l}
            S &\to 0A0 \mid 1B1 \mid BB,\\
            A &\to C,\\
            B &\to S \mid A,\\
            C &\to S \mid \varepsilon;
        \end{aligned}$
\\
        3)\ \ $\begin{aligned}%{l}
            S &\to AAA \mid B,\\
            A &\to aA \mid B,\\
            B &\to \varepsilon;
        \end{aligned}$
&
        4)\ \ $\begin{aligned}%{l}
            S &\to aAa \mid bBb \mid \varepsilon,\\
            A &\to C \mid a,\\
            B &\to C \mid b,\\
            C &\to CDE \mid \varepsilon,\\
            D &\to A \mid B \mid ab.
        \end{aligned}$
\end{tabular}
\end{center}
%\end{enumerate}
%\end{multicols}

\subsection*{CYK"/алгоритм}

Используя CYK"/алгоритм,
\begin{enumerate}
    \item
    для грамматики $G$ с продукциями:
    \[
        S \to AB, \qquad
        A \to BB \mid a, \qquad
        B \to AB \mid b
    \]
    определить, принадлежат ли $L(G)$ строки: (а) $aabbb$, (б) $babab$,
    (в) $b^7$;

    \item
    для грамматики $G$ с продукциями:
    \[
        S \to AB \mid BC,\qquad
        A \to BA \mid a,\qquad
        B \to CC \mid b,\qquad
        C \to AB \mid a
    \]
    определить, принадлежат ли $L(G)$ строки: (а) $ababa$, (б) $baaab$, (в) $aabab$.
\end{enumerate}