03.tex

\setcounter{section}{2}

\section{Мінімізація детермінованих скінчених \texorpdfstring{\\}{} автоматів}

\subsection{Мінімізація детермінованих скінчених \texorpdfstring{\\}{} автоматів}

В подальшому при програмуванні скінчених автоматів важливо мати справу з так званими  ``мінімальними автоматами''. \textit{Мінімальним} для даного скінченого автомата називається еквівалентний йому автомат з мінімальною кількістю станів. \medskip

Нагадаємо, що два автомати називаються \textit{еквівалентними} якщо вони розпізнають одну мову. \medskip

Те, що скінчені автомати можна мінімізувати покажемо на наступному прикладі:
\begin{figure}[H]
	\centering
	\input{img/4}
\end{figure}

Навіть при поверхневому аналізі діаграми переходів наведеного скінченого автомата видно, що вершини $q_3$, $q_4$ та $q_5$ є ``зайвими'', тобто при їх вилученні новий автомат буде еквівалентний початковому. З наведеного вище прикладу видно, що для отриманого детермінованого скінченого автомата можна запропонувати еквівалентний йому автомат з меншою кількістю станів, тобто мінімізувати скінчений автомат. Очевидно що серед зайвих станів цього автомата є недосяжні та тупикові стани.

\subsubsection{Недосяжні стани}

Стан $q$ скінченого автомата $M$ називається \textit{недосяжним}, якщо на діаграмі переходів скінченого автомата не існує шляху з $q_0$ в $q$. \medskip

\textbf{Алгоритм [пошуку недосяжних станів].} Спочатку спробуємо побудувати множину досяжних станів. Якщо $Q_m$ --- множина досяжних станів скінченого автомата $M$, то $Q \setminus Q_m$ --- множина недосяжних станів. Побудуємо послідовність множин $Q_0, Q_1, Q_2, \ldots$ таким чином, що:
\begin{enumerate}
	\item $Q_0 = \{q_0\}$.
	\item $Q_i = Q_{i-1} \cup \left\{ q \mid \exists a \in \Sigma, q_j \in Q_{i - 1}: q \in \delta(q_j, a) \right\}$.
	\item $Q_m = Q_{m+1} = \ldots$.
\end{enumerate}

Справді, очевидно, що кількість кроків скінчена, тому що послідовність $Q_i$ монотонна $\left(Q_0 \subseteq Q_1 \subseteq Q_2 \subseteq \ldots\right)$ та обмежена зверху: $Q_m \subseteq Q$. \medskip

Тоді $Q_m$ --- множина досяжних станів скінченого автомата, а $Q\setminus Q_m$ --- множина недосяжних станів. \medskip

Вилучимо з діаграми переходів скінченого автомата $M$ недосяжні вершини:
\begin{figure}[H]
	\centering
	\input{img/5}
\end{figure}

В новому автоматі функція $\delta$ визначається лише для досяжних станів. Побудований нами скінчений автомат з меншою кількістю станів буде еквівалентний початковому.

\subsubsection{Тупикові стани}

Стан $q$ скінченого автомата $M$ називається \textit{тупиковим}, якщо на діаграмі переходів скінченого автомата не існує шляху з $q$ в $F$. \medskip

\textbf{Алгоритм [пошуку тупикових станів].} Спочатку спробуємо знайти нетупикові стани. Якщо $S_m$ --- множина нетупикових станів, то $Q \setminus S_m$ --- множина тупикових станів. Побудуємо послідовність множин $S_0$, $S_1$, $S_2$, $\ldots$ таким чином, що:
\begin{enumerate}
	\item $S_0 = F$.
	\item $S_i = S_{i - 1} \cup \left\{ q \mid \exists a \in \Sigma: \delta(q, a) \cap S_{i - 1} \ne \varnothing \right\}$.
	\item $S_m = S_{m + 1} = \ldots$.
\end{enumerate}

Очевидно, що кількість кроків скінчена, тому що послідовність $S_i$ монотонна $\left(S_0 \subseteq S_1 \subseteq S_2 \subseteq \ldots\right)$ та обмежена зверху --- $S_m \subseteq Q$. \medskip

Тоді $S_m$ --- множина нетупикових станів скінченого автомата, а $Q \setminus S_m$ --- множина тупикових станів.  \medskip

Вилучимо з діаграми переходів скінченого автомата $M$ тупикові вершини:
\begin{figure}[H]
	\centering
	\input{img/6}
\end{figure}

В новому автоматі функція $\delta$ визначається лише для нетупикових станів.

\subsubsection{Еквівалентні стани}

Автомат, у котрого відсутні недосяжні та тупикові стани, піддається подальшій мінімізації шляхом ``склеювання'' еквівалентних станів. Продемонструємо це на конкретному прикладі:
\begin{figure}[H]
	\centering
	\input{img/7}
\end{figure}

Очевидно, що для наведеного вище скінченого автомата можна побудувати еквівалентний йому скінчений автомат з меншою кількістю станів:
\begin{figure}[H]
	\centering
	\input{img/8}
\end{figure}

Ми досягли бажаного нам результату шляхом ``склеювання'' двох станів $q_1 \equiv q_3$ та $q_2 \equiv q_4$. \medskip

Два стани $q_1$ та $q_2$ скінченого автомата $M$ називаються \textit{еквівалентними} (позначається $q_1 \equiv q_2$), якщо множини слів, які розпізнає автомат, починаючи з $q_1$ та $q_2$, співпадають. \medskip

Нехай $q_1$ та $q_2$ --- два різні стани скінченого автомата $M$, а $x \in \Sigma^\star$. Будемо говорити, що ланцюжок $x$ \textit{розрізняє} стани $q_1$ та $q_2$, якщо $(q_1,x) \models^\star (q_3, \varepsilon)$ та $(q_2,x) \models^\star (q_4, \varepsilon)$, причому рівно один зі станів $q_3$ і $q_4$ (не) належить множині заключних станів. \medskip

Стани $q_1$ та $q_2$ називаються \textit{$k$-нерозрізнені}, якщо не існує ланцюжка $x$ $(\left|x\right| \le k)$, що розрізняє стани $q_1$ та $q_2$. \medskip

Два стани $q_1$ та $q_2$ \textit{нерозрізнені}, якщо вони $k$-нерозрізнені для довільного $k$. \medskip

\textbf{Теорема.} \textit{Два стани $q_1$ та $q_2$ довільного скінченого автомата $M$ з $n$ станами нерозрізнені, якщо вони $(n - 2)$-нерозрізнені.} \medskip

\textbf{Доведення:} На першому кроці розіб'ємо множину станів скінченого автомата на дві підмножини: $F$ та $Q \setminus F$. На цій основі побудуємо відношення $\equiv^0$: $q_1 \equiv^0 q_2$, якщо обидва стани одночасно належать $F$ або $Q \setminus F$. \medskip

Побудуємо відношення $\equiv^k$: $q_1 \equiv^k q_2$, якщо $q_1 \equiv^{k - 1} q_2$ та $\delta(q_1,a) \equiv^{k - 1} \delta(q_2, a)$ для всіх $a \in \Sigma$. \medskip

Очевидно, кожна побудована множина містить не більше $(n-1)$ елементи. \medskip

Таким чином, можна отримати не більше $(n-2)$ уточнення відношення $\equiv^0$. \medskip

Відношення $\equiv^{n - 2}$ визначає класи еквівалентних станів автомата $M$.

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

\textbf{Алгоритм [побудови мінімального скінченого автомата].}
\begin{enumerate}
	\item Побудувати скінчений автомат без тупикових станів.
	\item Побудувати скінчений автомат без недосяжних станів.
	\item Знайти множини еквівалентних станів та побудувати найменший (мінімальний) автомат.
\end{enumerate}

\subsection{Контрольні запитання}

\begin{enumerate}
	\item Які автомати називаються еквівалентними? % ті які задають одну мову
	\item Який стан автомату називається недосяжним? % той у який немає шляху з $q_0$ на діаграмі переходів
	\item Опишіть алгоритм пошуку недосяжних станів і доведіть його збіжність. \smallskip
	
	Бонус: оцініть складність цього алгоритму за часом і пам'\-ят\-тю.
	\item Який стан автомату називається тупиковим? % той з якого немає шляху в $F$ на діаграмі переходів
	\item Опишіть алгоритм пошуку тупикових станів і доведіть його збіжність. \smallskip
	
	Бонус: оцініть складність цього алгоритму за часом і пам'\-ят\-тю.
	\item Які стани називаються еквівалентними? % для яких не існує розрізняючого слова
	\item Опишіть алгоритм пошуку еквівалентних станів і доведіть його збіжність. \smallskip
	
	Бонус: оцініть складність цього алгоритму за часом і пам'яттю.
	\item Опишіть алгоритм мінімізації детермінованого скінченного автомату. \smallskip
	
	Бонус: виведіть з попередніх оцінок складність цього алгоритму за часом і пам'яттю.
\end{enumerate}