CYK_for_CFPQ.tex

\chapter{CYK для вычисления КС запросов}\label{chpt:CFPQ_CYK}

В данной главе мы рассмотрим алгоритм CYK, позволяющий установить принадлежность слова грамматике и предоставить его вывод, если таковой имеется.

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

\section{Алгоритм CYK}\label{sect:lin_CYK}

Алгоритм CYK (Cocke-Younger-Kasami) --- один из классических алгоритмов синтаксического анализа. Его асимптотическая сложность в худшем случае --- $O(n^3 * |N|)$, где $n$ --- длина входной строки, а $N$ --- количество нетерминалов во входной грамматике~\cite{Hopcroft+Ullman/79/Introduction}.

Для его применения необходимо, чтобы подаваемая на вход грамматика находилась в Нормальной Форме Хомского (НФХ)~\ref{section:CNF}. Других ограничений нет и, следовательно,данный алгоритм применим для работы с произвольными контекстно-своболными языками.

В основе алгоритма лежит принцип динамического программирования. Используются два соображения:

\begin{enumerate}
\item Для правила вида $A \to a$ очевидно, что из $A$ выводится $\omega$ (с применением этого правила) тогда и только тогда, когда $a = \omega$:

\[
  A \derives \omega \iff \omega = a
\]

\item Для правила вида $A \to B C$ понятно, что из $A$ выводится $\omega$ (с применением этого правила) тогда и только тогда, когда существуют две цепочки $\omega_1$ и $\omega_2$ такие, что $\omega_1$ выводима из $B$, $\omega_2$ выводима из $C$ и при этом $\omega = \omega_1 \omega_2$:

\[
A \derives[] B C \derives \omega \iff \exists \omega_1, \omega_2 : \omega = \omega_1 \omega_2, B \derives \omega_1, C \derives \omega_2
\]

Или в терминах позиций в строке:

\[
A \derives[] B C \derives \omega \iff \exists k \in [1 \dots |\omega|] : B \derives \omega[1 \dots k], C \derives \omega[k+1 \dots |\omega|]
\]
\end{enumerate}

В процессе работы алгоритма заполняется булева трехмерная матрица $M$ размера $n \times n \times  |N|$ таким образом, что $$M[i, j, A] = true \iff A \derives \omega[i \dots j]$$.

Первым шагом инициализируем матрицу, заполнив значения $M[i, i, A]$:

\begin{itemize}
  \item $M[i, i, A] = true \text{, если в грамматике есть правило } A \to \omega[i]$.
  \item $M[i, i, A] = false$, иначе.
\end{itemize}

Далее используем динамику: на шаге $m > 1$ предполагаем, что ячейки матрицы $M[i', j', A]$ заполнены для всех нетерминалов $A$ и пар $i', j': j' - i' < m$.
Тогда можно заполнить ячейки матрицы $M[i, j, A] \text{, где } j - i = m$ следующим образом:

\[ M[i, j, A] = \bigvee_{A \to B C}^{}{\bigvee_{k=i}^{j-1}{M[i, k, B] \wedge M[k+1, j, C]}} \]

По итогу работы алгоритма значение в ячейке $M[0, |\omega|, S]$, где $S$ --- стартовый нетерминал грамматики, отвечает на вопрос о выводимости цепочки $\omega$ в грамматике.

\begin{example}\label{exampl:CYK}
  Рассмотрим пример работы алгоритма CYK на грамматике правильных скобочных последовательностей в Нормальной Форме Хомского.


\begin{align*}
S &\to A S_2 \mid \varepsilon & S_2  &\to b \mid B S_1 \mid S_1 S_3   & A   &\to a \\
S_1   &\to A S_2              & S_3  &\to b \mid B S_1              & B   &\to b\\
\end{align*}

Проверим выводимость цепочки $\omega = a a b b a b$.

Так как трехмерные матрицы рисовать на двумерной бумаге не очень удобно, мы будем иллюстрировать работу алгоритма двумерными матрицами размера $n \times n$, где в ячейках указано множество нетерминалов, выводящих соответствующую подстроку.

Шаг 1. Инициализируем матрицу элементами на главной диагонали:

\[
\begin{pmatrix}
\{A\}       & \varnothing & \varnothing    & \varnothing      & \varnothing & \varnothing    \\
\varnothing & \{A\}       & \varnothing    & \varnothing      & \varnothing & \varnothing    \\
\varnothing & \varnothing & \{B, S_2, S_3\} & \varnothing     & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing    & \{B, S_2, S_3\}   & \varnothing & \varnothing   \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \{A\}       & \varnothing    \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \varnothing & \{B, S_2, S_3\} \\
\end{pmatrix}
\]

Шаг 2. Заполняем диагональ, находящуюся над главной:

\[
\begin{pmatrix}
\{A\}       & \varnothing & \varnothing                             & \varnothing      & \varnothing & \varnothing    \\
\varnothing & \{A\}       & \cellcolor{lightgray}\{S_1\}            & \varnothing      & \varnothing & \varnothing    \\
\varnothing & \varnothing & \{B, S_2, S_3\} & \varnothing     & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing    & \{B, S_2, S_3\}   & \varnothing & \varnothing   \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \{A\}       & \cellcolor{lightgray}\{S_1\}            \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \varnothing & \{B, S_2, S_3\} \\
\end{pmatrix}
\]

В двух ячейках появилисб нетерминалы $S_1$ благодяря присутствиб в грамматике правила $S_1 \to A S_2$.

Шаг 3. Заполняем следующую диагональ:

\[
\begin{pmatrix}
\{A\}       & \varnothing & \varnothing    & \varnothing      & \varnothing & \varnothing    \\
\varnothing & \{A\}       & \{S_1\}        & \cellcolor{lightgray}\{S_2\}          & \varnothing & \varnothing    \\
\varnothing & \varnothing & \{B, S_2, S_3\} & \varnothing     & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing    & \{B, S_2, S_3\}   & \varnothing & \cellcolor{lightgray}\{S_2, S_3\}  \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \{A\}       & \{S_1\}            \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \varnothing & \{B, S_2, S_3\} \\
\end{pmatrix}
\]

Шаг 4. И следующую за ней:

\[
\begin{pmatrix}
\{A\}       & \varnothing & \varnothing    & \cellcolor{lightgray}\{S_1, S\}       & \varnothing & \varnothing    \\
\varnothing & \{A\}       & \{S_1\}            & \{S_2\}          & \varnothing & \varnothing    \\
\varnothing & \varnothing & \{B, S_2, S_3\} & \varnothing     & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing    & \{B, S_2, S_3\}   & \varnothing & \{S_2, S_3\}  \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \{A\}       & \{S_1\}            \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \varnothing & \{B, S_2, S_3\} \\
\end{pmatrix}
\]

Шаг 5 Заполняем предпоследнюю диагональ:

\[
\begin{pmatrix}
\{A\}       & \varnothing & \varnothing    & \{S_1, S\}       & \varnothing & \varnothing    \\
\varnothing & \{A\}       & \{S_1\}            & \{S_2\}          & \varnothing & \cellcolor{lightgray}\{S_2\}        \\
\varnothing & \varnothing & \{B, S_2, S_3\} & \varnothing     & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing    & \{B, S_2, S_3\}   & \varnothing & \{S_2, S_3\}  \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \{A\}       & \{S_1\}            \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \varnothing & \{B, S_2, S_3\} \\
\end{pmatrix}
\]

\bigbreak
Шаг 6. Завершаем выполнение алгоритма:

\[
\begin{pmatrix}
\{A\}       & \varnothing & \varnothing    & \{S_1, S\}       & \varnothing & \cellcolor{lightgray}\{S_1, S\}     \\
\varnothing & \{A\}       & \{S_1\}            & \{S_2\}          & \varnothing & \{S_2\}        \\
\varnothing & \varnothing & \{B, S_2, S_3\} & \varnothing     & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing    & \{B, S_2, S_3\}   & \varnothing & \{S_2, S_3\}  \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \{A\}       & \{S_1\}            \\
\varnothing & \varnothing & \varnothing    & \varnothing      & \varnothing & \{B, S_2, S_3\} \\
\end{pmatrix}
\]


Стартовый нетерминал находится в верхней правой ячейке, а значит цепочка $a a b b a b$ выводима в нашей грамматике.
\end{example}

\begin{example}
Теперь выполним алгоритм на цепочке $\omega=abaa$.

Шаг 1. Инициализируем таблицу:

\[
\begin{pmatrix}
\{A\}       & \varnothing    & \varnothing & \varnothing    \\
\varnothing & \{B, S_2, S_3\} & \varnothing & \varnothing       \\
\varnothing & \varnothing    & \{A\}       & \varnothing    \\
\varnothing & \varnothing    & \varnothing & \{A\}          \\
\end{pmatrix}
\]

Шаг 2. Заполняем следующую диагональ:

\[
\begin{pmatrix}
\{A\}       & \cellcolor{lightgray}\{S_1, S\}     & \varnothing & \varnothing    \\
\varnothing & \{B, S_2, S_3\} & \varnothing & \varnothing       \\
\varnothing & \varnothing    & \{A\}       & \varnothing    \\
\varnothing & \varnothing    & \varnothing & \{A\}          \\
\end{pmatrix}
\]

Больше ни одну ячейку в таблице заполнить нельзя и при этом стартовый нетерминал отсутствует в правой верхней ячейке, а значит эта строка не выводится в грамматике правильных скобочных последовательностей.

\end{example}

\section{Алгоритм для графов на основе CYK}
\label{graph:CYK}
Первым шагом на пути к решению задачи достижимости с использованием CYK является модификация представления входа. Прежде мы сопоставляли каждому символу слова его позицию во входной цепочке, поэтому при инициализации заполняли главную диагональ матрицы. Теперь вместо этого обозначим числами позиции между символами. В результате слово можно представить в виде линейного графа следующим образом(в качестве примера рассмотрим слово $a a b b a b$ из предыдущей главы~\ref{sect:lin_CYK}):

\begin{center}
    \begin{tikzpicture}[shorten >=1pt,on grid,auto]
    \node[state] (q_0) at (0,0)  {$0$};
    \node[state] (q_1) at (2,0)  {$1$};
    \node[state] (q_2) at (4,0)  {$2$};
    \node[state] (q_3) at (6,0)  {$3$};
    \node[state] (q_4) at (8,0)  {$4$};
    \node[state] (q_5) at (10,0) {$5$};
    \node[state] (q_6) at (12,0) {$6$};
    \path[->]
    (q_0) edge  node {$a$} (q_1)
    (q_1) edge  node {$a$} (q_2)
    (q_2) edge  node {$b$} (q_3)
    (q_3) edge  node {$b$} (q_4)
    (q_4) edge  node {$a$} (q_5)
    (q_5) edge  node {$b$} (q_6);
    \end{tikzpicture}
\end{center}

Что нужно изменить в описании алгоритма, чтобы он продолжал работать при подобной нумерации? Каждая буква теперь идентифицируется не одним числом, а парой --- номера слева и справа от нее. При этом чисел стало на одно больше, чем при прежнем способе нумерации.

Возьмем матрицу  $(n + 1) \times (n + 1) \times  |N|$ и при инициализации будем заполнять не главную диагональ, а диагональ прямо над ней. Таким образом, мы начинаем наш алгоритм с определения значений $M[i, j, A] \text{, где } j = i + 1$. При этом наши дальнейшие действия в рамках алгоритма не изменятся.

Для примера~\ref{exampl:CYK} на шаге инициализации матрица выглядит следующим образом:

\[
\begin{pmatrix}
\varnothing & \{A\}       & \varnothing & \varnothing    & \varnothing    & \varnothing & \varnothing    \\
\varnothing & \varnothing & \{A\}     & \varnothing    & \varnothing      & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing & \{B, S_2, S_3\} & \varnothing       & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing & \varnothing    & \{B, S_2, S_3\} & \varnothing & \varnothing   \\
\varnothing & \varnothing & \varnothing & \varnothing    & \varnothing    & \{A\}       & \varnothing    \\
\varnothing & \varnothing & \varnothing & \varnothing    & \varnothing    & \varnothing & \{B, S_2, S_3\} \\
\varnothing & \varnothing & \varnothing & \varnothing    & \varnothing    & \varnothing & \varnothing    \\

\end{pmatrix}
\]

А в результате работы алгоритма имеем:

\[
\begin{pmatrix}
\varnothing & \{A\}       & \varnothing & \varnothing    & \{S_1, S\}     & \varnothing & \{S_1, S\}     \\
\varnothing & \varnothing & \{A\}       & \{S_1\}        & \{S_2\}            & \varnothing & \{S_2\}        \\
\varnothing & \varnothing & \varnothing & \{B, S_2, S_3\} & \varnothing       & \varnothing & \varnothing    \\
\varnothing & \varnothing & \varnothing & \varnothing    & \{B, S_2, S_3\} & \varnothing & \{S_2, S_3\}  \\
\varnothing & \varnothing & \varnothing & \varnothing    & \varnothing    & \{A\}       & \{S_1\}            \\
\varnothing & \varnothing & \varnothing & \varnothing    & \varnothing    & \varnothing & \{B, S_2, S_3\} \\
\varnothing & \varnothing & \varnothing & \varnothing    & \varnothing    & \varnothing & \varnothing    \\
\end{pmatrix}
\]

Мы представили входную строку в виде линейного графа, а на шаге инициализации получили его матрицу смежности. Добавление нового нетерминала в язейку матрицы можно рассматривать как нахождение нового пути между соответствующими вершинами, выводимого из добавленного нетерминала. Таким образом, шаги алгоритма напоминают построение транзитивного замыкания графа. Различие заключается в том, что мы добавляем новые ребра только для тех пар нетерминалов, для которых существует соответстующее правило в грамматике.

Алгоритм можно обобщить и на произвольные графы с метками, рассматриваемые в этом курсе. При этом можно ослабить ограничение на форму входной грамматики: она должна находиться в ослабленной Нормальной Форме Хомского~(\ref{defn:wCNF}).

Шаг инициализации в алгоритме теперь состоит из двух пунктов.
\begin{itemize}
\item Как и раньше, с помощью продукций вида \[A \to a \text{, где } A \in N, a \in \Sigma\]
заменяем терминалы на ребрах входного графа на множества нетерминалов, из которых они выводятся.
\item  Добавляем в каждую вершину петлю, помеченную множеством нетерминалов для которых в данной грамматике есть правила вида $$A \to \varepsilon\text{, где } A \in N.$$
\end{itemize}

 Затем используем матрицу смежности получившегося графа (обозначим ее $M$) в качестве начального значения. Дальнейший ход алгоритма можно описать псевдокодом, представленным в листинге~\ref{alg:graphParseCYK}.

\begin{algorithm}[H]
    \begin{algorithmic}[1]
        \caption{Алгоритм КС достижимости на основе CYK}
        \label{alg:graphParseCYK}
        \Function{contextFreePathQuerying}{G, $\mathcal{G}$}

        \State{$n \gets$ the number of nodes in $\mathcal{G}$}
        \State{$M \gets$ the modified adjacency matrix of $\mathcal{G}$}
        \State{$P \gets$ the set of production rules in $G$}
        \While{$M$ is changing}
        \For {$k \in 0..n$}
            \For {$i \in 0..n$}
                \For {$j \in 0..n$}
                    \ForAll {$N_1 \in M[i, k]$, $N_2 \in M[k, j]$}
                        \If {$N_3 \to N_1 N_2 \in P$ }
                            \State{$M[i, j] \mathrel{+}= \{N_3\}$}
                        \EndIf
                    \EndFor
                \EndFor
            \EndFor
        \EndFor
        \EndWhile
        \State \Return $M$
        \EndFunction
    \end{algorithmic}
\end{algorithm}

После завершения алгоритма, если в некоторой ячейке результируюшей матрицы с номером $(i, j)$ находятся стартовый нетерминал, то это означает, что существует путь из вершины $i$ в вершину $j$, удовлетворяющий данной грамматике. Таким образом, полученная матрица является ответом для задачи достижимости для заданных графа и грамматики.

\begin{example}
\label{CYK_algorithm_ex}
Рассмотрим работу алгоритма на графе

\begin{center}
  \input{figures/graph/graph0.tex}
\end{center}

и грамматике:

\begin{align*}
S   & \to A B    & A   & \to a     \\
S   & \to A S_1  & B   & \to b\\
S_1 & \to S B   &&\\
\end{align*}

Данный пример является классическим и еще не раз будет использоваться в рамках данного курса. \\

\textbf{Инициализация.}
Заменяем терминалы на ребрах графа на нетерминалы, из которых они выводятся, и строим матрицу смежности получившегося графа:

\begin{center}
  \input{figures/cyk/graph1.tex}
\end{center}

\[
\begin{pmatrix}
\varnothing & \{A\}       & \varnothing & \varnothing \\
\varnothing & \varnothing & \{A\}       & \varnothing \\
\{A\}       & \varnothing & \varnothing & \{B\}       \\
\varnothing & \varnothing & \{B\}       & \varnothing \\
\end{pmatrix}
\]

\textbf{Итерация 1.}
Итерируемся по $k$, $i$ и $j$, пытаясь найти пары нетерминалов, для которых существуют правила вывода, их выводящие. Нам интересны следующие случаи:

\begin{itemize}
    \item $k = 2, i = 1, j = 3: A \in M[1, 2], B \in M[2, 3]$, так как в грамматике присутствует правило $S \to A B$, добавляем нетерминал $S$ в ячейку $M[1, 3]$.
    \item $k = 3, i = 1, j = 2: S \in M[1, 3], B \in M[3, 2]$, поскольку в грамматике есть правило $S_1 \to S B$, добавляем нетерминал $S_1$ в ячейку $M[1, 2]$.
\end{itemize}

В остальных случаях либо какая-то из клеток пуста, либо не существует продукции в грамматике, выводящей данные два нетерминала.

Матрица после данной итерации:

\[
\begin{pmatrix}
\varnothing & \{A\}       & \varnothing & \varnothing \\
\varnothing & \varnothing & \cellcolor{lightgray}\{A, \boldsymbol{S_1}\}  & \cellcolor{lightgray}\{S\}       \\
\{A\}       & \varnothing & \varnothing & \{B\}       \\
\varnothing & \varnothing & \{B\}       & \varnothing \\
\end{pmatrix}
\]

\textbf{Итерация 2.}
Снова итерируемся по $k$, $i$, $j$. Рассмотрим случаи:

\begin{itemize}
    \setlength\itemsep{1em}
    \item $k = 1, i = 0, j = 2: A \in M[0, 1], S_1 \in M[1, 2]$, так как в грамматике присутствует правило $S \to A S_1$, добавляем нетерминал $S$ в ячейку $M[0, 2]$.
    \item $k = 2, i = 0, j = 3: S \in M[0, 2], B \in M[2, 3]$, поскольку в грамматике есть правило $S_1 \to S B$, добавляем нетерминал $S_1$ в ячейку $M[0, 3]$.
\end{itemize}

Матрица на данном шаге:

\[
\begin{pmatrix}
\varnothing & \{A\}       & \cellcolor{lightgray}\{S\}       & \cellcolor{lightgray}\{S_1\}     \\
\varnothing & \varnothing & \{A, S_1\}  & \{S\}       \\
\{A\}       & \varnothing & \varnothing & \{B\}       \\
\varnothing & \varnothing & \{B\}       & \varnothing \\
\end{pmatrix}
\]

\textbf{Итерация 3.}
Рассматриваемые на данном шаге случаи:

\begin{itemize}
    \setlength\itemsep{1em}
    \item $k = 0, i = 2, j = 3: A \in M[2, 0], S_1 \in M[0, 3]$, так как в грамматике присутствует правило $S \to A S_1$, добавляем нетерминал $S$ в ячейку $M[2, 3]$.
    \item $k = 3, i = 2, j = 2: S \in M[2, 3], B \in M[3, 2]$, поскольку в грамматике есть правило $S_1 \to S B$, добавляем нетерминал $S_1$ в ячейку $M[2, 2]$.
\end{itemize}

Матрица после этой итерации:

\[
\begin{pmatrix}
\varnothing & \{A\}       & \{S\}      & \{S_1\}     \\
\varnothing & \varnothing & \{A, S_1\} & \{S\}       \\
\{A\}       & \varnothing & \cellcolor{lightgray}\{S_1\}    & \cellcolor{lightgray}\{B, \boldsymbol{S}\}    \\
\varnothing & \varnothing & \{B\}      & \varnothing \\
\end{pmatrix}
\]

\textbf{Итерация 4.}
Рассмариваемые случаи:

\begin{itemize}
    \setlength\itemsep{1em}
    \item $k = 2, i = 1, j = 2: A \in M[1, 2], S_1 \in M[2, 2]$, так как в грамматике присутствует правило $S \to A S_1$, добавляем нетерминал $S$ в ячейку $M[1, 2]$.
    \item $k = 2, i = 1, j = 3: S \in M[1, 2], B \in M[2, 3]$, поскольку в грамматике есть правило $S_1 \to S B$, добавляем нетерминал $S_1$ в ячейку $M[1, 3]$.
\end{itemize}

Матрица:

\[
\begin{pmatrix}
\varnothing & \{A\}       & \{S\}         & \{S_1\}     \\
\varnothing & \varnothing & \cellcolor{lightgray}\{A, \boldsymbol{S}, S_1\} & \cellcolor{lightgray}\{S, \boldsymbol{S_1}\}  \\
\{A\}       & \varnothing & \{S_1\}       & \{B, S\}    \\
\varnothing & \varnothing & \{B\}         & \varnothing \\
\end{pmatrix}
\]

\textbf{Итерация 5.}
Рассмотрим на это шаге:

\begin{itemize}
    \setlength\itemsep{1em}
    \item $k = 1, i = 0, j = 3: A \in M[0, 1], S_1 \in M[1, 3]$, поскольку в грамматике есть правило $S \to A S_1$, добавляем нетерминал $S$ в ячейку $M[0, 3]$.
    \item $k = 3, i = 0, j = 2: S \in M[0, 3], B \in M[3, 2]$, поскольку в грамматике есть правило $S_1 \to S B$, добавляем нетерминал $S_1$ в ячейку $M[0, 2]$.
\end{itemize}

Матрица на этой итерации:
\[
\begin{pmatrix}
\varnothing & \{A\}       & \cellcolor{lightgray}\{S, \boldsymbol{S_1}\}    & \cellcolor{lightgray}\{\boldsymbol{S}, S_1\}  \\
\varnothing & \varnothing & \{A, S, S_1\} & \{S, S_1\}  \\
\{A\}       & \varnothing & \{S_1\}       & \{B, S\}    \\
\varnothing & \varnothing & \{B\}         & \varnothing \\
\end{pmatrix}
\]

\textbf{Итерация 6.}
Интересующие нас на этом шаге случаи:

\begin{itemize}
    \setlength\itemsep{1em}
    \item $k = 0, i = 2, j = 2: A \in M[2, 0], S_1 \in M[0, 2]$, поскольку в грамматике есть правило $S \to A S_1$, добавляем нетерминал $S$ в ячейку $M[2, 2]$.
    \item $k = 2, i = 2, j = 3: S \in M[2, 2], B \in M[2, 3]$, поскольку в грамматике есть правило $S_1 \to S B$, добавляем нетерминал $S_1$ в ячейку $M[2, 3]$.
\end{itemize}

Матрица после данного шага:

\[
\begin{pmatrix}
\varnothing & \{A\}       & \{S, S_1\}    & \{S, S_1\}    \\
\varnothing & \varnothing & \{A, S, S_1\} & \{S, S_1\}    \\
\{A\}       & \varnothing & \cellcolor{lightgray}\{\boldsymbol{S}, S_1\}    & \cellcolor{lightgray}\{B, S, \boldsymbol{S_1}\} \\
\varnothing & \varnothing & \{B\}         & \varnothing   \\
\end{pmatrix}
\]

На следующей итерации матрица не изменяется, поэтому заканчиваем работу алгоритма. В результате, если ячейка $M[i, j]$ содержит стартовый нетерминал $S$, то существует путь из $i$ в $j$, удовлетворяющий ограничениям, заданным грамматикой.
\end{example}

Можно заметить, что мы делаем много лишних итераций.
Можно переписать алгоритм так, чтобы он не просматривал заведомо пустые ячейки.
Данную модификацию предложил Й.Хеллингс в работе~\cite{hellingsRelational}, также она реализована в работе~\cite{10.1007/978-3-319-46523-4_38}.

Псевдокод алгоритма Хеллингса представлен в листинге~\ref{alg:graphParseHellings}.

\begin{algorithm}[H]
    \begin{algorithmic}[1]
        \caption{Алгоритм Хеллингса}
        \label{alg:graphParseHellings}
        \Function{contextFreePathQuerying}{$G= \langle \Sigma, N, P, S \rangle$, $\mathcal{G} = \langle V,E,L \rangle$}

        \State{$r \gets \{(N_i,v,v) \mid v \in V \wedge N_i \to \varepsilon \in P \} \cup \{(N_i,v,u) \mid (v,t,u) \in E \wedge N_i \to t \in P \}$}
        \State{$m \gets r$}
        \While{$m \neq \varnothing$}
        \State{$(N_i,v,u) \gets$ m.pick()}
        \For {$(N_j,v',v) \in r$}
            \For {$N_k \to N_j N_i \in P$ таких что $((N_k, v',u) \notin r)$}
                \State{$m \gets  m \cup \{(N_k, v',u)\}$}
                \State{$r \gets  r \cup \{(N_k, v',u)\}$}
            \EndFor
        \EndFor
        \For {$(N_j,u,v') \in r$}
            \For {$N_k \to N_i N_j \in P$ таких что $((N_k, v, v') \notin r)$}
                \State{$m \gets  m \cup \{(N_k, v, v')\}$}
                \State{$r \gets  r \cup \{(N_k, v, v')\}$}
            \EndFor
        \EndFor

        \EndWhile
        \State \Return $r$
        \EndFunction
    \end{algorithmic}
\end{algorithm}


\begin{example}
  Запустим алгоритм Хеллингса на нашем примере.

  \textbf{Инициализация}
  $$
  m = r = \{(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2)\}
  $$

  \textbf{Итерации внешнего цикла.} Будем считеть, что $r$ и $m$ --- упорядоченные списки и $pick$ возврпщает его голову, оставляя хвост.
  Новые элементы добавляются в конец.
  \begin{enumerate}
  \item Обрабатываем $(A,0,1)$.
  Ни один из вложенных циклов не найдёт новых путей, так как для рассматриваемого ребра есть только две возможности достроить путь: $2 \xrightarrow{A} 0 \xrightarrow{A} 1$ и $0 \xrightarrow{A} 1 \xrightarrow{A} 2$
  и ни одна из соответствующих строк не выводтся в заданной грамматике.
  \item Перед началом итерации
     $$
     m = \{(A,1,2),(A,2,0),(B,2,3),(B,3,2)\},
     $$ $r$ не изменилось.
     Обрабатываем $(A,1,2)$.
     В данной ситуации второй цикл найдёт тройку $(B,2,3)$ и соответсвующее правило $S \to A \ B$.
     Это значит, что и в $m$ и в $r$ добавится тройка $(S, 1, 3)$.
  \item
   Перед началом итерации
     $$
     m = \{(A,2,0),(B,2,3),(B,3,2),(S,1,3)\},
     $$
     $$
     r= \{(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3)\}.
     $$
     Обрабатываем $(A,2,0)$.
     Внутринние циклы ничего не найдут, новых путей н появится.
   \item
   Перед началом итерации
     $$
     m = \{(B,2,3),(B,3,2),(S,1,3)\},
     $$
     $$
     r= \{(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3)\}.
     $$
     Обрабатываем $(B,2,3)$.
     Первый цикл мог бы найти $(A,1,2)$, однако при проверке во вложенном цикле выяснится, что $(S, 1, 3)$ уже найдена.
     В итоге, на данной итерации новых путей н появится.
   \item
   Перед началом итерации
     $$
     m = \{(B,3,2),(S,1,3)\},
     $$
     $$
     r= \{(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3)\}.
     $$
     Обрабатываем $(B,3,2)$.
     Первый цикл найдёт $(S,1,3)$ и соответствующее правило $S_1 \to S \ B$.
     Это значит, что и в $m$ и в $r$ добавится тройка $(S_1, 1, 2)$.
   \item
   Перед началом итерации
     $$
     m = \{(S,1,3),(S_1, 1, 2)\},
     $$
     $$
     r= \{(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2)\}.
     $$
     Обрабатываем $(S,1,3)$.
     Второй цикл мог бы найти $(B,3,2)$, однако при проверке во вложенном цикле выяснится, что $(S_1, 1, 2)$ уже найдена.
     В итоге, на данной итерации новых путей н появится.
   \item
   Перед началом итерации
     $$
     m = \{(S_1, 1, 2)\},
     $$
     $$
     r= \{(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2)\}.
     $$
     Обрабатываем $(S_1,1,2)$.
     Первый цикл найдёт $(A,0,1)$ и соответствующее правило $S \to A \ S_1$.
     Это значит, что и в $m$ и в $r$ добавится тройка $(S, 0, 2)$.

   \item
   Перед началом итерации
     $$
     m = \{(S, 0, 2)\},
     $$
     $$
     r= \{(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2)\}.
     $$
     Обрабатываем $(S, 0, 2)$.
     Найдено: $(B,2,3)$ и соответствующее правило $S_1 \to S \ B$.
     B $m$ и в $r$ добавится тройка $(S_1, 0, 3)$.

   \item
   Перед началом итерации
     $$
     m = \{(S_1, 0, 3)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3)\}.
     \end{align*}
     Обрабатываем $(S_1, 0, 3)$.
     Найдено: $(A,2,0)$ и соответствующее правило $S \to A \ S_1$.
     B $m$ и в $r$ добавится тройка $(S, 2, 3)$.

   \item
   Перед началом итерации
     $$
     m = \{(S, 2, 3)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3),(S, 2, 3)\}.
     \end{align*}

     Обрабатываем $(S, 2, 3)$.
     Найдено: $(B,3,2)$ и соответствующее правило $S_1 \to S \ B$.
     B $m$ и в $r$ добавится тройка $(S_1, 2, 2)$.

   \item
   Перед началом итерации
     $$
     m = \{(S_1, 2, 2)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3),(S, 2, 3),(S_1, 2, 2)\}.
     \end{align*}
     Обрабатываем $(S_1, 2, 2)$.
     Найдено: $(A,1,2)$ и соответствующее правило $S \to A \ S_1$.
     B $m$ и в $r$ добавится тройка $(S, 1, 2)$.

   \item
   Перед началом итерации
     $$
     m = \{(S, 1, 2)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3),(S, 2, 3),(S_1, 2, 2),(S, 1, 2)\}.
     \end{align*}
     Обрабатываем $(S, 1, 2)$.
     Найдено: $(B,2,3)$ и соответствующее правило $S_1 \to S \ B$.
     B $m$ и в $r$ добавится тройка $(S_1, 1, 3)$.

   \item
   Перед началом итерации
     $$
     m = \{(S_1, 1, 3)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3),(S, 2, 3),(S_1, 2, 2),(S, 1, 2),(S_1, 1, 3)\}.
     \end{align*}
     Обрабатываем $(S_1, 1, 3)$.
     Найдено: $(A,0,1)$ и соответствующее правило $S \to A \ S_1$.
     B $m$ и в $r$ добавится тройка $(S, 0, 3)$.

   \item
   Перед началом итерации
     $$
     m = \{(S, 0, 3)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3),(S, 2, 3),(S_1, 2, 2),(S, 1, 2),(S_1, 1, 3),(S, 0, 3)\}.
     \end{align*}
     Обрабатываем $(S, 0, 3)$.
     Найдено: $(B,3,2)$ и соответствующее правило $S_1 \to S \ B$.
     B $m$ и в $r$ добавится тройка $(S_1, 0, 2)$.

   \item
   Перед началом итерации
     $$
     m = \{(S_1, 0, 2)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3),(S, 2, 3),(S_1, 2, 2),(S, 1, 2),(S_1, 1, 3),(S, 0, 3),(S_1, 0, 2)\}.
     \end{align*}
     Обрабатываем $(S_1, 0, 2)$.
     Найдено: $(A,2,0)$ и соответствующее правило $S \to A \ S_1$.
     B $m$ и в $r$ добавится тройка $(S, 2, 2)$.

   \item
   Перед началом итерации
     $$
     m = \{(S, 2, 2)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3),(S, 2, 3),(S_1, 2, 2),(S, 1, 2),(S_1, 1, 3),(S, 0, 3),(S_1, 0, 2),\\
          &(S, 2, 2)\}.
     \end{align*}
     Обрабатываем $(S, 2, 2)$.
     Найдено: $(B,2,3)$ и соответствующее правило $S_1 \to S \ B$.
     B $m$ и в $r$ добавится тройка $(S_1, 2, 3)$.

   \item
   Перед началом итерации
     $$
     m = \{(S_1, 2, 3)\},
     $$
     \begin{align*}
     r= \{&(A,0,1),(A,1,2),(A,2,0),(B,2,3),(B,3,2),(S,1,3),(S_1, 1, 2),(S, 0, 2),\\
          &(S_1, 0, 3),(S, 2, 3),(S_1, 2, 2),(S, 1, 2),(S_1, 1, 3),(S, 0, 3),(S_1, 0, 2),\\
          &(S, 2, 2),(S_1, 2, 3)\}.
     \end{align*}
     Обрабатываем $(S_1, 2, 3)$.
     Могло бы быть найдено: $(A,1,2)$ и соответствующее правило $S \to A \ S_1$, однако тройка $(S, 1, 3)$ уже есть в $r$.
     А значит никаких новых троек найдено не будет и $m$ становится пустым.
     Это была последняя итерация внешнего цикла, в $r$ на текущий момент уже содержится всё ршение.

  \end{enumerate}

\end{example}

Как можно заметить, количество итераций внешнего цикла также получилось достаточно большим.
Проверьте, зависит ли оно от порядка обработки элементов из $m$.
При этом внутренние циклы в нашем случае достаточно короткие, так как просматриваются только ``существенные'' элементы и избегается дублирование.

%\section{Вопросы и задачи}
%\begin{enumerate}
%    \item Проверить работу алгоритма CYK для цепочек на грамматике
%    \begin{flushleft}
%    $E \to E + E$ \\
%    $E \to E * E$ \\
%    $E \to (E)$   \\
%    $E \to n$     \\
%    \end{flushleft}
%    и словах (алфавит $\Sigma = \{n, +, *, (, )\}$)
%    \begin{flushleft}
%    $ (n + n) * n$    \\
%    $ n + n * n$      \\
%    $n + n + n + n$   \\
%    $n + (n * n) + n$ \\
%    \end{flushleft}
%
%    \item Изучить вычислительную сложность алгоритма CYK для матриц в зависимости от размера входного графа (размер грамматики считать фиксированным).
%
%    \item Проверить работу алгоритма CYK для графов на графе
%
%    \begin{center}
%        \begin{tikzpicture}[node distance=3cm,shorten >=1pt,on grid,auto]
%        \node[state] (q_0)  {$0$};
%        \node[state] (q_1) [right=of q_0]  {$1$};
%        \node[state] (q_2) [right=of q_1]  {$2$};
%        \node[state] (q_3) [right=of q_2]  {$3$};
%        \node[state] (q_4) [right=of q_3]  {$4$};
%        \path[->]
%        (q_0) edge  node {$a$} (q_1)
%        (q_1) edge  node {$b$} (q_2)
%        (q_2) edge  node {$a$} (q_3)
%        (q_3) edge  node {$b$} (q_4)
%        (q_1) edge[bend left, above]  node {$b$} (q_3)
%        (q_4) edge[bend left, below]  node {$a$} (q_1);
%        \end{tikzpicture}
%    \end{center}
%
%    И грамматике
%
%    \begin{flushleft}
%        $S \to S S$ \\
%        $S \to A B$ \\
%        $A \to a$   \\
%        $B \to b$     \\
%    \end{flushleft}
%
%    \item Оцените временную сложность алгоритма Хеллингса и сравните её с оценкой для наивного обобщения CYK.
%
%\end{enumerate}