chapter-4.tex

\chapter{Конечные автоматы со спонтанными переходами}
\label{Chapter4}

\section{Определения и примеры}
\label{Chapter4Defines}

\mydef{Конечный автомат со спонтанными переходами (или 
$\eps$-переходами)} --- это одно из обобщений конечных автоматов.У 
конечного автомата появляется новое свойство --- возможность совершать 
переходы по $\eps$ (пустой цепочке), т. е. спонтанно, не получая на 
вход никакого символа. Эта новая возможность, как и недетерминизм, не 
расширяет класс языков, допустимых конечными автоматами, но дает 
некоторое дополнительное  <<удобство программирования>>.

Пусть $M = (Q,\Sigma, \delta, q_0, F)$ --- недетерминированный конечный автомат. Автомат $M$
назовем \mydef{$\eps$-НКА}, если
\[
    \delta \colon Q \times (\Sigma \cup \{ \eps \} ) \to P(Q)
\]


\begin{myexample}
Рассмотрим $\eps$-НКА, распознающий ключевые слова \emph{web} и \emph{day} в последовательности символов $\{ a..z \}$. Граф переходов этого автомата представлен на рисунке~\ref{ch4-aut-graph-3}.
\input{img/chap4/aut-graph-3}
Для каждого ключевого слова строится полная последоватльность состояний, как если бы это было единственное слово, которое автомат должен распознать. Затем добавляется новое начальное состояние (состояние 8 на рисунке~\ref{ch4-aut-graph-3}) с $\eps$-переходами в начальные состояния автоматов для каждого из ключевых слов.
\end{myexample}

\begin{myexample}
Рассмотрим $\eps$-НКА (рисунок~\ref{aut-graph-4}), допускающий запись десятичных чисел из следующих элементов $\colon$
\begin{enumerate}
   \item Необязательный знак + или $-$.
   \item Цепочка цифр.
   \item Разделяющая десятичная точка.
   \item Еще одна цепочка цифр. Эта цепочка, как и цепочка (2), может быть пустой, но хотя бы одна из них должна быть непустой.
\end{enumerate}
\input{img/chap4/aut-graph-4}

Поскольку переход из состояния $q_0$ в $q_1$ может произойти по любому из символов $+, -, \eps$, то состояние $q_1$ моделирует ситуацию, когд а прочитан знак числа (если есть), он не прочитана ни одна из цифр, ни десятичная точка. Состояние $q_2$ соответствует ситуации, когда только что прочитана десятичная точка, а цифры целой части числа либо уже прочитаны, либо нет. В состоянии $q_4$ уже наверняка прочитана хотя бы одна цифра, но еще не прочитана десятичная точка. Состояние $q_3$ определяет ситуацию, когда  прочитаны десятичная точка и хотя бы одна цифра слева или справа от нее. Автомат может оставаться в состоянии $q_3$, продолжая читать цифры, а может и <<предположить>>, что цепочка цифр закончена, и спонтанно перейти в допускающее состояние $q_5$.
$\delta$-функция переходов автомата представлена в таблице на рисунке~\ref{tab4}.
\end{myexample}

\input{img/chap4/tab4}

Пусть $M = (Q,\Sigma, \delta, q_0, F)$ --- $\eps$-НКА. Определим \mydef{$\eps$-замыкание} состояния $q \in \Sigma$ рекурсивно следующим образом:
\begin{enumerate}
   \item $E(q) \subseteq P(q)$.
   \item $q \in E(q)$.
   \item Если $p \in E(q)$ и $r \in \delta(p, \eps)$, то $r \in E(q)$.
\end{enumerate}

\begin{myexample}
\label{example-413}
Построим $\eps$-замыкание для состояния $q$ из $\eps$-НКА, заданного графом переходов (рисунок~\ref{aut-graph-5}).
\input{img/chap4/aut-graph-5}
\begin{align*}
    E^0(q_1) &= \{q_1\}; \\
    E^1(q_1) &= \{ q_1; q_2; q_4 \};\\
    E^2(q_1) &= \{ q_1; q_2; q_4; q_3 \}; \\
    E^3(q_1) &= \{ q_1; q_2; q_4; q_3; q_6 \}. \\
\end{align*}
Таким образом, $E(q_1) = \{ q_1; q_2; q_4; q_3; q_6 \} $.
\end{myexample}

Пусть $M = (Q,\Sigma, \delta, q_0, F)$ --- $\eps$-НКА и $S \subseteq Q$ --- произвольное подмножество множества $Q$. Назовем множестов $S$ \mydef{$\eps$-замкнутым}, если $S = \{ q \mid \text{если } p \in \delta(q, \eps), \text{то } p \in S \}$. Отметим, что $\es$ --- $\eps$-замкнутое множество.

\section{Редукция $\eps$-НКА к ДКА}
\label{Chapter4Reduct}
Для всякого $\eps$-НКА $E$ можно найти ДКА $D$, допускающий тот же язык, что и $E$.

\begin{mylemma}
\label{lemma-ENKAtoDKA}
Пусть $M_E = (Q_E,\Sigma, \delta_E, q_E, F_E)$ --- $\eps$-НКА. Тогда найдется такой ДКА $M_D$, что $L(M_E) = L(M_D)$.
\end{mylemma}
\begin{myproof}
По данному $\eps$-НКА построим новый ДКА $M_D = (Q_D, \Sigma, \delta_D, q_D, F_D)$ следующим образом:
\begin{enumerate}
   \item $Q_D = P(Q_E)$. Причем, достижимыми состояниями автомата $M_D$ будут только такие $S \in Q_D$, что $S$ является $\eps$-замкнутым множеством.
   \item $q_D = E(q_E)$.
   \item $F_D = \{ S \in Q_D \colon S \cap F_E \neq \es \}$.
   \item Функция переходов $\delta_D$ определим следующим образом: \newline
   если $S \in Q_D$ и $a \in \Sigma$, то $\delta_D(S,a)$ строится по правилам:
   \begin{enumerate}
   	\item пусть $\{ q_1; q_2;...;q_n \}$ --- множество состояний $S$;
    \item $\{ r_1; r_2;...;r_m \} = \bigcup_{i\in 1}^{n}\delta_E(q_i, a)$;
    \item $\delta_D(S,a) = \bigcup_{j\in 1}^{m}E(r_j)$.
   \end{enumerate}
\end{enumerate}
Доказательство корректности конструкций леммы основывается на стягивании вершин автомата по $\eps$-переходам.
\end{myproof}

\begin{figure}
%
\begin{subfigure}[b]{.5\linewidth}
\input{img/chap4/tab5}
\end{subfigure}%
%
\begin{subfigure}[b]{.5\linewidth}
\input{img/chap4/aut-graph-6}
\end{subfigure}
\caption{Описание $\eps$-НКА из примера \ref{example-reduceENKAtoDKA}}\label{fig:1}
%
\end{figure}

\begin{myexample} \label{example-reduceENKAtoDKA} Пусть $M_E = (\{ p; 
q; r \},\{ a; b; c \}, \delta_E, p, \{ r \})$ --- $\eps$-НКА. 
$\delta$-функция переходов автомата задана таблицей на рисунке~\ref{tab5}. Граф 
переходов автомата представлен на рисунке~\ref{aut-graph-6}. Пользуясь 
конструкциями из леммы~\ref{lemma-ENKAtoDKA}, по данному автомату 
построим ДКА $M_D = (Q_D, \Sigma, \delta_D, q_D, F_D)$. Начальным 
состоянием ДКА является $\eps$-замыкание начального состояния исходного 
автомата. \[
	q_D = E(p).
\]
Построим $\eps$-замыкание:
\[
	E^0(p) = \{ p \};
	E^1(p) = \{ p \}.
\]
Таким образом $q_D = \{ p \}$.

\input{img/chap4/tab6}

Аналогично начальному состоянию, построим $\eps$-замыкания для 
остальных состояний исходного автомата. $\delta$-функция переходов 
автомата $M_D$ представлена в таблице на рисунке~\ref{tab6}. Граф 
переходов автомата $M_D$  представлен на рисунке~\ref{aut-graph-7} 
(с.~\pageref{aut-graph-7}). Отметим, что множество конечных состояний 
$F_D$ содержит единственное состояние $\{ r; q; p \}$, поскольку 
состояние $\{ r \}$ было конечным состоянием исходного автомата.
\end{myexample}

\input{img/chap4/aut-graph-7}

\section{Преобразование регулярного выражения в автомат} 
\label{Chapter4RegtoFA} 

Для любого регулярного языка $L$, заданного 
регулярным выражением $R$, может быть построен $\eps$-НКА, распознающий 
этот язык. Эта возможность заложена в определение регулярного языка и 
задающего его регулярного выражения (см. 
раздел~\ref{Chapter2RegExprs}). Регулярными являются элементарные 
множества над алфавитом $\Sigma$ : пустое множество (ему соответствует 
регулярное выражение $\es$), множество из одной пустой цепочке 
(регулярное выражение $\eps$) и множество из одного однобуквенного 
слова из любой буквы $a$ множества $\Sigma$ (регулярное выражение $a$). 
Также из определения следует, что результаты объединения, конкатенации 
и итерации регулярных языков являются регулярными языками. Далее мы 
построим автоматы для элементарных языков и опишем процесс построения 
более сложных автоматов, допускающих объединение, конкатенацию или 
итерацию языков, распознаваемых более простыми автоматами.

Для связывания простых автоматов в сложные конструкции удобно 
использовать $\eps$-переходы. Условимся, что каждый автомат любой 
степени сложности будет иметь ровно один вход и один выход. Начальное 
состояние у автомата всегда единственное. Одно конечное состояние можем 
получить, если ввести новое конечное состояние и связать его 
$\eps$-переходами со старыми конечными состояниями.

Таким образом все конструируемые на основе регулярных выражений 
автоматы будут представлять собой $\eps$-НКА с одним допускающим 
состоянием.

\begin{mytheorem}
Любой язык, определяемый регулярным выражением, можно задать некоторым 
конечным автоматом. 
\end{mytheorem}

\begin{myproof}

Предположим, что $L = L(R)$ для регулярного выражения $R$. Покажем, что  
$L = L(E)$ для некоторого $\eps$-НКА $E$, обладающего следующими свойствами:
\begin{enumerate}
	\item Автомат имеет ровно одно допускающее состояние.
	\item У автомата нет дуг, ведущих в начальное состояние.
	\item У автомата нет дуг, выходящих из допускающего состояния.
\end{enumerate}
Для доказательства теоремы применим структурную индукцию по выражению $R$, 
следуя рекурсивному определению регулярных выражений из раздела~\ref{Chapter2RegExprs}.

В доказательстве леммы~\ref{lemma-FA-of-ElemLangs} построены конечные 
автоматы, распознающие элементарные языки. На рисунке~\ref{ra-struct-1}
(с.~\pageref{ra-struct-1})
приведены схемы автоматов, распознающих пустой язык (\textsl{a}), язык 
из одного символа $eps$ (\textsl{b}) и язык из одного однобуквенного 
слова (\textsl{c}). Все эти автоматы удовлетворяют условиям (1), (2), 
(3) индуктивной гипотезы.

\input{img/chap4/ra-struct-1}

Предположим, что утверждение теоремы истинно для непосредственных подвыражений данного регулярного выражения, т. е. языки этих подвыражений являются также языками $\eps$-НКА с единственным допускающим состоянием. Возможны четыре случая.
\begin{enumerate}
\item Данное выражение имеет вид $R + S$ для некоторых подвыражений $R$ и $S$. Тогда ему соответствует автомат $M_U$, представленный на рисунке~\ref{ra-struct-2_a}.

\input{img/chap4/ra-struct-2_a}

В этот автомат добавлено новое начальное состояние, из которого можно перейти в начальное состояние автомата для выражения $R$ или $S$ и продолжать работу, моделируя выбранный автомат. Попав в допускающее состояние автомата для $R$ или $S$ (распознав цепочку из языка $L(R)$ или $L(S)$ соответственно), новый автомат может по одному из $\eps$-путей перейти в свое допускающее состояние. Таким образом,  $L(M_U) = L(R) \cup L(S)$.
	\item Выражение имеет вид $RS$ для некоторых подвыражений $R$ и $S$. Автомат $M_C$ для распознавания конкатенации представлен на рисунке~\ref{ra-struct-2_b}.
	
\input{img/chap4/ra-struct-2_b}
	
Начальное состояние первого автомата становится начальным для всего автомата $M_C$, представляющего конкатенацию, а допускающим для него будет допускающее состояние второго автомата. Вначале автомат $M_C$ моделирует поведение автомата для $R$ (распознает цепочку из языка $L(R)$), потом из допускающего состояния первого автомата он переходит в начальное состояние автомата для $S$ и моделирует его поведение (распознает цепочку из языка $L(S)$). Таким образом, $L(M_C) = L(R)L(S)$.

\input{img/chap4/ra-struct-2_c}

\item Выражение имеет вид $R^*$ для некоторого подвыражения $R$. Рассмотрим автомат $M_I$, представленный на рисунке~\ref{ra-struct-2_c}. Возможные случаи распознавания:
	\begin{enumerate}
		\item из начального состояния автомат  $M_I$ сразу переходит в допускающее состояние по символу $\eps$. В этом случае допускается цепочка $\eps$, которая принадлежит $L(R^*)$ независимо от выражения $R$;
		\item из начального состояния автомат  $M_I$ переходит в начальное состояние автомата для $R$, моделирует поведение этого автомата и попадает в его допускающее состояние, из которого может начать заново моделировать автомат для $R$ или перейти в свое допускающее состояние. Такое поведение автомата дает возможность распознавать цепочки, принадлежащие языкам $L(R)$, $L(R)L(R)$, $L(R)L(R)L(R)$ ... $(R^*)$, за исключением, возможно, цепочки $\eps$. Но возможность ее распознавания показана в предыдущем пункте. Таким образом, $L(M_I) = L(R^*)$.
	\end{enumerate}

\item Выражение имеет вид $(R)$ для некоторого подвыражения $R$. Автомат для $R$ может быть автоматом и для $(R)$, поскольку скобки не влияют на язык, задаваемый выражением.

\end{enumerate}
Построенные автоматы удовлетворяют всем трем условиям индуктивной гипотезы: одно допускающее состояние, отсутствие дуг, ведущих в начальное состояние, и дуг, выходящих из допускающего состояния.
\end{myproof}

\input{img/chap4/ra-struct-example-1_a}

\begin{myexample}
Преобразуем регулярное выражение $(0 + 1)^*1(0 + 1)$ в $\eps$-НКА. Вначале построим автомат для выражения $0 + 1$. Для этого используем два автомата, построенные по схеме на рисунке~\ref{ra-struct-1}с (с.~\pageref{ra-struct-1}): один автомат с меткой $0$ на дуге, другой --- с меткой $1$. Эти автоматы соединим с помощью конструкции объединения по схеме с рисунка~\ref{ra-struct-2_a} (с.~\pageref{ra-struct-2_a}). Полученный результат представлен на рисунке~\ref{ra-struct-example-1_a} (с.~\pageref{ra-struct-example-1_a}):. 
После этого применим к полученному автомату конструкцию итерации по схеме с рисунка~\ref{ra-struct-2_c} (с.~\pageref{ra-struct-2_c}). Получим автомат, представленный на рисунке~\ref{ra-struct-example-1_b}. 

\input{img/chap4/ra-struct-example-1_b}

Осталось к полученному автомату применить конструкции конкатенации по схеме с рисунка~\ref{ra-struct-2_b} (с.~\pageref{ra-struct-2_b}). Сначала автомат, представленный на рисунке~\ref{ra-struct-example-1_b}, соединяется с автоматом, допускающим только цепочку $1$ (нужно еще раз применить конструкцию по схеме с рисунка~\ref{ra-struct-1}с с меткой $1$ на дуге). Последним автоматом в конкатенации будет еще один автомат для выражения $0 + 1$, построенный по тем же принципам, что и автомат на рисунке~\ref{ra-struct-example-1_b}.
Полный автомат для выражения $(0 + 1)^*1(0 + 1)$ представлен на рисунке~\ref{ra-struct-example-1_c} (с.~\pageref{ra-struct-example-1_c}).
\end{myexample}

\input{img/chap4/ra-struct-example-1_c}

\section{Построение $\eps$-НКА по ПЛ-грамматике}
\label{Chapter4GramtoFA}

В разделе $1.4$ приведена классификация Хомского формальных грамматик. По этой классификации ПЛ-грамматикой являются такая грамматика, все правила которой имеют вид:
\[
	\begin{array}{l}
	A \to xB, \\
	A \to x, \\
	\end{array} \qquad \text{где $A,B \in N$, $x\in\Sigma^*$.}
\]


Из леммы~\ref{lemma-dka-to-pl} известно, что для любого конечного автомата можно построить ПЛ-грамматику, порождающую тот же язык, что распознает исходный автомат. При этом получается, строго говоря, не ПЛ-грамматика, а автоматная грамматика, все правила которой имеют вид:
\[
 \begin{array}{l}
	A \to xB, \\
	A \to x, \\
	\end{array}\qquad \text{где $A,B \in N, x\in\Sigma$.}
\]

Фактически автоматная грамматика --- это ПЛ-грамматика, в правилах которой могут встречаться только одиночные терминальные буквы.
Автомат работает следующим образом: по текущему состоянию и текущему входному символу автомат переходит в следующее состояние. В формальной грамматике нетерминальные символы соответствуют состояниям, а терминальные символы - входным символом автомата. За один раз автомат может прочитать только один входной символ, который в принципе может состоять из нескольких букв, но автомат считает этот символ неделимым. С точки зрения же ПЛ-грамматики последовательность терминальных букв в правилах является частью выводимого слова.
\begin{mylemma}
\label{lemma-pl-to-nka}
Пусть задана ПЛ-грамматика $G = (\Sigma, N, \mathcal P, S \in N)$. Тогда $\exists$ такой $\eps$-НКА $M$, что $L(M) = L(G)$.
\end{mylemma}
\begin{myproof}
Построим $M = (Q, \Sigma, \delta, q_0, F)$ следующим образом:
\begin{enumerate}
	\item $Q = N \cup \{ f \}$, где $f \notin N$.
	\item $F = \{ f \}$.
	\item $q_0 = S$.
	\item Для определения $\delta$-функции введем вспомогательную $\hat{\delta}$-функцию по аналогии с конструкциями из леммы~\ref{lemma-dka-to-pl}:
		\begin{enumerate}
			\item Если $(A \to \alpha B)\in \mathcal P$, где $A, B \in N, \alpha \in \Sigma^*$, то $\hat{\delta}(A, \alpha) = B$.
			\item Если $(A \to \alpha)\in \mathcal P$, где $A \in N, \alpha \in \Sigma^*$, то $\hat{\delta}(A, \alpha) = f$.
		\end{enumerate}
		$\hat{\delta}$-функция в качестве второго входного параметра принимает цепочку (возможно, пустую) символов входного алфавита, т. е.
		\[
			\hat{\delta} \colon Q \times (\Sigma^*) \to P(Q).
		\]
		Поскольку автомат за один такт может прочитать не более одного символа входного алфавита, необходимо перейти от $\hat{\delta}$-функции к $\delta$-функции автомата $M$:
		\[
			\delta \colon Q \times (\Sigma \cup \{ \eps \} ) \to P(Q).
		\]
		Пусть $\omega \in L(M)$, тогда $(q_0,\omega)\vdash_M^*(f,\eps)$.
		Представим $\omega = \alpha_1\alpha_2...\alpha_n$. Тогда
		\[
			(q_0, \alpha_1\alpha_2...\alpha_n)\vdash_M(q_1, \alpha_2...\alpha_n)\vdash_M^*(q_{n-1}, \alpha_n)\vdash_M(f, \eps).
		\]
Дополним множество $\mathcal P$ правил грамматики $G$ правилом $S \to \alpha_1q_1$. Этому правилу будет соответствовать $\delta(q_0, \alpha_1) = \{q_1\}$.
		Повторяя эти действия для всех $\alpha_i$, получим:
		\[
			S \To^* \alpha_1\alpha_2...\alpha_{n-1}q_{n-1} \To \alpha_1...\alpha_n = \omega.
		\]
		Если $\hat{\delta}(q_1, \omega = \alpha_1\alpha_2...\alpha_k) = \{q_2\}$, то
		\[
			\begin{array}{l}
			\delta(q_1, \alpha_1) = \{q_1^{(1)}\};  \\
			\delta(q_1^{(1)}, \alpha_2) = \{q_1^{(2)}\}; \\
			... \\
			\delta(q_1^{(k-2)}, \alpha_{k-2}) = \{q_1^{(k-1)}\};\\
			\delta(q_1^{(k-1)}, \alpha_k) = \{q_2\}.
			\end{array}
		\]
	\end{enumerate}
	Таким образом, каждый такт автомата $M$ соответствует одному правилу грамматики $G$, и $L(M) = L(G)$.
\end{myproof}
\begin{myexample}
\label{ex-pl-to-nka}
	Рассмотрим грамматику $G = (\{S; T\}, \{0; 1\}, \mathcal P, S)$, где множество $\mathcal P$ состоит из следующих продукций:
	\[
			S \to 01T \mid 1S \mid \eps; \quad
			T \to 11S \mid 000T \mid 01 \mid \eps.
	\]
Построим $\eps$-НКА $M$, применяя конструкции из леммы~\ref{lemma-pl-to-nka}.
	\input{img/chap4/aut-graph-8}
\[
			Q = \{ S; T \} \cup \{ f \}; \quad
			\Sigma = \{ 0; 1 \}; \quad
			q_0 = S;\quad
			F = \{ f \}.
\]
		По правилам грамматики $G$ определим $\hat{\delta}$-функцию:
		\[
			\begin{array}{llll}
				\hat{\delta}(S, 01) = T; &
				\hat{\delta}(S, 1) = S; &
				\hat{\delta}(S, \eps) = f; &
				\hat{\delta}(T, 11) = S; \\
				\hat{\delta}(T, 000) = T; &
				\hat{\delta}(T, 01) = f; &
				\hat{\delta}(T, \eps) = f.&
		\end{array}
	\]
	Граф переходов $\hat{\delta}$-функции представлен на рисунке~\ref{aut-graph-8}.
	Для построения $\delta$-функции автомата $M$ определим множество <<промежуточных>> состояний, изменив множество $\mathcal P$ правил грамматики $G$ следующим образом:
	\[
			\begin{array}{llll}
				S \to 0S_1 \mid 1S \mid \eps; &
				S_1 \to 1T; & 
				T \to 1T_1 \mid 0T_2 \mid 0T_3 \mid 0T_4 \mid \eps; &\\
				T_1 \to 1S; &
				T_2 \to 0T_3; &
				T_3 \to 0T; &
				T_4 \to 1.
			\end{array}
	\]
	По модифицированным правилам грамматики $G$ определим ${\delta}$-функцию как показано на рисунке~\label{fig-ex-4-4}.

\begin{figure}
\label{fig-ex-4-4}
	\[
			\begin{array}{llll}
				\delta(S, 0) = S_1; &
				\delta(S_1, 1) = T; &
				\delta(S, 1) = S; &
				\delta(S, \eps) = f; \\
				\delta(T, 1) = T_1; &
				\delta(T, 0) = T_2; &
				\delta(T, 0) = T_3; &
				\delta(T, 0) = T_4; \\
				\delta(T, \eps) = f; &
				\delta(T_1, 1) = S; &
				\delta(T_2, 0) = T_3; &
				\delta(T_3, 0) = T; \\
				\delta(T_4, 1) = f. &&&
		\end{array}
	\]
\caption{Функция переходов автомата из примера~\ref{ex-pl-to-nka}.}
\end{figure}

	Множество состояний $Q$ дополняется состояниями, полученными при расширении правил грамматики $G$:
	\[
	Q = \{ S; T; F \} \cup \{ S_1; T_1; T_2; T_3; T_4 \}
	\]

	Граф искомого автомата $M = (Q, \Sigma, q_0, \delta, F)$ представлен на рисунке~\ref{aut-graph-9}.
\end{myexample}

\input{img/chap4/aut-graph-9}

\section{Вычисление языка $\eps$-НКА}
\label{Chapter4FALang}
По автомату, допускающему некоторый язык, можно построить регулярное выражение, задающее этот язык. Для этого нужно построить выражения, описывающие множества цепочек, которыми помечены определенные пути на графе переходов автомата. Эти пути могут проходить только через ограниченное подмножество состояний. При индуктивном определении таких выражений нужно начинать с самых простых выражений, описывающих пути, которые не проходят ни через одно состояние (т. е. являются отдельными вершинами или дугами). После этого индуктивно строятся выражения, которые позволяют этим путям проходить через постепенно расширяющиеся множества состояний. В конце этой процедуры будут получены пути, которые могут проходить через любые состояния, т. е. генерируются выражения, представляющие все возможные пути. Подробно эти идеи излагаются в~\cite{Hop} (раздел 3.2.1).
В данной работе будет рассмотрен менее трудоёмкий способ вычисления регулярного выражения по конечному автомату.
\subsection*{Метод последовательного исключения состояний}
Метод вычисления регулярного выражения, рассматриваемый в данном разделе, предполагает исключение состояний конечного автомата. Если исключить некоторое состояние $r$, то все пути автомата, проходящие через это состояние, исчезают. Чтобы язык, допускаемый автоматом, не изменился, необходимо написать на дуге, ведущей непосредственно из некоторого состояния $q$ в состояние $p$, метки всех тех путей, которые вели из состояния $q$ в состояние $p$, проходя через состояние $r$. Поскольку теперь метка такой дуги будет содержать цепочки, а не отдельные символы, и таких цепочек может быть даже бесконечно много, то нельзя использовать список этих цепочек в качестве метки. Необходимо использовать конечный способ представления всех подобных цепочек, т. е., использовать регулярные выражения.

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

Опишем процедуру исключения состояния.
Пусть $M = (Q, \Sigma, \delta, q_0, F)$ --- конечный автомат. Рассмотрим подграф графа переходов автомата $M$ (см. рис.~\ref{m_del_1}). Введем операцию $DEL(p, r, q)$, где $r$ --- вершина, подлежащая удалению, следующим образом:
\begin{enumerate}
	\item Если из вершины $r$ ведет дуга с меткой $\gamma$ в эту же вершину (петля), то после удаления вершины $r$ этой дуге будет соответствовать метка $\gamma^*$ (соответствие операции итерация).
	\item Если $\exists$ путь из вершины $p$ в вершину $q$, и этот путь проходит по дугам, помеченным $\alpha$, $\alpha_1$,..., $\beta$, то после удаления вершины $r$ дуга $(p, q)$ будет помечена меткой $\alpha\alpha_1,...,\beta$, составленной из меток всех дуг, образующих этот путь (соответствие операции конкатенация).
	\item Если $\exists$ другие пути, ведущие из вершины $p$ в вершину $q$, то их метки объединяются (соответствие операции объединение).
\end{enumerate}
Результат применения операции $DEL(p, r, q)$ к подграфу из рисунка~\ref{m_del_1} представлен на рисунке~\ref{m_del_2}.
\input{img/chap4/m_del_1}
\input{img/chap4/m_del_2}
\Algo{Алгоритм исключения вершины из графа конечного автомата}
{
	$\Gamma = (V, E, \phi)$ --- граф автомата $M$, где $\phi$ --- функция разметки; \\
	$r \in V$ --- вершина, которая исключается из графа автомата.
}
{$\Gamma' = (V', E', \phi)$ --- граф автомата $M$ без вершины $r$.}
{ }
{
\item Для $p \in V$, $p \neq r$ и $(p, r) \in E$ выполнить: \\
			Для $q \in V$, $q \neq r$ и $(r, q) \in E$ выполнить: \\
			$\phi(p, q) = \phi(p, q) \cup \phi(p, r)(\phi(r, r))^*\phi(r, q)$
\item  Исключить из графа $\Gamma$ вершину $q$ и инцидентные ей дуги.
}

Опишем стратегию построения регулярного выражения по конечному автомату.
\begin{enumerate}
	\item Если начальное состояние совпадает с допускающим, нужно ввести новое допускающее состояние и добавить $\eps$-переход из начального состояния в добавленное. После этого начальное состояние перестает быть допускающим.
	\item Если автомат содержит более одного допускающего состояния, то нужно ввести новое допускающее состояние и добавить $\eps$-переходы из старых допускающих состояний в добавленное состояние. Новое состояние становится единственным допускающим состоянием автомата.
	\item С помощью алгоритма~$4.5.1$ исключить все состояния, кроме начального ($q_0$) и конечного ($f$).
	\item После шагов 1-3 должен остаться автомат с двумя состояниями, подобный автомату на рисунке~\ref{excl-aut-1}. Регулярное выражение по этому автомату может быть выписано разными способами.

Рассмотрим выражение $(R + SU^*T)^*SU^*$ как один из возможных вариантов записи регулярного выражения по данному автомату. В автомате есть возможность переходить из начального состояния в него же любое количество раз, проходя по путям, метки которых принадлежат либо $L(R)$, либо $L(SU^*T)$. Выражение $SU^*T$ представляет пути, которые ведут в допускающее состояние по пути с меткой из языка $L(S)$, затем, возможно, несколько раз проходят через допускающее состояние, используя пути с метками из $L(U)$, и наконец возвращаются в начальное состояние, следуя по пути с меткой из $L(T)$. Отсюда нужно перейти в допускающее состояние, уже никогда не возвращаясь в начальное, вдоль пути с меткой из $L(S)$. Находясь в допускающем состоянии, можно произвольное количество раз вернуться в него по пути с меткой из $L(U)$.
\input{img/chap4/excl-aut-1}
\item Искомое выражение представляет собой регулярное выражение, являющееся меткой дуги из начального состояния в конечное сокращенного автомата.
\end{enumerate}

\section{Задача минимизации конечного автомата}
\label{Chapter4FALMin}

Конечный автомат распознаёт регулярный язык, для которого может существовать несколько вариантов записи в виде регулярных выражений. В разделе~\ref{Chapter4RegtoFA} показано, что любое регулярное выражение можно преобразовать в конечный автомат, распознающий тот же язык. Таким образом один и тот же язык может быть распознан различными конечными автоматами, причём эти автоматы будут эквивалентны между собой.

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

\subsection*{Отношение эквивалентности на множестве конечных автоматов}

Напомним, что отношение эквивалентности на множестве $X$ --- это бинарное отношение, для которого выполняются следующие условия:
\begin{enumerate}
\item Рефлексивность: $a \sim a$ для $\forall a \in X$.
\item Симметричность: $a \sim b$, то $b \sim a$ для $\forall a, b \in X$.
\item Транзитивность: $a \sim b$ и $b \sim c$, то $a \sim c$ для $\forall a, b, c \in X$.
\end{enumerate}

\begin{mylemma}
Конечные автоматы ($\eps$-НКА, НКА, ДКА) $M_1$ и $M_2$ над одним и тем же конечным алфавитом $\Sigma$ называются эквивалентными, если $L(M_1) = L(M_2)$.
\end{mylemma}
\begin{myproof}
Покажем, что для введённого отношения эквивалентности на конечных автоматах выполняются свойства рефлексивности, симметричности и транзитивности.
Пусть $M_{\Sigma}$ --- множество всех конечных автоматов ($\eps$-НКА, НКА, ДКА) над входным алфавитом  $\Sigma$.
\begin{enumerate}
\item Рефлексивность: $\forall M \in M_{\Sigma}$ $M \sim M \Leftrightarrow L(M) = L(M)$.
\item Симметричность: $\forall M_1, M_2 \in M_{\Sigma}$ если $M_1 \sim M_2 \Leftrightarrow M_2 \sim M_1$, то $L(M_1) = L(M_2) \Leftrightarrow L(M_2) = L(M_1)$.
\item Транзитивность: $\forall M_1, M_2, M_3 \in M_{\Sigma}$ $M_1 \sim M_2$ и  $M_2 \sim M_3 \Rightarrow M_1 \sim M_3$, т.~к. $ L(M_1) = L(M_2)$ и $L(M_2) = L(M_3) \Rightarrow L(M_1) = L(M_3)$.
\end{enumerate}
\end{myproof}
Итак, два конечных автомата ($\eps$-НКА, НКА, ДКА) считаются эквивалентными между собой, если они допускают один и тот же язык. Нам известно, что автомат любого типа ($\eps-НКА$, НКА) может быть сведён к ДКА. Тогда сформулируем задачу минимизации конечного автомата следующим образом: \\
\textit{Задача:} Для произвольного ДКА найти эквивалентный ему ДКА с минимальным числом состояний.
Минимальные ДКА всегда одинаковые. Если даны два минимальных ДКА для одного и того же языка, то всегда можно переименовать состояния так, что данные ДКА будут одинаковыми.
Для того, чтобы построить минимальный ДКА, необходимо выделить состояния, которые можно удалить, не нарушая при этом эквивалентность исходного и модифицированного ДКА.

\subsection*{Недостижимые состояния конечного автомата}
Безболезненно из конечного автомата можно удалить только те состояния, которые не участвуют в распознавании языка.

\textbf{\textit{Определение:}} Состояние $q \in Q$ конечного автомата $M = (Q,\Sigma, \delta, q_0, F)$ называется недостижимым, если $\nexists \omega \in \Sigma^* \mid (q_0, \omega) \vdash_M^* (q, \eps)$.\\
Из определения следует, что нельзя подобрать никакую цепочку, по которой можно было бы пройти от стартового состояния до недостижимого, следовательно, это состояние не используется при распознавании любых цепочек языка и может быть удалено вместе с соответствующими переходами.

\Algo{Устранение недостижимых состояний конечного автомата}
{
	Конечный автомат $M = (Q,\Sigma, \delta, q_0, F)$.
}
{
	Конечный автомат $M' = (Q',\Sigma, \delta', q_0, F')$ --- КА без недостижимых состояний, такой что $L(M) = L(M')$.
}
{
 Рекурсивное построение расширяющейся последовательности подмножеств специального вида специального вида множества $Q$.
}
{
\item Положить $Q_{D_0}=\{q_0\}$, $i=1$.
\item Положить $Q_{D_i}=\{p \mid  \forall q \in Q_{D_{i-1}} \exists \delta(q, t) = \{p\}, t \in \Sigma  \}\cup Q_{D_{i-1}}$.
\item Если $Q_{D_i}\neq Q_{D_{i-1}}$, то положить $i=i+1$ перейти к шагу 2, в противном случае положить $Q_D=Q_{D_i}$.
\item Вернуть КА $M'=(Q',\Sigma, \delta', q_0, F')$, где $Q'=Q_D\cap Q$, $F'=Q_D\cap F$, $\delta' = \delta \setminus \{ \delta(q, t) = p \mid q \in (Q \setminus Q_D), t \in \Sigma \}$.
}

\begin{myexample}
Рассмотрим детерминированный конечный автомат $M = (Q,\Sigma, \delta, q_0, F)$, заданный графом переходов на рисунке~\ref{aut-graph-10}. По алгоритму $4.6.1$ построим множество достижимых состояний $Q_D$: \\
$Q_{D_0} = \{ q_0 \}$ \\
Из вершины $q_0$ можно перейти в вершины $q_1, q_2$. Таким образом \\
$Q_{D_1} = \{ q_1, q_2 \} \cup \{ q_0 \} $ \\
Из вершин $q_1, q_2$ можно попасть в вершины $q_3, q_4$ соответственно. Таким образом \\
$Q_{D_2} = \{ q_3, q_4 \} \cup \{ q_0, q_1, q_2 \} $ \\
Из вершины $q_3$ можно попасть в вершины $q_2, q_4$, а из $q_4$ --- в вершины $q_1, q_3$. Тогда \\
$Q_{D_3} = \{ q_2, q_4, q_1, q_3 \} \cup \{ q_0, q_1, q_2, q_3, q_4 \} $, следовательно $Q_{D_2} = Q_{D_3}$ и искомое множество достижимых состояний $Q_D = \{ q_0, q_1, q_2, q_3, q_4 \}$.
Конечный автомат без недостижимых состояний, эквивалентный исходному, представлен на рисунке ~\ref{aut-graph-11}.
\end{myexample}

\input{img/chap4/aut-graph-10}
\input{img/chap4/aut-graph-11}

\subsection*{Неразличимые состояния конечного автомата}
\textit{\textbf{Определение:}} Пусть $M = (Q,\Sigma, \delta, q_0, F)$ --- детерминированный конечный автомат. Два состояния $p, q \in Q$ называются \textit{неразличимыми}, если для $\forall \omega \in \Sigma^*$ выполняется \[ (p, \omega) \vdash_M^* (f_1, \eps), (q, \omega) \vdash_M^* (f_2, \eps), \] при этом либо $f_1, f_2 \in F$, либо $f_1, f_2 \notin F$. $f_1, f_2$ могут быть двумя разными или одним состоянием.

Иными словами, состояния невозможно различить, если просто проверить, допускает ли данный КА входную цепочку, начиная работу в одном (произвольно) из этих состояний.

\textit{\textbf{Определение:}} Пусть $M = (Q,\Sigma, \delta, q_0, F)$ --- детерминированный конечный автомат. Два состояния $p, q \in Q$ называются \textit{различимыми}, если $\exists \omega \in \Sigma^*$ такая, что \[ (p, \omega) \vdash_M^* (f_1, \eps), (q, \omega) \vdash_M^* (f_2, \eps), \] при этом либо $f_1 \in F$ и $f_2 \notin F$, либо наоборот. Очевидно, что $f_1 \neq f_2$ в обязательном порядке.

Слово $\omega$ в этом случае называется различающим словом состояний $p, q$. Любая пара состояний конечного автомата либо различима, либо нет.

Рассмотрим лемму об отношении неразличимости.
\begin{mylemma}
Пусть $M = (Q,\Sigma, \delta, q_0, F)$ --- ДКА. Неразличимость является отношением эквивалентности на множестве $Q$ и разбивает $Q$ в объединение непересекающихся классов эквивалентности, каждый из которых состоит из попарно непересекающихся состояний, но при этом любая пара состояний из разных классов эквивалентности будет различимой.
\end{mylemma}
\begin{myproof}
Покажем, что для введённого отношения неразличимости на множестве состояний конечного автомата выполняются свойства рефлексивности, симметричности и транзитивности.
\begin{enumerate}
\item Рефлексивность: $\forall p \in Q$ $p \sim p \Leftrightarrow \forall \omega \in \Sigma^*$ $ (p, \omega) \vdash^* (f_1, \eps), (p, \omega) \vdash^* (f_1, \eps) $, так как $f_1 = f_1$, то $(p, p)$ --- неразличимы, следовательно $p \sim p$.
\item Симметричность: $\forall p, q \in Q$ если $p \sim q$, то $q \sim p$: \\
$\forall \omega \in \Sigma^* (p, \omega) \vdash^* (f_1, \eps), (q, \omega) \vdash^* (f_2, \eps) $. Так как $p \sim q$, то либо $f_1, f_2 \in F$, либо $f_1, f_2 \notin F$.
\item Транзитивность: $\forall p, q, r$ если $p \sim q, q \sim r$, то $p \sim r$.\\ $\forall \omega \in \Sigma^* (p, \omega) \vdash^* (f_1, \eps), (q, \omega) \vdash^* (f_2, \eps) $.
Так как $p \sim q$, то либо $f_1, f_2 \in F$, либо $f_1, f_2 \notin F$. \\
$ (q, \omega) \vdash^* (f_2, \eps), (r, \omega) \vdash^* (f_3, \eps) $.
Так как $q \sim r$, то либо $f_2, f_3 \in F$, либо $f_2, f_3 \notin F$. \\
$ (p, \omega) \vdash^* (f_1, \eps), (q, \omega) \vdash^* (f_2, \eps), (r, \omega) \vdash^* (f_3, \eps) $
и либо $f_1, f_2, f_3 \in F$, либо $f_1, f_2, f_3 \notin F$.
\end{enumerate}
\end{myproof}

\textit{\textbf{Определение:}} Пусть $M = (Q,\Sigma, \delta, q_0, F)$ --- ДКА. $q_1, q_2$ --- различимые состояния $M$.

Будем говорить, что $q_1, q_2$ --- $k$-неразличимы $q_1 \sim^k q_2$, если не существует такой цепочки $\omega$, различающей $q_1, q_2$, длина которой меньше или равна $k$.

Состояния $q_1, q_2$ неразличимы ($q_1 \sim q_2$), если они $k$-неразличимы при любом $k \geq 0$.

\begin{mylemma}
Пусть $M = (Q,\Sigma, \delta, q_0, F)$ --- ДКА c $n$ состояниями. Состояния $q_1, q_2$ неразличимы $\Leftrightarrow$ они $(n-2)$ неразличимы.
\end{mylemma}
\begin{myproof}
\textit{Необходимость} условия тривиальна. Для того, чтобы была возможность различения состояний, в конечном автомате должны быть минимум одно обычное и одно конечное состояние. Количество остальных состояний не превышает $n-2$.

\textit{Достаточность} тривиальна в тех случаях, когда множество $F$ содержит $0$ или $n$ элементов. Рассмотрим случай, когда число элементов множества $F$ отличается от $0$ или $n$.

Покажем, что
\[ \sim \subseteq \sim^{n-2} \subseteq \sim^{n-3} \subseteq \ldots \subseteq \sim^{2} \subseteq \sim^{1}  \subseteq \sim^{0} \]
Заметим, что для любых состояний $q_1, q_2$ выполняются следующие свойства:
\begin{enumerate}
\item $q_1 \sim^0 q_2 \Leftrightarrow q_1, q_2 \in F$ или $q_1, q_2 \notin F$.
\item $q_1 \sim^k q_2 \Leftrightarrow q_1 \sim^{k-1} q_2$ и $ \forall x \in \Sigma \delta(q_1, x) \sim^{k-1} \delta(q_2, x)$.
\end{enumerate}
Отношение $\sim^0$ самое грубое. Оно разбивает множество $Q$ на два класса: $F$ и $Q \setminus F$. Если $\sim^{k+1} \neq \sim^k$, то отношение $\sim^{k+1}$ содержит по крайней мере на один класс эквивалентности больше, чем $\sim^k$, т. е. оно тоньше. Поскольку каждое множество из $F$ и $Q \setminus F$ содержит не более $n-1$ элементов, можно получить не более $n-2$ последовательных утончений отношения $\sim^0$. Если $\sim^{k+1} = \sim^{k}$ для некоторого $k$, то в силу свойства $2$ $\sim^{k+1} = \sim^{k+2} = \ldots$. Таким образом, $\sim$ --- это первое из отношений $\sim^{k}$, для которых $\sim^{k+1} = \sim^{k}$.
\end{myproof}
\textit{Вывод}: если два состояния можно различить, то их можно различить с помощью входной цепочки, длина которой меньше числа состояний конечного автомата. Таким образом процесс различения любой пары состояний конечен.

\subsection*{Построение минимального конечного автомата}
Для любого конечного автомата можно найти эквивалентный ему минимальный конечный автомат. Для этого нужно убрать из исходного автомата недостижимые и неразличимые состояния. Поскольку неразличимые состояния не участвуют в распознавании цепочек, а пара неразличимых состояний не влияет на результат распознавания, то удаление этих состояний не приведёт к изменению распознаваемого языка.

\textbf{\textit{Определение:}} Полностью определённый детерминированный конечный автомат называется каноническим (приведённым), если он не содержит недостижимых состояний и любая пара состояний этого автомата различима.

\Algo{\label{algo-mini}Построение канонического автомата (Минимизация ДКА)}
{
	Полностью определённый ДКА $M = (Q,\Sigma, \delta, q_0, F)$.
}
{
	Приведённый ДКА $M' = (Q',\Sigma, \delta', q_0, F')$, такой что $L(M') = L(M)$.
}
{
	Поиск и удаление недостижимых и неразличимых состояний.
}
{
\item Применить к конечному автомату $M$ алгоритм поиска недостижимых состояний и построить конечный автомат $M_1$ без недостижимых состояний, такой что $L(M_1) = L(M)$.
\item Строить отношения эквивалентности $\sim^0, \sim^1, \ldots $ по описанию в лемме $4.6.3$ до тех пор, пока это будет возможно, т. е. $\sim^{k+1} = \sim^{k}$. Взять в качестве $\sim$ отношение $\sim^k$.
\item Построить множество $Q'$ как множество классов эквивалентности отношения $\sim$. Через $[p]$ будем обозначать класс эквивалентности отношения $\sim$, содержащий состояние $p$.
\item Построить $\delta'([p], a) = [q]$, если $\delta(p,a) = q$.
\item Обозначить $q'_0$ как $q_0$.
\item Обозначить $F'$ как $\{ [q], q \in F \}$.
\item Вернуть  $M' = (Q',\Sigma, \delta', q_0, F')$.
}

\begin{mytheorem}
Автомат $M'$, который строится алгоритмом~\ref{algo-mini}, содержит наименьшее число состояний среди всех эквивалентных ему конечных автоматов.
\end{mytheorem}

\begin{myproof} Пусть $M' = (Q',\Sigma, \delta', q_0, F')$ --- 
приведённый конечный автомат. Предположим, что существует такой КА $M_m 
= (Q_m,\Sigma, \delta_m, q_{0_m}, F_m)$, что $\backslash Q_m \backslash 
< \backslash Q' \backslash$ и $L(M_m) = L(M')$.

В силу шага 1 алгоритма все состояния автомата $M'$ достижимы. Так как 
$M_m$ имеет меньше состояний, то найдутся цепочки $\omega, x$, 
переводящие состояние $q_0$ в разные состояния, а  $q_{0_m}$ --- в одно 
и то же: $(q_{0_m}, \omega) \vdash_{M_m}^* (q, \eps)$ и $(q_{0_m}, x) 
\vdash_{M_m}^* (q, \eps)$. Следовательно, $\omega, x$ переводят автомат 
$M'$  в различимые состояния, например в $p, r$. Следовательно, 
существует такая цепочка $y$, что точно одна из цепочек $\omega y, xy$ 
принадлежит $L(M')$. Но  $\omega y, xy$ должны переводить $M_m$ в одно 
и то же состояние $s$, для которого $(q, y) \vdash_{M_m}^* (s, \eps)$. 
Таким образом, точно одна из цепочек $\omega y, xy$ не может 
принадлежать $L(M_m)$, а это противоречит предположению о том, что 
$L(M_m) = L(M')$. 
\end{myproof}

\input{img/chap4/tab7}

\begin{myexample}
Пусть $M=(\{A;B;C;D;E;F\},\{a;b\},\delta,A,\{A;F\})$ --- детерминированный полностью определённый конечный автомат, где функция переходов $\delta$ задаётся таблицей с рисунка~\ref{tab7}. Применим к автомату $M$ алгоритм $4.6.2$ минимизации ДКА и построим приведённый автомат $M'$, эквивалентный исходному.

Вначале убедимся, что все состояния автомата $M$ достижимы. Для этого проследим переходы из начального автомата во все остальные: из начального состояния $A$ достижимы состояния $F, B$. Из пары $F, B$ можно перейти в состояния $F, E, D$. Из состояний $E, D$ возможны переходы в состояния $B, C, D, A$. Таким образом, все состояния автомата $M$ достижимы.

Начнём разбиение множества $Q$ на классы неразличимости:
\begin{itemize}
\item \textit{Неразличимость цепочками длины $0 (\sim^0)$.} На этом этапе множество состояний разбивается на два класса финальных и обычных состояний. Чтобы отличить финальное состояние от нефинального, цепочка не требуется. В результате получим два непересекающихся подмножества множества $Q$: $[A;F], [B;C;D;E]$.
\item \textit{Неразличимость цепочками длины $1 (\sim^1)$.} Здесь будем работать с каждым классом, выделенным на предыдущем шаге. Неразличимость цепочками длины $1$ означает, что переход по одной букве из проверяемой пары состояний приводит в одинаковые по типу состояния. Проверим пару состояний $[A;F]$. Из состояния $A$ по букве $a$ попадаем в финальное состояние $F$, по букве $b$ --- в обычное состояние $B$. Из состояния $F$ по букве $a$ попадаем в финальное состояние $F$, по букве $b$ --- в обычное состояние $E$. Таким образом, переход по одной букве (любой из алфавита $\Sigma$ не различает состояния, множество неразличимый состояний стабилизировалось. Мы нашли первую группу неразличимых состояний $[A;F]$. Проверим пары состояний из множества $[B;C;D;E]$. Для установления неразличимости цепочками длины 1 достаточно посмотреть на правую часть таблицы переходов. Если в паре строк для проверяемых состояний справа финальные и нефинальные состояния расположены одинаково, то эти состояния находятся в классе неразличимости $\sim^1$. В данном примере будут выделены следующие классы неразличимости цепочками длины $1$: $[B;E]$ и $[C;D]$.

\begin{figure}[t]

\begin{subfigure}[b]{.5\linewidth}
\centering
\begin{tabular}{rlll}
		 \midrule
		 $$ & $\sim^1$ & $$ & $\sim^2$ \\
     \midrule
     $B$ & $\{E,D\}$ & $E$ & $\{B,C\}$ \\
     $E$ & $\{B,C\}$ & $D$ & $\{D,\textbf{A}\}$ \\
     $$ & $$        & $B$ & $\{E,D\}$ \\
     $$  & $$        & $C$ & $\{C,\textbf{F}\}$ \\
     \bottomrule
\end{tabular}
\caption{Для пары состояний $[B;E]$}
\label{min-check-1}
\end{subfigure}
%
\begin{subfigure}[b]{.5\linewidth}
\centering
\begin{tabular}{rlll}
		 \midrule
		 $$ & $\sim^1$ & $$ & $\sim^2$ \\
     \midrule
     $C$ & $\{C,\textbf{F}\}$ & $C$ & $\{C,\textbf{F}\}$ \\
     $D$ & $\{D,\textbf{A}\}$ & $F$ & $\{\textbf{F},E\}$ \\
     $$ & $$        & $D$ & $\{D,\textbf{A}\}$ \\
     $$  & $$        & $A$ & $\{\textbf{F},B\}$ \\
     \bottomrule
    \end{tabular}
    \caption{Для пары состояний $[C;D]$}
    \label{min-check-2}
\end{subfigure}

\caption{Проверка неразличимости состояний}
\end{figure}

\item \textit{Неразличимость цепочками длины $0 (\sim^2)$.} На этом шаге нам осталось проверить, различимы ли пары  $[B;E]$ и $[C;D]$ цепочками терминалов длины $2$. Для этого из каждой пары состояний нужно сделать два перехода по всем комбинациям цепочек длины $2$ и сравнить пары состояний, в которых автомат остановился. Проверим пару состояний $[B;E]$ (рисунок~\ref{min-check-1}). Жирным в таблице выделены финальные состояния. Заметим, что расположение финальных и обычных состояний в таблице одинаково, следовательно рассматриваемая пара состояний неразличима цепочками длины $2$.

Проверим пару состояний $[C;D]$, как показано на рисунке~\ref{min-check-2} (с.~\pageref{min-check-2}).
В получившейся таблице расположение финальных и нефинальных состояний одинаково, следовательно пара $[C;D]$ неразличима цепочками длины $2$.

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

\input{img/chap4/tab8}

В результате выделены три класса неразличимости: $X = [A;F]$, $Y = [B;E]$ и $Z = [C;D]$. Минимальный автомат $M' = (\{X;Y;Z\},\{a;b\},\delta',X,\{X\})$ задаётся таблицей переходов с рисунка~\ref{tab8} (с.~\pageref{tab8}).
\end{itemize}
\end{myexample}

В примере $4.6.2$ показан принцип разбиения множества состояний 
конечного автомата на классы неразличимости. Для простых случаев вести 
<<дневник>> переходов достаточно просто, но если нужно установить 
неразличимость цепочками длины больше $3$, то запись переходов будет 
очень громоздкой. В \cite{Hop} изложена методика поиска неразличимых 
состояний путём заполнения таблицы. В данном случае громоздкий 
<<дневник>> переходов представляется в компактной форме таблицы 
неразличимости.

\begin{figure}[t]

\begin{subfigure}[b]{.5\linewidth}
\centering
\begin{tabular}{llllll}
\cline{2-2}
\multicolumn{1}{l|}{B} & \multicolumn{1}{l|}{} &                       &                       &                       &                       \\ \cline{2-3}
\multicolumn{1}{l|}{C} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} &                       &                       &                       \\ \cline{2-4}
\multicolumn{1}{l|}{D} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} &                       &                       \\ \cline{2-5}
\multicolumn{1}{l|}{E} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} &                       \\ \cline{2-6}
\multicolumn{1}{l|}{\textbf{F}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \cline{2-6}
                       & \textbf{A}                     & B                     & C                     & D                     & E
\end{tabular}
\caption{}
\label{min-tab-1}
\end{subfigure}
%
\begin{subfigure}[b]{.5\linewidth}
\centering
\begin{tabular}{llllll}
\cline{2-2}
\multicolumn{1}{l|}{B}          & \multicolumn{1}{l|}{X} &                        &                        &                        &                        \\ \cline{2-3}
\multicolumn{1}{l|}{C}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{}  &                        &                        &                        \\ \cline{2-4}
\multicolumn{1}{l|}{D}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  &                        &                        \\ \cline{2-5}
\multicolumn{1}{l|}{E}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{}  &                        \\ \cline{2-6}
\multicolumn{1}{l|}{\textbf{F}} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} \\ \cline{2-6}
                                & \textbf{A}             & B                      & C                      & D                      & E
\end{tabular}
    \caption{}
    \label{min-tab-2}
\end{subfigure}

\caption{}
\end{figure}

\begin{figure}[t]

\begin{subfigure}[b]{.5\linewidth}
\centering
\begin{tabular}{llllll}
\cline{2-2}
\multicolumn{1}{l|}{B}          & \multicolumn{1}{l|}{X} &                        &                        &                        &                        \\ \cline{2-3}
\multicolumn{1}{l|}{C}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} &                        &                        &                        \\ \cline{2-4}
\multicolumn{1}{l|}{D}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{}  &                        &                        \\ \cline{2-5}
\multicolumn{1}{l|}{E}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} &                        \\ \cline{2-6}
\multicolumn{1}{l|}{\textbf{F}} & \multicolumn{1}{l|}{}  & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} \\ \cline{2-6}
                                & \textbf{A}             & B                      & C                      & D                      & E
\end{tabular}
\caption{}
\label{min-tab-3}
\end{subfigure}
%
\begin{subfigure}[b]{.5\linewidth}
\centering
\begin{tabular}{llllll}
\cline{2-2}
\multicolumn{1}{l|}{B}          & \multicolumn{1}{l|}{X} &                        &                        &                        &                        \\ \cline{2-3}
\multicolumn{1}{l|}{C}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} &                        &                        &                        \\ \cline{2-4}
\multicolumn{1}{l|}{D}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{O} &                        &                        \\ \cline{2-5}
\multicolumn{1}{l|}{E}          & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{O} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} &                        \\ \cline{2-6}
\multicolumn{1}{l|}{\textbf{F}} & \multicolumn{1}{l|}{O} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} & \multicolumn{1}{l|}{X} \\ \cline{2-6}
                                & \textbf{A}             & B                      & C                      & D                      & E
\end{tabular}
    \caption{}
    \label{min-tab-4}
\end{subfigure}

\caption{}
\end{figure}
 

\begin{myexample} Еще раз рассмотрим автомат из примера $4.6.2$. Пусть 
$M=(\{A;B;C;D;E;F\},\{a;b\},\delta,A,\{A;F\})$ --- детерминированный 
полностью определённый конечный автомат, где функция переходов $\delta$ 
задаётся таблицей с рисунка~\ref{tab7}. В примере $4.6.2$ установлено, 
что этот автомат не содержит недостижимых состояний. Подготовим для 
множества $Q$ таблицу неразличимости как показано на рисунке~\ref{min-tab-1}.

Принцип заполнения таблицы следующий: в ячейку ставим $X$, если пара состояний, соответствующая этой ячейке, различима. На первом шаге расставим $X$ в ячейках, соответсвующих парам финальных и обычных состояний (установим неразличимость состояний цепочками длины $0$) — рисунок~\ref{min-tab-2}.

Далее по таблице переходов определяем пары неразличимых состояний цепочками длины $1$. Для этого нам достаточно сравнить строки справа и посмотреть расположение финальных и нефинальных состояний. Получим следующую таблицу неразличимости с рисунка~\ref{min-tab-3}.

Незаполненными остались ячейки на пересечении пар состояний $[F;A]$, $[E;B]$, $[D;C]$. Рассмотрим пару $[F;A]$. По таблице переходов из состояния $F$ можно попасть в состояния $F, E$ по одной букве, а из состояния $A$ --- в состояния $F, B$. В результате получается, что буква $a$ не различает состояния $[F;A]$, поскольку переводит автомат в одно и то же состояние $F$. Буква $b$ переводит автомат из состояний $F, A$ в состояния $B, E$ соответственно. В таблице неразличимости на пересечении этих состояний пока нет отметки о неразличимости. Можем условно поставить в ячейку на пересечении состояний $[F;A]$ знак вопроса и перейти к исследованию пары состояний $[E;B]$. Для этой пары состояний буква $a$ переводит автомат в те же состояния (перекрёстно), а буква $b$ переводит автомат в состояния $D, C$. Для этой пары в таблице нет отметки о неразличимости, поэтому ставим знак вопроса и переходим к анализу пары состояний  $[D;C]$. Буква $a$ переводит автомат в ту же пару состояний $C, D$, а $b$ --- в пару состояний $F, A$, для которой мы уже поставили в таблицу знак вопроса. В итоге круг замкунлся, и мы выделили пары неразличимых состояний (рисунок~\ref{min-tab-4}).

Далее можно переобозначить выделенные классы неразличимости: $X = [A;F]$, $Y = [B;E]$ и $Z = [C;D]$. Минимальный автомат $M'$, эквивалентный исходному автомату $M$, уже построен в примере $4.6.2$.
\end{myexample}


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

\subsection*{Построение $\eps$"/НКА по регулярному выражению}

Построить $\eps$"/НКА по следующим регулярным выражениям:
\begin{enumerate}
	\item $R = (a+b+c)(bab)*(a+b)$;
  \item $R = 1(10+10)^*1(0+1)^*$;
  \item $R = (a^*b^*)^*+(ab+b)^*$.
\end{enumerate}
Для каждого полученного $\eps$"/НКА построить соответствующий ему ДКА. 
\subsection*{Построение $\eps$"/НКА по ПЛ"/грамматике}
Построить $\eps$"/НКА по грамматикам со стартовым символом $S$ и продукциями:
\begin{align*}
    \text{(1) }&
        \begin{aligned}%{l}
            S &\to 10A \mid 101A,\\
            A &\to 0A \mid 1B,\\
            B &\to 1 \mid 0;
        \end{aligned}
        \qquad
    &
    \text{(2) }&
        \begin{aligned}%{l}
            S &\to abaA \mid abB,\\
            A &\to a \mid aaB \mid baC,\\
            B &\to b \mid abaC,\\
            C &\to aaB \mid a;
		        \end{aligned}
        \qquad
    &
    \text{(3) }&
        \begin{aligned}%{l}
            S &\to xA \mid B,\\
            A &\to yxyA \mid \eps \mid xB,\\
            B &\to b \mid \eps.
        \end{aligned}
\end{align*}
Методом исключения состояний определить язык для каждого полученного автомата.
\subsection*{Минимизация конечного автомата}
Минимизировать конечные автоматы, заданные таблицами переходов, а также определить язык полученных автоматов методом исключения состояний:
\begin{multicols}{2}
\begin{enumerate}
  \item
     \begin{tabular}{rlll}
     \toprule
     \multirow{2}{*}{\Large $\delta$}
      & \multicolumn{3}{c}{\text{Вход}} \\
     \cmidrule(rl){2-4}
        & \multicolumn{1}{c}{a}
        & \multicolumn{1}{c}{b}
        &\multicolumn{1}{c}{$\eps$}\\
     \midrule
     ${}\to A$ & $\{B; C\}$ & $\{C\}$  & $\{D\}$\\
     $B$ & $\{C\}$ & $\{D\}$ &  \\
     $C$ & $\{B; C\}$ & $\{D\}$ &  \\
     $\boxed{D}$ & $\emptyset$ & $\emptyset$ &  \\
     \bottomrule
    \end{tabular}
		\qquad\qquad
  \item
     \begin{tabular}{rll}
     \toprule
     \multirow{2}{*}{\Large $\delta$}
      & \multicolumn{2}{c}{\text{Вход}} \\
     \cmidrule(rl){2-3}
        & \multicolumn{1}{c}{a}
        &\multicolumn{1}{c}{b}\\
     \midrule
     ${}\to q_1$ & $q_2$ & $q_4$\\
     $q_2$ & $q_2$ & $q_3$\\
		 \boxed{q_3} & $q_4$ & $q_5$\\
     $q_4$ & $q_4$ & $q_5$\\
     \boxed{q_5} & $q_2$ & $q_3$\\
     \bottomrule
    \end{tabular}
\end{enumerate}
\end{multicols}

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