TensorProduct.tex

\chapter{КС достижимость через тензорное произведение}

Предыдущий подход позволяет выразить задачу поиска путей с ограничениями в терминах формальных языков через набор матричных операций.
Это позволяет использовать высокопроизводительные библиотеки, массовопараллельные архитектуры и другие готовые решения для линейной алгебры.
Однако, такой подход требует, чтобы грамматика находилась в ослабленной нормальной форме Хомского, что приводит к её разрастанию.
Можно ли как-то избежать этого?

В данном разделе мы предложим альтернативное сведение задачи поиска путей к матричным операциям.
В результате мы сможем избежать преобразования грамматики в ОНФХ, однако, матрицы, с которыми нам предётся работать, будут существенно б\'{о}льшего размера.

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



\section{Тензорное произведение}
\label{section2}

Теперь перейдём к графам.
Сперва дадим классическое определение тензорного произведения двух неориентированных графов.

\begin{definition}
Пусть даны два графа: $\mathcal{G}_1 = \langle V_1, E_1\rangle$ и $\mathcal{G}_2 = \langle V_2, E_2\rangle$.
Тензорным произведением этих графов будем называть граф $\mathcal{G}_3 = \langle V_3, E_3\rangle$, где $V_3 = V_1 \times V_2$, $E_3 = \{ ((v_1,v_2),(u_1,u_2)) \mid (v_1,u_1) \in E_1 \text{ и } (v_2,u_2) \in E_2 \}$.
\end{definition}

Иными словами, тензорным произведением двух графов является граф, такой что:
\begin{enumerate}
 \item множество вершин --- это прямое произведение множеств вершин исходных графов;
 \item ребро между вершинами $v=(v_1,v_2)$ и $u=(u_1,u_2)$ существует тогда и только тогда, когда существуют рёбра между парами вершин $v_1$, $u_1$ и $v_2$, $u_2$ в соответствующих графах.
\end{enumerate}

Для того, чтобы построить тензорное произведение ориентированных графов, необходимо в предыдущем определении, в условии существования ребра в результирующем графе, дополнительно потребовать, чтобы направления рёбер совпадали.
Данное требование получается естественным образом, если считать, что пары вершин, задающие ребро, упорядочены, поэтому формальное определение отличаться не будет.

Осталось добавить метки к рёбрам.
Это приведёт к логичному усилению требования к существованию ребра: метки рёбер в исходных графах должны совпадать.
Таким образом, мы получаем следующее определение тензорного произведения ориентированных графов с метками на рёбрах.

\begin{definition}
Пусть даны два ориентированных графа с метками на рёбрах: $\mathcal{G}_1 = \langle V_1, E_1, L_1 \rangle$ и $\mathcal{G}_2 = \langle V_2, E_2, L_2 \rangle$.
Тензорным произведением этих графов будем называть граф $\mathcal{G}_3 = \langle V_3, E_3, L_3\rangle$, где $V_3 = V_1 \times V_2$, $E_3 = \{ ((v_1,v_2),l,(u_1,u_2)) \mid (v_1,l,u_1) \in E_1 \text{ и } (v_2,l,u_2) \in E_2 \}$, $L_3=L_1 \cap L_2$.
\end{definition}

Нетрудно заметить, что матрица смежности графа $\mathcal{G}_3$ равна тензорному произведению матриц смежностей исходных графов $\mathcal{G}_1$ и $\mathcal{G}_2$.

\begin{example}
Рассмотрим пример.
В качестве одного из графов возьмём рекурсивный автомат, построенный ранее (изображение~\ref{input1}).
Его матрица смежности выглядит следующим образом.
\[ M_1 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [S] & [b] \\
. & . & . & [b] \\
. & . & . & .
\end{pmatrix}
\]

\begin{align}
\label{input2}
    \input{figures/graph/graph0.tex}
\end{align}

Второй граф представлен на изображении~\ref{input2}.
Его матрица смежности имеет следующий вид.
\[ M_2 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [a] & . \\
[a] & . & . & [b] \\
. & . & [b] & .
\end{pmatrix}
\]

Теперь вычислим $M_1 \otimes M_2$.
\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
M_3 &= M_1 \otimes M_2 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [S] & [b] \\
. & . & . & [b] \\
. & . & . & .
\end{pmatrix}
\otimes
\begin{pmatrix}
. & [a] & . & . \\
. & . & [a] & . \\
[a] & . & . & [b] \\
. & . & [b] & .
\end{pmatrix}
=\notag\\
&=
\label{eq:graph_tm}
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  .   & [a] & .   & .  &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  .   & .   & [a] & .  &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  [a] & .   & .   & .  &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  .   & .   & .   & .  &  . & . & . & .  &  . & . & . & .   \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .
\end{array}\right)
\end{scaledalign}

\end{example}

\section{Алгоритм}

Идея алгоритма основана на обобщении пересечения двух конечных автоматов до пересечения рекурсивного автомата, построенного по грамматике, со входным графом.

Пересечение двух конечных автоматов --- тензорное произведение соответствующих графов.
Пересечение языков коммутативно, тензорное произведение нет, но, как было сказано в замечании~\ref{note:KronIsNotCommutative}, существует решение этой проблемы.

Будем рассматривать два конечных автомата: одни получен из входного графа, второй из грамматики.
Можно найти их пересечение, вычислив тензорное произведение матриц смежности соответствующих графов.
Однако, одной такой итерации не достаточно для решения исходной задачи. За первую итерацию мы найдём только те пути, которые выводятся в грамматике за одни шаг. После этого необходимо добавить соответствующие рёбра во входной граф и повторить операцию: так мы найдём пути, выводимые за два шага. Данные действия надо повторять до тех пор, пока не перестанут находиться новые пары достижимых вершин.
Псевдокод, описывающий данные действия, представлен в листинге~\ref{lst:algo1}.

\begin{algorithm}
  \floatname{algorithm}{Listing}
%\begin{algorithmic}[1]
%\caption{Поиск путей через тензорное произведение}
%\label{lst:algo1}
%\Function{contextFreePathQueryingTP}{G, $\mathcal{G}$}
%    \State{$R \gets$ рекурсивный автомат для $G$}
%    \State{$N \gets$ нетерминальный алфавит для $R$}
%    \State{$S \gets$ стартовые состояния для $R$}
%    \State{$F \gets$ конечные состояния для $R$}
%    \State{$M_1 \gets$ матрица смежности $R$}
%    \State{$M_2 \gets$ матрица смежности $\mathcal{G}$}
%    \For{$N_i \in N$}
%       \If{$N_i \xrightarrow{*} \varepsilon$}
%          \State{for all $j \in \mathcal{G}.V: M_2[j,j] \gets M_2[j,j] \cup \{N_i\}$}
%          \Comment{Добавим петли для нетерминалов, выводящих $\varepsilon$}
%       \EndIf
%    \EndFor
%    \While{матрица $M_2$ изменяется}
%        \State{$M_3 \gets M_1 \otimes M_2$}
%        \Comment{Пересечение графов}
%        \State{$tC_3 \gets \textit{transitiveClosure}(M_3)$}
%        \State{$n \gets$ количество строк и столбцов матрицы $M_3$}
%        \Comment{размер матрицы $M_3$ = $n \times n$}
%        \For{$i \in 0..n$}
%           \For{$j \in 0..n$}
%                \If{$tC_3[i,j]$}
%                    \State{$s \gets$ стартовая вершина ребра $tC_3[i,j]$}
%                    \State{$f \gets$ конечная вершина ребра $tC_3[i,j]$}
%                    \If{$s \in S$ and $f \in F$ }
%                        \State{$x, y \gets$ $getCoordinates(i,j)$}
%                        \State{$M_2[x,y] \gets M_2[x,y] \cup \{getNonterminals(s,f)\}$}
%                    \EndIf
%                \EndIf
%           \EndFor
%        \EndFor
%    \EndWhile
%\State \Return $M_2$
%\EndFunction
%\end{algorithmic}
\end{algorithm}


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

Представленный алгоритм не требует преобразования грамматики в ОНФХ, более того, рекурсивный автомат может быть минимизирован. Однако, результатом тензорного рпоизведения является матрица существенно б\'{о}льшего размера, чем в алгоритме, основанном на матричном рпоизведении.
Кроме этого, необходимо искать транзитивное замыкание этой матрицы.

Ещё одним важным свойством представленного алгоритма является его оптимальность при обработке регулярных запросов.
Так как по контекстно свободной грамматике мы не можем определить, задаёт ли она регулярный язык, то при добавлении в язык запросов возможности задавать контекстно-свободные ограничения, возникает проблема: мы не можем в общем случае отличить регулярный запрос от контекстно-свободного. Следовательно, мы вынуждены применять наиболее общий механизм выполнения заросов, что может приводить к существенным накладным расходам при выполнении регулярного запроса.
Данный же алгоритм не выполнит лишних действий, так как сразу выполнит классическое пересечение двух автоматов и получит результат.

\section{Примеры}

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

\begin{example}
\label{algorithm_example}
Теоретически худший случай.
Такой же как и для матричного.

\textbf{Итерация 1 (конец).} Начало в разделе~\ref{section2}, где мы вычислили тензорное произведение матриц смежности.
Теперь нам осталось только вычислить транзитивное замыкание полученной матрицы:

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
tc(M_3) =
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & .  &  . & . & . & .\\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & .  &  . & . & . & \bfgray{[ab]}   \\
. & . & . & .  &  [a] & . & . & .  &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .  &  . & . & . & .
\end{array}\right).
\end{scaledalign}

Мы видим, что в результате транзитивного замыкания появилось новое ребро с меткой $ab$ из вершины $(0,1)$ в вершину $(3,3)$.
Так как вершина 0 является стартовой в рекурсивном автомате, а 3 является финальной, то слово вдоль пути из вершины 1 в вершину 3 во входном графе выводимо из нетерминала $S$.
Это означает, что в графе должно быть добавлено ребро из $0$ в $3$ с меткой $S$, после чего граф будет выглядеть следующим образом:

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

Матрица смежности обновлённого графа:
\[ M_2 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [a] & \textbf{[S]} \\
[a] & . & . & [b] \\
. & . & [b] & .
\end{pmatrix}
\]

Итерация закончена.
Возвращаемся к началу цикла и вновь вычисляем тензорное произведение.

\textbf{Итерация 2.}
Вычисляем тензорное произведение матриц смежности.

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
M_3 &= M_1 \otimes M_2 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [S] & [b] \\
. & . & . & [b] \\
. & . & . & .
\end{pmatrix}
\otimes
\begin{pmatrix}
. & [a] & . & . \\
. & . & [a] & [S] \\
[a] & . & . & [b] \\
. & . & [b] & .
\end{pmatrix}
=\notag\\
&=
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  [a] & . & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & \bfgray{[S]}  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .
\end{array}\right)
\end{scaledalign}

Вычисляем транзитивное замыкание полученной матрицы:

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
tc(M_3) =
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & \bfgray{[aS]}  &  . & . & \bfgray{[aSb]} & .   \\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & .              &  . & . & .              & [ab]   \\
. & . & . & .  &  [a] & . & . & .  &  . & . & . & .              &  . & . & .              & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & .              & .   \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .    \\
. & . & . & .  &  . & . & . & .    &  . & . & . & [S]            &  . & . & \bfgray{[Sb]}    & .    \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & .    & [b]  \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & [b]  & .    \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .
\end{array}\right)
\end{scaledalign}

В транзитивном замыкании появилось три новых ребра, однако только одно из них соединяет вершины, соответствующие стартовому и конечному состоянию входного рекурсивного автомата.
Таким образом только это ребро должно быть добавлено во входной граф.
В итоге, обновлённый граф:
\begin{center}
\input{figures/tensor/graph1.tex}
\end{center}

И его матрица смежности:
\[ M_2 =
\begin{pmatrix}
. & [a] & [S] & . \\
. & . & [a] & [S] \\
[a] & . & . & [b] \\
. & . & [b] & .
\end{pmatrix}
\]
\textbf{Итерация 3.}
Снова начинаем с тензорного произведения.

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
M_3 &= M_1 \otimes M_2 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [S] & [b] \\
. & . & . & [b] \\
. & . & . & .
\end{pmatrix}
\otimes
\begin{pmatrix}
. & [a] & [S] & . \\
. & . & [a] & [S] \\
[a] & . & . & [b] \\
. & . & [b] & .
\end{pmatrix}
=\notag\\
&=
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  [a] & . & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & \bfgray{[S]} & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & [S]  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & .    &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & .    &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .
\end{array}\right)
\end{scaledalign}

Затем вычисляем транзитивное замыкание:

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
tc(M_3) =
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & [aS]           &  . & . & [aSb] & .     \\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & .              &  . & . & .     & [ab]  \\
. & . & . & .  &  [a] & . & . & .  &  . & . & \bfgray{[aS]} & .  &  . & . & .     & \bfgray{[aSb]} \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & .     & .     \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & [S] & .            &  . & . & .    & \bfgray{[Sb]}    \\
. & . & . & .  &  . & . & . & .    &  . & . & . & [S]            &  . & . & [Sb] & .    \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & .    & [b]  \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & [b]  & .    \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .
\end{array}\right)
\end{scaledalign}

И наконец обновляем граф:
\begin{center}
\input{figures/tensor/graph2.tex}
\end{center}

Матрица смежности обновлённого графа:
\[ M_2 =
\begin{pmatrix}
. & [a] & [S] & . \\
. & . & [a] & [S] \\
[a] & . & . & [b, \textbf{S}] \\
. & . & [b] & .
\end{pmatrix}
\]
Уже можно заметить закономерность: на каждой итерации мы добавляем ровно одно новое ребро во входной граф, ровно как и в алгоритме, основанном на матричном произведении, и как в алгоритме Хеллингса.
То есть находим ровно одну новую пару вершин, между которыми существует интересующий нас путь.
Попробуйте спрогнозировать, сколько итераций нам ещё осталось сделать.

\textbf{Итерация 4}.
Продолжаем. Вычисляем тензорное произведение.

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
M_3 &= M_1 \otimes M_2 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [S] & [b] \\
. & . & . & [b] \\
. & . & . & .
\end{pmatrix}
\otimes
\begin{pmatrix}
. & [a] & [S] & . \\
. & . & [a] & [S] \\
[a] & . & . & [b,S] \\
. & . & [b] & .
\end{pmatrix}
=\notag\\
&=
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  [a] & . & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & [S] & .             &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & [S]           &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & \bfgray{[S]}  &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & .             &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .
\end{array}\right)
\end{scaledalign}

Затем транзитивное замыкание:

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
tc(M_3) =
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & [aS]           &  . & . & [aSb]          & .     \\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & \bfgray{[aS]}  &  . & . & \bfgray{[aSb]} & [ab]  \\
. & . & . & .  &  [a] & . & . & .  &  . & . & [aS] & .           &  . & . & .              & [aSb] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & .              & .     \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & [S] & .            &  . & . & .             & [Sb]    \\
. & . & . & .  &  . & . & . & .    &  . & . & . & [S]            &  . & . & [Sb]          & .    \\
. & . & . & .  &  . & . & . & .    &  . & . & . & [S]            &  . & . & \bfgray{[Sb]} & [b]  \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & [b]           & .    \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .              &  . & . & . & .
\end{array}\right)
\end{scaledalign}

И снова обновляем граф, так как в транзитивном замыкании появился один (и снова ровно один) новый элемент, соответствующий принимающему пути в автомате.
\begin{center}
\input{figures/tensor/graph3.tex}
\end{center}


Матрица смежности обновлённого графа:
\[ M_2 =
\begin{pmatrix}
. & [a] & [S] & . \\
. & . & [a, \textbf{S}] & [S] \\
[a] & . & . & [b,S] \\
. & . & [b] & .
\end{pmatrix}
\]
\textbf{Итерация 5.}
Приступаем к выполнению следующей итерации основного цикла.
Вычисляем тензорное произведение.

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
M_3 &= M_1 \otimes M_2 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [S] & [b] \\
. & . & . & [b] \\
. & . & . & .
\end{pmatrix}
\otimes
\begin{pmatrix}
. & [a] & [S] & . \\
. & . & [a,S] & [S] \\
[a] & . & . & [b,S] \\
. & . & [b] & .
\end{pmatrix}
=\notag\\
&=
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  [a] & . & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & [S]          & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & \bfgray{[S]} & [S]  &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & .            & [S]  &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & .            & .    &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .
\end{array}\right)
\end{scaledalign}

Затем вычисляем транзитивное замыкание:

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
tc(M_3) =
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & \bfgray{[aS]} & [aS]  &  . & . & [aSb] & \bfgray{[aSb]}  \\
. & . & . & .  &  . & . & [a] & .  &  . & . & .             & [aS]  &  . & . & [aSb] & [ab]          \\
. & . & . & .  &  [a] & . & . & .  &  . & . & [aS]          & .     &  . & . & .     & [aSb]         \\
. & . & . & .  &  . & . & . & .    &  . & . & .             & .     &  . & . & .     & .             \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & [S] & .             &  . & . & .    & [Sb]    \\
. & . & . & .  &  . & . & . & .    &  . & . & [S] & [S]           &  . & . & [Sb] & \bfgray{[Sb]}    \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & [S]           &  . & . & [Sb] & [b]  \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & .             &  . & . & [b]  & .    \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & .    & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & .    & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & .    & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & [b]  & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & . & .
\end{array}\right)
\end{scaledalign}

Обновляем граф:
\begin{center}
  \input{figures/tensor/graph4.tex}
\end{center}


Матрица смежности обновлённого графа:
\[ M_2 =
\begin{pmatrix}
. & [a] & [S] & \textbf{[S]} \\
. & . & [a, S] & [S] \\
[a] & . & . & [b,S] \\
. & . & [b] & .
\end{pmatrix}
\]
\textbf{Итерация 6.}
И наконец последняя содержательная итерация основного цикла.

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
M_3 &= M_1 \otimes M_2 =
\begin{pmatrix}
. & [a] & . & . \\
. & . & [S] & [b] \\
. & . & . & [b] \\
. & . & . & .
\end{pmatrix}
\otimes
\begin{pmatrix}
. & [a] & [S] & [S] \\
. & . & [a,S] & [S] \\
[a] & . & . & [b,S] \\
. & . & [b] & .
\end{pmatrix}
=\\
&=
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & [a] & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  [a] & . & . & .  &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & [S] & \bfgray{[S]}    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & [S] & [S]             &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & [S]             &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & .               &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & [b] & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .    &  . & . & . & .
\end{array}\right)
\end{scaledalign}

Транзитивное замыкание:

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
tc(M_3) =
\left(\begin{array}{c c c c | c c c c | c c c c | c c c c }
. & . & . & .  &  . & [a] & . & .  &  . & . & [aS] & [aS]           &  . & . & [aSb]          & [aSb]  \\
. & . & . & .  &  . & . & [a] & .  &  . & . & .    & [aS]           &  . & . & [aSb]          & [ab]          \\
. & . & . & .  &  [a] & . & . & .  &  . & . & [aS] & \bfgray{[aS]}  &  . & . & \bfgray{[aSb]} & [aSb]         \\
. & . & . & .  &  . & . & . & .    &  . & . & .    & .              &  . & . & .              & .             \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & [S] & \bfgray{[S]}    &  . & . & \bfgray{[Sb]}  & [Sb]    \\
. & . & . & .  &  . & . & . & .    &  . & . & [S] & [S]             &  . & . & [Sb] & [Sb]    \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & [S]             &  . & . & [Sb] & [b]  \\
. & . & . & .  &  . & . & . & .    &  . & . & .   & .               &  . & . & [b]  & .    \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & .    & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & .    & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & .    & [b] \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & [b]  & . \\
\hline
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & . & .   \\
. & . & . & .  &  . & . & . & .    &  . & . & . & .               &  . & . & . & .
\end{array}\right)
\end{scaledalign}

Обновлённый граф:
\begin{center}
\input{figures/tensor/graph5.tex}
\end{center}


И матрица смежности:
\[ M_2 =
\begin{pmatrix}
. & [a] & [S] & [S] \\
. & . & [a, S] & [S] \\
[a] & . & \textbf{[S]} & [b,S] \\
. & . & [b] & .
\end{pmatrix}
\]
Следующая итерация не приведёт к изменению графа.
Читатель может убедиться в этом самостоятельно.
Соответственно, алгоритм можно завершать.
Нам потребовалось семь итераций (шесть содержательных и одна проверочная), на каждой из которых вычисляются тензорное произведение двух матриц смежности и транзитивное замыкание результата.

Матрица смежности получилась такая же, как и раньше, ответ правильный.
Мы видим, что количество итераций внешнего цикла такое же как и у алгоритма CYK (пример~\ref{CYK_algorithm_ex}).

\end{example}


\begin{example}

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

Интуитивно понятно, что чем меньше состояний в рекурсивной сети, тем лучше.
То есть желательно получить как можно более компактное описание контекстно-свободного языка.

Для примера возьмём в качестве КС языка язык Дика на одном типе скобок и опишем его двумя различными грамматиками.
Первая грамматика классическая:
\[
G_1 = \langle \{a,\ b\}, \{ S \}, \{S \to a \ S \ b \ S \mid \varepsilon  \} \rangle
\]
Во второй грамматике мы будем использовать конструкции регулярных выражений в правой части правил.
То есть вторая грамматика находится в EBNF (Расширенная форма Бэкуса-Наура~\cite{Hemerik2009, Wirth1977}).
\[
G_2 = \langle \{a, \ b\}, \{S\}, \{S \to (a \ S \ b)^{*}\} \rangle
\]
Построим рекурсивные автоматы $N_1$ и $N_2$ и их матрицы смежности для этих грамматик.

Рекурсивный автомат $N_1$ для грамматики $G_1$:
\begin{center}
\begin{tikzpicture}[node distance=2cm,shorten >=1pt,on grid,auto]
   \node[state, initial, accepting] (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, accepting] (q_4) [right=of q_3] {$4$};
    \path[->]
    (q_0) edge  node {a} (q_1)
    (q_1) edge  node {S} (q_2)
    (q_2) edge  node {b} (q_3)
    (q_3) edge  node {S} (q_4);
\end{tikzpicture}
\end{center}

Матрица смежности $N_1$:
\[
M_1^1 =
\begin{pmatrix}
. & [a] & .   & .   & .  \\
. & .   & [S] & .   & .  \\
. & .   & .   & [b] & .  \\
. & .   & .   & .   & [S] \\
. & .   & .   & .   & .
\end{pmatrix}
\]
Рекурсивный автомат $N_2$ для грамматики $G_2$:
\begin{center}
  \input{figures/tensor/recursive.tex}
\end{center}

Матрица смежности $N_2$:
\[
M_1^2 =
\begin{pmatrix}
.   & [a] & .    \\
.   & .   & [S]  \\
[b] & .   & .
\end{pmatrix}
\]
Первое очевидное наблюдение --- количество состояний в $N_2$ меньше, чем в $N_1$.
Это значит, что матрица смежности, а значит, и результат тензорного произведения будут меньше, следовательно, вычисления будут производиться быстрее.

Выполним пошагово алгоритм для двух заданных рекурсивных сетей на линейном входе:
\begin{center}
\begin{tikzpicture}[node distance=2cm,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$};
   \node[state] (q_5) [right=of q_4] {$5$};
   \node[state] (q_6) [right=of q_5] {$6$};
    \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_4) edge  node {a} (q_5)
    (q_5) edge  node {b} (q_6);
\end{tikzpicture}
\end{center}


Сразу дополним матрицу смежности нетерминалами, выводящими пустую строку, и получим следующую матрицу:
\begin{scaledalign}{\footnotesize}{0.5pt}{0.9}{\notag}
M_2 =
\begin{pmatrix}
[S] & [a] & .   & .   & .   & .   & .   \\
.   & [S] & [b] & .   & .   & .   & .   \\
.   & .   & [S] & [a] & .   & .   & .   \\
.   & .   & .   & [S] & [b] & .   & .   \\
.   & .   & .   & .   & [S] & [a] & .   \\
.   & .   & .   & .   & .   & [S] & [b] \\
.   & .   & .   & .   & .   & .   & [S]
\end{pmatrix}
\end{scaledalign}

Сперва запустим алгоритм на данном входе и $N_2$.
Первый шаг первой итерации --- вычисление тензорного произведения $M_1^2 \otimes M_2$.

\begin{scaledalign}{\footnotesize}{2pt}{0.9}{\notag}
M_3 &= M_1^2 \otimes M_2 =
\begin{pmatrix}
.   & [a] & .    \\
.   & .   & [S]  \\
[b] & .   & .
\end{pmatrix}
\otimes
\begin{pmatrix}
[S] & [a] & .   & .   & .   & .   & .   \\
.   & [S] & [b] & .   & .   & .   & .   \\
.   & .   & [S] & [a] & .   & .   & .   \\
.   & .   & .   & [S] & [b] & .   & .   \\
.   & .   & .   & .   & [S] & [a] & .   \\
.   & .   & .   & .   & .   & [S] & [b] \\
.   & .   & .   & .   & .   & .   & [S]
\end{pmatrix}
=\notag\\
&=
\left(\begin{array}{c c c c c c c | c c c c c c c | c c c c c c c }
. & . & . & . & . & . & .  &  . & [a] & . & .   & . & .   & .  &  . & . & . & . & . & . & . \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & . \\
. & . & . & . & . & . & .  &  . & .   & . & [a] & . & .   & .  &  . & . & . & . & . & . & . \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & . \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & [a] & .  &  . & . & . & . & . & . & . \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & . \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & . \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & . & . & . & . & . & . \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & [S] & . & . & . & . & . \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [S] & . & . & . & . \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & [S] & . & . & . \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & [S] & . & . \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & [S] & . \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & [S] \\
\hline
. & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & . \\
. & . & [b] & . & .   & . & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & . \\
. & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & . \\
. & . & .   & . & [b] & . & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & . \\
. & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & . \\
. & . & .   & . & .   & . & [b]  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & . \\
. & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .
\end{array}\right)
\end{scaledalign}


\newcommand{\tinybf}[1]{\cellcolor{lightgray}\textbf{\tiny{[#1]}}}
\newcommand{\tntm}[1]{\text{\tiny{#1}}}

Опустим промежуточные шаги вычисления транзитивного замыкания $M_3$ и сразу представим конечный результат:
\begin{scaledalign}{\footnotesize}{0.5pt}{0.5}{\notag}
&tc(M_3)=
\left(\begin{array}{c c c c c c c | c c c c c c c | c c c c c c c }
. & . & \tinybf{aSb} & . & \tinybf{aSbaSb} & . & \tinybf{aSbaSbaSb}           &         . & [a] & . & \tinybf{aSba} & . & \tinybf{aSbaSba} & .         &           .   & \tinybf{aS} & .   & \tinybf{aSbaS} & .   & \tinybf{aSbaSbaS} & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & \tinybf{aSb}    & . & \tinybf{aSbaSb}              &         . & .   & . & [a]           & . & \tinybf{aSba}    & .         &           .   & .           & .   & \tinybf{aS}    & .   & \tinybf{aSbaS}    & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & .               & . & \tinybf{aSb}                 &         . & .   & . & .             & . & [a]              & .         &           .   & .           & .   & .              & .   & \tinybf{aS}       & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
\hline
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           [S] & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & [S]         & .   & .              & .   & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & [S] & .              & .   & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & [S]            & .   & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & [S] & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & [S]               & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & [S] \\
\hline
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & [b]          & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & [b]             & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & .               & . & [b]                          &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & . \\
. & . & .            & . & .               & . & .                            &         . & .   & . & .             & . & .                & .         &           .   & .           & .   & .              & .   & .                 & .
\end{array}\right)
\end{scaledalign}

В результате вычисления транзитивного замыкания появилось большое количество новых рёбер, однако нас будут интересовать только те, информация о которых храниться в левом верхнем блоке.
Остальные рёбра не соответствуют принимающим путям в рекурсивном автомате (убедитесь в этом самостоятельно).

После добавления соответствующих рёбер, мы получим следующий граф:
\begin{center}
\begin{tikzpicture}[node distance=2cm,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$};
   \node[state] (q_5) [right=of q_4] {$5$};
   \node[state] (q_6) [right=of q_5] {$6$};
    \path[->]
    (q_0) edge  node {a} (q_1)
    (q_0) edge[bend left, above]  node {\textbf{S}} (q_2)
    (q_0) edge[bend right, above]  node {\textbf{S}} (q_4)
    (q_0) edge[bend right, above]  node {\textbf{S}} (q_6)
    (q_1) edge  node {b} (q_2)
    (q_2) edge  node {a} (q_3)
    (q_2) edge[bend left, above]  node {\textbf{S}} (q_4)
    (q_2) edge[bend right, above]  node {\textbf{S}} (q_6)
    (q_3) edge  node {b} (q_4)
    (q_4) edge  node {a} (q_5)
    (q_4) edge[bend left, above]  node {\textbf{S}} (q_6)
    (q_5) edge  node {b} (q_6);
\end{tikzpicture}
\end{center}


Его матрица смежности:

\begin{scaledalign}{\footnotesize}{0.5pt}{0.9}{\notag}
M_2 =
\begin{pmatrix}
[S] & [a] & \bfgray{[S]} & .   & \bfgray{[S]} & .   & \bfgray{[S]} \\
.   & [S] & [b]          & .   & .            & .   & .            \\
.   & .   & [S]          & [a] & \bfgray{[S]} & .   & \bfgray{[S]} \\
.   & .   & .            & [S] & [b]          & .   & .            \\
.   & .   & .            & .   & [S]          & [a] & \bfgray{[S]} \\
.   & .   & .            & .   & .            & [S] & [b]          \\
.   & .   & .            & .   & .            & .   & [S]
\end{pmatrix}
\end{scaledalign}

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

Теперь запустим алгоритм на второй грамматике и том же входе.

\begin{scaledalign}{\footnotesize}{0.5pt}{0.8}{\notag}
&M_3 = M_1^1 \otimes M_2 =
\begin{pmatrix}
. & [a] & .   & .   & .  \\
. & .   & [S] & .   & .  \\
. & .   & .   & [b] & .  \\
. & .   & .   & .   & [S] \\
. & .   & .   & .   & .
\end{pmatrix}
\otimes
\begin{pmatrix}
[S] & [a] & .   & .   & .   & .   & .   \\
.   & [S] & [b] & .   & .   & .   & .   \\
.   & .   & [S] & [a] & .   & .   & .   \\
.   & .   & .   & [S] & [b] & .   & .   \\
.   & .   & .   & .   & [S] & [a] & .   \\
.   & .   & .   & .   & .   & [S] & [b] \\
.   & .   & .   & .   & .   & .   & [S]
\end{pmatrix}
=\notag\\
&=
\left(\begin{array}{c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c}
. & . & . & . & . & . & .  &  . & [a] & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & [a] & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & [a] & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & [S] & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [S] & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & [S] & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & [S] & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & [S] & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & [S]  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [b] & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & [b] & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & [b]  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & [S] & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [S] & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & [S] & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & [S] & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & [S] & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & [S]   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .
\end{array}\right)
\end{scaledalign}

Уже сейчас можно заметить, что размер матриц, с которыми нам придётся работать, существенно увеличился, по сравнению с предыдущим вариантом.
Это, конечно, закономерно, ведь в рекурсивном автомате для предыдущего варианта меньше состояний, а значит и матрица смежности имеет меньший размер.

Транзитивное замыкание:
\begin{scaledalign}{\footnotesize}{0.3pt}{0.5}{\notag}
&tc(M_3)=
\left(\begin{array}{c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c}
. & . & . & . & . & . & .   &   . & [a] & . & .   & . & .   & .   &   . & \tinybf{aS} & . & .           & . & .           & .  &  . & . & \tinybf{aSb} & . & .            & . & .             &  . & . & \tinybf{aSbS} & . & .             & . & .   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .   \\
. & . & . & . & . & . & .   &   . & .   & . & [a] & . & .   & .   &   . & .           & . & \tinybf{aS} & . & .           & .  &  . & . & .            & . & \tinybf{aSb} & . & .             &  . & . & .             & . & \tinybf{aSbS} & . & .   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & [a] & .   &   . & .           & . & .           & . & \tinybf{aS} & .  &  . & . & .            & . & .            & . & \tinybf{aSb}  &  . & . & .             & . & .             & . & \tinybf{aSbS}   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .   \\
\hline
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   [S] & .   & .   & .   & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & [S] & .   & .   & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & [S] & .   & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & [S] & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & [S] & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & .   & [S] & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & .   & .   & [S]  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [b] & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & [b] & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & [b]  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & [S] & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [S] & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & [S] & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & [S] & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & [S] & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & [S]   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .
\end{array}\right)
\end{scaledalign}

Обновлённый граф:
\begin{center}
\begin{tikzpicture}[node distance=2cm,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$};
   \node[state] (q_5) [right=of q_4] {$5$};
   \node[state] (q_6) [right=of q_5] {$6$};
    \path[->]
    (q_0) edge  node {a} (q_1)
    (q_0) edge[bend left, above]  node {\textbf{S}} (q_2)
    (q_1) edge  node {b} (q_2)
    (q_2) edge  node {a} (q_3)
    (q_2) edge[bend left, above]  node {\textbf{S}} (q_4)
    (q_3) edge  node {b} (q_4)
    (q_4) edge  node {a} (q_5)
    (q_4) edge[bend left, above]  node {\textbf{S}} (q_6)
    (q_5) edge  node {b} (q_6);
\end{tikzpicture}
\end{center}


Его матрица смежности:

\begin{scaledalign}{\footnotesize}{0.5pt}{0.9}{\notag}
M_2 =
\begin{pmatrix}
[S] & [a] & \bfgray{[S]} & .   & .            & .   & .            \\
.   & [S] & [b]          & .   & .            & .   & .            \\
.   & .   & [S]          & [a] & \bfgray{[S]} & .   & .            \\
.   & .   & .            & [S] & [b]          & .   & .            \\
.   & .   & .            & .   & [S]          & [a] & \bfgray{[S]} \\
.   & .   & .            & .   & .            & [S] & [b]          \\
.   & .   & .            & .   & .            & .   & [S]
\end{pmatrix}
\end{scaledalign}

Потребуется ещё одна итерация.

\begin{scaledalign}{\footnotesize}{0.5pt}{0.8}{\notag}
&M_3 = M_1^1 \otimes M_2 =
\begin{pmatrix}
. & [a] & .   & .   & .  \\
. & .   & [S] & .   & .  \\
. & .   & .   & [b] & .  \\
. & .   & .   & .   & [S] \\
. & .   & .   & .   & .
\end{pmatrix}
\otimes
\begin{pmatrix}
[S] & [a] & [S] & .   & .   & .   & .   \\
.   & [S] & [b] & .   & .   & .   & .   \\
.   & .   & [S] & [a] & [S] & .   & .   \\
.   & .   & .   & [S] & [b] & .   & .   \\
.   & .   & .   & .   & [S] & [a] & [S] \\
.   & .   & .   & .   & .   & [S] & [b] \\
.   & .   & .   & .   & .   & .   & [S]
\end{pmatrix}
=\notag\\
&=
\left(\begin{array}{c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c}
. & . & . & . & . & . & .  &  . & [a] & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & [a] & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & [a] & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & .   & \bfgray{[S]} & .   & .            & .   & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & [S] & .            & .   & .            & .   & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & [S]          & .   & \bfgray{[S]} & .   & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .            & [S] & .            & .   & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .            & .   & [S]          & .   & \bfgray{[S]}  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .            & .   & .            & [S] & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .            & .   & .            & .   & [S]           &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [b] & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & [b] & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & [b]  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & .   & \bfgray{[S]} & .   & .            & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & [S] & .            & .   & .            & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & [S]          & .   & \bfgray{[S]} & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .            & [S] & .            & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .            & .   & [S]          & .   & \bfgray{[S]}   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .            & .   & .            & [S] & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .            & .   & .            & .   & [S]   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .
\end{array}\right)
\end{scaledalign}

Транзитивное замыкание:
\begin{scaledalign}{\footnotesize}{0.3pt}{0.5}{\notag}
&tc(M_3)=
\left(\begin{array}{c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c}
. & . & . & . & . & . & .   &   . & [a] & . & .   & . & .   & .   &   . & \tntm{[aS]} & . & \tinybf{aS} & . & .           & .  &  . & . & \tntm{[aSb]} & . & \tinybf{aSb} & . & .             &  . & . & \tntm{[aSbS]} & . & \tinybf{aSbS} & . & .               \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .               \\
. & . & . & . & . & . & .   &   . & .   & . & [a] & . & .   & .   &   . & .           & . & \tntm{[aS]} & . & \tinybf{aS} & .  &  . & . & .            & . & \tntm{[aSb]} & . & \tinybf{aSb}  &  . & . & .             & . & \tntm{[aSbS]} & . & \tinybf{aSbS}   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .               \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & [a] & .   &   . & .           & . & .           & . & \tntm{[aS]} & .  &  . & . & .            & . & .            & . & \tntm{[aSb]}  &  . & . & .             & . & .             & . & \tntm{[aSbS]}   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .               \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .               \\
\hline
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   [S] & .   & [S] & .   & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & [S] & .   & .   & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & [S] & .   & [S] & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & [S] & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & [S] & .   & [S]  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & .   & [S] & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & .   & .   & [S]  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [b] & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & [b] & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & [b]  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & .   & [S] & .   & .   & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & [S] & .   & .   & .   & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & [S] & .   & [S] & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & [S] & .   & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & [S] & .   & [S]   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & .   & [S] & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & .   & .   & [S]   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .
\end{array}\right)
\end{scaledalign}

Обновлённый граф:
\begin{center}
\begin{tikzpicture}[node distance=2cm,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$};
   \node[state] (q_5) [right=of q_4] {$5$};
   \node[state] (q_6) [right=of q_5] {$6$};
    \path[->]
    (q_0) edge  node {a} (q_1)
    (q_0) edge[bend left, above]  node {S} (q_2)
    (q_0) edge[bend right, above]  node {\textbf{S}} (q_4)
    (q_1) edge  node {b} (q_2)
    (q_2) edge  node {a} (q_3)
    (q_2) edge[bend left, above]  node {S} (q_4)
    (q_2) edge[bend right, above]  node {\textbf{S}} (q_6)
    (q_3) edge  node {b} (q_4)
    (q_4) edge  node {a} (q_5)
    (q_4) edge[bend left, above]  node {S} (q_6)
    (q_5) edge  node {b} (q_6);
\end{tikzpicture}
\end{center}

На этом шаге мы смогли ``склеить'' из подстрок, выводимых из $S$, более длинные пути.
Однако, согласно правилам грамматики, мы смогли ``склеить'' только две подстроки в единое целое.

Матрица смежности обновлённого графа:

\begin{scaledalign}{\footnotesize}{0.5pt}{0.9}{\notag}
M_2 =
\begin{pmatrix}
[S] & [a] & [S]          & .   & \bfgray{[S]} & .   &              \\
.   & [S] & [b]          & .   & .            & .   & .            \\
.   & .   & [S]          & [a] & [S]          & .   & \bfgray{[S]} \\
.   & .   & .            & [S] & [b]          & .   & .            \\
.   & .   & .            & .   & [S]          & [a] & [S]          \\
.   & .   & .            & .   & .            & [S] & [b]          \\
.   & .   & .            & .   & .            & .   & [S]
\end{pmatrix}
\end{scaledalign}

И, наконец, последняя содержательная итерация.

\begin{scaledalign}{\footnotesize}{0.5pt}{0.8}{\notag}
&M_3 = M_1^1 \otimes M_2 =
\begin{pmatrix}
. & [a] & .   & .   & .  \\
. & .   & [S] & .   & .  \\
. & .   & .   & [b] & .  \\
. & .   & .   & .   & [S] \\
. & .   & .   & .   & .
\end{pmatrix}
\otimes
\begin{pmatrix}
[S] & [a] & [S] & .   & [S] & .   & .   \\
.   & [S] & [b] & .   & .   & .   & .   \\
.   & .   & [S] & [a] & [S] & .   & [S] \\
.   & .   & .   & [S] & [b] & .   & .   \\
.   & .   & .   & .   & [S] & [a] & [S] \\
.   & .   & .   & .   & .   & [S] & [b] \\
.   & .   & .   & .   & .   & .   & [S]
\end{pmatrix}
=\notag\\
&=
\left(\begin{array}{c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c}
. & . & . & . & . & . & .  &  . & [a] & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & [a] & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & [a] & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & .   & . & .   & . & .   & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & .   & [S] & .   & \bfgray{[S]} & .   & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & [S] & .   & .   & .            & .   & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & [S] & .   & [S]          & .   & \bfgray{[S]}  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & [S] & .            & .   & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & [S]          & .   & [S]           &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & .            & [S] & .             &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & .            & .   & [S]           &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [b] & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & [b] & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & [b]  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & .   & [S] & .   & \bfgray{[S]} & .   & .             \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & [S] & .   & .   & .            & .   & .             \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & [S] & .   & [S]          & .   & \bfgray{[S]}  \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & [S] & .            & .   & .             \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & [S]          & .   & [S]           \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & .            & [S] & .             \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & .            & .   & [S]           \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .
\end{array}\right)
\end{scaledalign}

Транзитивное замыкание:
\begin{scaledalign}{\footnotesize}{0.3pt}{0.5}{\notag}
&tc(M_3)=
\left(\begin{array}{c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c | c c c c c c c}
. & . & . & . & . & . & .   &   . & [a] & . & .   & . & .   & .   &   . & \tntm{[aS]} & . & \tntm{[aS]} & . & \tinybf{aS} & .  &  . & . & \tntm{[aSb]} & . & \tntm{[aSb]} & . & \tinybf{aSb}  &  . & . & \tntm{[aSbS]} & . & \tntm{[aSbS]} & . & \tinybf{aSbS}   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .               \\
. & . & . & . & . & . & .   &   . & .   & . & [a] & . & .   & .   &   . & .           & . & \tntm{[aS]} & . & \tntm{[aS]} & .  &  . & . & .            & . & \tntm{[aSb]} & . & \tntm{[aSb]}  &  . & . & .             & . & \tntm{[aSbS]} & . & \tntm{[aSbS]}   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .               \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & [a] & .   &   . & .           & . & .           & . & \tntm{[aS]} & .  &  . & . & .            & . & .            & . & \tntm{[aSb]}  &  . & . & .             & . & .             & . & \tntm{[aSbS]}   \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .               \\
. & . & . & . & . & . & .   &   . & .   & . & .   & . & .   & .   &   . & .           & . & .           & . & .           & .  &  . & . & .            & . & .            & . & .             &  . & . & .             & . & .             & . & .               \\
\hline
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   [S] & .   & [S] & .   & [S] & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & [S] & .   & .   & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & [S] & .   & [S] & .   & [S]  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & [S] & .   & .   & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & [S] & .   & [S]  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & .   & [S] & .    &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .   &   . & . & . & . & . & . & .   &   .   & .   & .   & .   & .   & .   & [S]  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & [b] & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & [b] & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & [b]  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & .   & . & .   & . & .    &  . & . & . & . & . & . & .   \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  [S] & .   & [S] & .   & [S] & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & [S] & .   & .   & .   & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & [S] & .   & [S] & .   & [S] \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & [S] & .   & .   & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & [S] & .   & [S] \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & .   & [S] & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  .   & .   & .   & .   & .   & .   & [S] \\
\hline
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .   \\
. & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .  &  . & . & . & . & . & . & .
\end{array}\right)
\end{scaledalign}


В конечном итоге мы получаем такой же результат, как и при первом запуске.
Однако нам потребовалось выполнить существенно больше итераций внешнего цикла, а именно четыре (три содержательных и одна проверочная).
При этом, в ходе работы нам пришлось оперировать существенно б\'{о}льшими матрицами: $35 \times 35$ против $21 \times 21$.

Таким образом, видно, что минимизация представления запроса, в частности, минимизация рекурсивного автомата как конечного автомата над смешанным алфавитом может улучшить производительность выполнения запросов.
\end{example}

\section{Особенности реализации}

Как и алгоритмы, представленные в разделе~\ref{chpt:MatrixBasedAlgos}, представленный здесь алгоритм оперирует разреженными матрицами, поэтому, к нему применимы все те же соображения, что и к алгоритмам, основанным на произведении матриц. Более того, так как результат тензорного произведения является блочной матрицей, то могут оказаться полезными различные форматы для хранения блочно-разреженных матриц. Вместе с этим, в некоторых случаях матрицу смежности рекурсивного автомата удобнее представлять в классическом, плотном, виде, так как для некоторых запросов её размер мал и накладные расходы на представление в разреженном формате и работе с ним будут больше, чем выигрыш от его использования.


Также заметим, что блочная структура матриц даёт хорошую основу для распределённого умножения матриц при построении транзитивного замыкания.

Вместо того, чтобы перезаписывать каждый раз матрицу смежности входного графа $M_2$ можно вычислять только разницу с предыдущим шагом.
Для этого, правда, потребуется хранить в памяти ещё одну матрицу.
Поэтому нужно проверять, что вычислительно дешевле: поддерживать разницу и потом каждый раз поэлементно складывать две матрицы или каждый раз вычислять полностью произведение.

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

%\section{Вопросы и задачи}
%
%\begin{enumerate}
%    \item Оценить пространсвенную сложность алгоритма.
%    \item Оценить временную сложность алгоритма.
%    \item Найти библиотеку для тензорного произведения. Реализовать алгоритм. Можно предпологать, что запросы содержат ограниченное число терминалов и нетерминалов. Провести замеры. Сравнить с матричным.
%    \item Реализовать распределённое решение.
%См. блочную структуру
%\end{enumerate}