\documentclass[12pt, a4paper] {ncc}
\usepackage[utf8] {inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english, russian] {babel}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{listings,a4wide,longtable,amsmath,amsfonts,graphicx,tikz}
\usepackage{pgfplots}
\usepackage{indentfirst}
\usepackage{bytefield}

\usetikzlibrary{arrows,shapes,snakes,automata,backgrounds,petri}
\tikzstyle{state}=[circle,thick,draw=blue!75,fill=blue!20,minimum size=6mm]
\tikzstyle{fstate}=[circle,thick,draw=blue!75,fill=green!20,minimum size=6mm]
\tikzstyle{trans}=[rectangle,thick,draw=red!30,fill=lightgray!10]

\begin{document}
\frenchspacing
\pagestyle{empty}
% ============================ ТИТУЛЬНЫЙ ЛИСТ ================================
\begin{center}
     Национальный исследовательский университет информационных технологий,
                              механики и оптики\\
                 Кафедра информатики и прикладной математики\\
                                Теория автоматов
\end{center}
\vspace{\stretch{2}}
\begin{center}
                               Домашняя работа №3\\
                        {\sl Вариант 11, на <<отлично>>}
\end{center}
\vspace{\stretch{3}}
\begin{flushright}
                                          Работу выполнил студент группы P3315\\
                                                         {\it Халанский Дмитрий}
\end{flushright}
\vspace{\stretch{4}}
\begin{center}
                                      2016
\end{center}
\newpage
% ======================== КОНЕЦ ТИТУЛЬНОГО ЛИСТА ============================

% ================================ ОТЧЁТ =====================================
\setcounter{figure}{0}

\section{Цели работы}

\begin{itemize}
        \item Представить регулярное выражение в виде недетерминированного
                конечного автомата;
        \item Преобразовать его в детерминированный конечный автомат;
        \item Минимизировать полученный конечный автомат;
        \item Привести примеры последовательностей, принимаемых и отвергаемых
                результирующим конечным автоматом.
\end{itemize}

\section{Исходные данные}

Регулярное выражение: $\left((ab)*|(a|\varepsilon)\right)\left((ba?)|(ac)?
\right)*$

\section{Ход работы}

\subsection{Построение НКА}

\begin{enumerate}
        \item Исходные данные:\\
\begin{tikzpicture}[->,semithick,node distance=8cm]
\node[ state] (a1)               {$a_1$};
\node[fstate] (a2) [right of=a1] {$a_2$};

\path
        (a1) edge node[trans] {\scriptsize
        $\left((ab)*|(a|\varepsilon)\right)\left((ba?)|(ac)?\right)*$} (a2);
\end{tikzpicture}

        \item Правило конкатенации:\\
\begin{tikzpicture}[->,semithick,node distance=4cm]
\node[ state] (a1)               {$a_1$};
\node[ state] (a3) [right of=a1] {$a_3$};
\node[fstate] (a2) [right of=a3] {$a_2$};

\path
        (a1) edge node[trans] {\scriptsize $(ab)*|(a|\varepsilon)$} (a3)
        (a3) edge node[trans] {\scriptsize $\left((ba?)|(ac)?\right)*$} (a2)
;
\end{tikzpicture}

        \item Правило объединения:\\
\begin{tikzpicture}[->,semithick,node distance=4cm]
\node[ state] (a1)               {$a_1$};
\node[ state] (a3) [right of=a1] {$a_3$};
\node[fstate] (a2) [right of=a3] {$a_2$};

\path
        (a1) edge[bend left]  node[trans] {\scriptsize $(ab)*$} (a3)
        (a1) edge[bend right] node[trans] {\scriptsize $a$} (a3)
        (a1) edge             node[trans] {\scriptsize $\varepsilon$} (a3)
        (a3) edge node[trans] {\scriptsize $\left((ba?)|(ac)?\right)*$} (a2)
;
\end{tikzpicture}

        \item Правило преобразования замыкания:\\
\begin{tikzpicture}[->,semithick,node distance=2cm]
\node[ state] (a1)               {$a_1$};
\node[ state] (a3) [right of=a1] {$a_3$};
\node[ state] (a5) [right of=a3] {$a_5$};
\node[fstate] (a2) [right of=a5] {$a_2$};
\node[ state] (a4) [above of=a1] {$a_4$};

\path
        (a1) edge[bend right] node[trans] {\scriptsize $a$} (a3)
        (a1) edge             node[trans] {\scriptsize $\varepsilon$} (a3)
        (a1) edge[bend left]  node[trans] {\scriptsize $\varepsilon$} (a4)
        (a4) edge[bend left]  node[trans] {\scriptsize $\varepsilon$} (a3)
        (a3) edge node[trans] {\scriptsize $\varepsilon$} (a5)
        (a5) edge node[trans] {\scriptsize $\varepsilon$} (a2)
        (a4) edge [looseness=4] node[loop below,trans,above]
                                          {\scriptsize $ab$} (a4)
        (a5) edge [looseness=4] node[loop below,trans,above] {\scriptsize
                $(ba?)|(ac)?$} (a5)
;
\end{tikzpicture}

        \item Дальнейшие преобразования:\\
\begin{tikzpicture}[->,semithick,node distance=2cm]
\node[ state] (a1)               {$a_1$};
\node[ state] (a3) [right of=a1] {$a_3$};
\node[ state] (a5) [right of=a3] {$a_5$};
\node[fstate] (a2) [right of=a5] {$a_2$};
\node[ state] (a4) [above of=a1] {$a_4$};
\node[ state] (a6) [above right of=a4] {$a_6$};
\node[ state] (a7) [above left  of=a5] {$a_7$};
\node[ state] (a8) [right of=a7] {$a_8$};
\node[ state] (a9) [above right of=a7] {$a_9$};
\node[ state] (a10)[right of=a9] {$a_{10}$};

\path
        (a1) edge[bend right] node[trans] {\scriptsize $a$} (a3)
        (a1) edge             node[trans] {\scriptsize $\varepsilon$} (a3)
        (a1) edge[bend left]  node[trans] {\scriptsize $\varepsilon$} (a4)
        (a4) edge[bend left]  node[trans] {\scriptsize $\varepsilon$} (a3)
        (a3) edge node[trans] {\scriptsize $\varepsilon$} (a5)
        (a5) edge node[trans] {\scriptsize $\varepsilon$} (a2)
        (a4) edge[bend left]  node[trans] {\scriptsize $a$} (a6)
        (a6) edge[bend left]  node[trans] {\scriptsize $b$} (a4)
        (a5) edge node [trans] {\scriptsize $\varepsilon$} (a7)
        (a7) edge node [trans] {\scriptsize $b$} (a9)
        (a7) edge node [trans] {\scriptsize $\varepsilon$} (a10)
        (a7) edge node [trans] {\scriptsize $a$} (a8)
        (a8) edge node [trans] {\scriptsize $c$} (a10)
        (a9) edge[bend left]  node [trans] {\scriptsize $a$} (a10)
        (a9) edge node [trans] {\scriptsize $\varepsilon$} (a10)
        (a10) edge[bend left] node [trans] {\scriptsize $\varepsilon$} (a5)
;
\end{tikzpicture}

\item Избавление от $\varepsilon$-переходов
\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline
\bf Состояние & $a$ & $b$ & $c$ \\
\hline
$b_1 = \Xi(a_1) = \left\{a_1, a_2, a_3, a_4, a_5, a_7, a_{10}\right\}$ &
        $\left\{\Xi (a_3), \Xi (a_6), \Xi (a_8)\right\}$ &
        $\left\{\Xi (a_9)\right\}$ &
        $\emptyset$ \\
\color{red} $\Xi(a_2) = \left\{a_2\right\}$ &
        $\emptyset$ &
        $\emptyset$ &
        $\emptyset$ \\
$b_2 = \Xi(a_3) = \left\{a_2, a_3, a_5, a_7, a_{10}\right\}$ &
        $\left\{\Xi(a_8)\right\}$ &
        $\left\{\Xi(a_9)\right\}$ &
        $\emptyset$ \\
$b_3 = \Xi(a_4) = \left\{a_4, a_3, a_2, a_5, a_7, a_{10}\right\}$ &
        $\left\{\Xi (a_6), \Xi (a_8)\right\}$ &
        $\left\{\Xi (a_9)\right\}$ &
        $\emptyset$ \\
\color{red} $\Xi(a_5) = \left\{a_2, a_5, a_7, a_{10}\right\}$ &
        $\left\{\Xi (a_8)\right\}$ &
        $\left\{\Xi (a_9)\right\}$ &
        $\emptyset$ \\
$b_4 = \Xi(a_6) = \left\{a_6\right\}$ &
        $\emptyset$ &
        $\left\{\Xi (a_4)\right\}$ &
        $\emptyset$ \\
\color{red} $\Xi(a_7) = \left\{a_2, a_5, a_7, a_{10}\right\}$ &
        $\left\{\Xi (a_8)\right\}$ &
        $\left\{\Xi (a_9)\right\}$ &
        $\emptyset$ \\
$b_5 = \Xi(a_8) = \left\{a_8\right\}$ &
        $\emptyset$ &
        $\emptyset$ &
        $\left\{\Xi (a_{10})\right\}$ \\
$b_6 = \Xi(a_9) = \left\{a_2, a_5, a_7, a_9, a_{10}\right\}$ &
        $\left\{\Xi (a_8), \Xi (a_{10})\right\}$ &
        $\left\{\Xi (a_9)\right\}$ &
        $\emptyset$ \\
$b_7 = \Xi(a_{10}) = \left\{a_2, a_5, a_7, a_9, a_{10}\right\}$ &
        $\left\{\Xi (a_8)\right\}$ &
        $\left\{\Xi (a_9)\right\}$ &
        $\emptyset$ \\
\hline
\end{tabular}
\end{center}

\begin{tikzpicture}[->,semithick,node distance=3cm]
\node[fstate] (b1)               {$b_1$};
\node[ state] (b4) [right of=b1] {$b_4$};
\node[fstate] (b2) [below of=b4] {$b_2$};
\node[ state] (b3) [right of=b4] {$b_3$};
\node[ state] (b5) [right of=b3] {$b_5$};
\node[fstate] (b6) [below of=b5] {$b_6$};
\node[fstate] (b7) [right of=b5] {$b_7$};

\path
        (b1) edge             node[trans] {\scriptsize $a$} (b2)
        (b1) edge             node[trans] {\scriptsize $a$} (b4)
        (b1) edge[bend left]  node[trans] {\scriptsize $a$} (b5)
        (b1) edge             node[trans] {\scriptsize $b$} (b6)
        (b2) edge             node[trans] {\scriptsize $a$} (b5)
        (b2) edge             node[trans] {\scriptsize $b$} (b6)
        (b3) edge             node[trans] {\scriptsize $a$} (b5)
        (b3) edge             node[trans] {\scriptsize $b$} (b6)
        (b3) edge[bend left]  node[trans] {\scriptsize $a$} (b4)
        (b4) edge[bend left]  node[trans] {\scriptsize $b$} (b3)
        (b5) edge[bend left]  node[trans] {\scriptsize $c$} (b7)
        (b6) edge             node[trans] {\scriptsize $a$} (b5)
        (b6) edge[bend right] node[trans] {\scriptsize $a$} (b7)
        (b7) edge             node[trans] {\scriptsize $a$} (b5)
        (b7) edge             node[trans] {\scriptsize $b$} (b6)
        (b6) edge [out=300, in=0, looseness=4] node[loop,trans]
                {\scriptsize $b$} (b6)
;

\end{tikzpicture}

\end{enumerate}

\subsection{Получение ДКА}

\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline
\bf Состояние & $a$ & $b$ & $c$ \\
\hline
        $p_0 = b_1$ &
                $p_1$ &
                $p_2$ &
                $\emptyset$ \\
        $p_1 = \left\{b_2, b_4, b_5\right\}$ &
                $p_3$ &
                $p_4$ &
                $\emptyset$ \\
        $p_2 = \left\{b_6\right\}$ &
                $p_5$ &
                $p_2$ &
                $\emptyset$ \\
        $p_3 = \left\{b_5\right\}$ &
                $\emptyset$ &
                $\emptyset$ &
                $p_6$ \\
        $p_4 = \left\{b_3, b_6\right\}$ &
                $p_7$ &
                $p_2$ &
                $\emptyset$ \\
        $p_5 = \left\{b_5, b_7\right\}$ &
                $p_3$ &
                $p_2$ &
                $p_6$ \\
        $p_6 = \left\{b_7\right\}$ &
                $p_3$ &
                $p_2$ &
                $\emptyset$ \\
        $p_7 = \left\{b_4, b_5, b_7\right\}$ &
                $p_3$ &
                $p_4$ &
                $p_6$ \\
\hline
\end{tabular}
\end{center}

\begin{tikzpicture}[->,semithick,node distance=3cm]
        \node[state] (p0)                     {$p_0$};
        \node[state] (p1) [above right of=p0] {$p_1$};
        \node[state] (p2) [below right of=p0] {$p_2$};
        \node[state] (p4) [      right of=p0] {$p_4$};
        \node[state] (p7) [      right of=p4] {$p_7$};
        \node[state] (p3) [      right of=p1] {$p_3$};
        \node[state] (p6) [      right of=p7] {$p_6$};
        \node[state] (p5) [      right of=p6] {$p_5$};

        \path
        (p0) edge node[trans] {\scriptsize $a$} (p1)
        (p0) edge node[trans] {\scriptsize $b$} (p2)
        (p1) edge node[trans] {\scriptsize $a$} (p3)
        (p1) edge node[trans] {\scriptsize $b$} (p4)
        (p2) edge node[trans] {\scriptsize $a$} (p5)
        (p2) edge [out=180, in=240, looseness=4] node[loop,trans]
                {\scriptsize $b$} (p2)
        (p3) edge[bend left]  node[trans] {\scriptsize $c$} (p6)
        (p4) edge[bend left]  node[trans] {\scriptsize $a$} (p7)
        (p4) edge             node[trans] {\scriptsize $b$} (p2)
        (p5) edge[bend right] node[trans] {\scriptsize $a$} (p3)
        (p5) edge[bend left]  node[trans] {\scriptsize $b$} (p2)
        (p5) edge             node[trans] {\scriptsize $c$} (p6)
        (p6) edge             node[trans] {\scriptsize $a$} (p3)
        (p6) edge             node[trans] {\scriptsize $b$} (p2)
        (p7) edge             node[trans] {\scriptsize $a$} (p3)
        (p7) edge             node[trans] {\scriptsize $b$} (p4)
        (p7) edge             node[trans] {\scriptsize $c$} (p6)
        ;

;

\end{tikzpicture}

Данная форма является минимальной, так как не существует повторений в таблице
состояний.

\subsection{Проверка автомата}

% ((ab)*|a)?(ba?|ac)*
\begin{tabular}{|c|c|c|}
        \hline
        \bf Строка & \bf Корректная? & \bf Автомат принял? \\
        \hline
        \tt abcabc  & Нет & Нет \\
        \tt aaabc   & Нет & Нет \\
        \tt abacb   & Да  & Да  \\
        \tt abbac   & Да  & Да  \\
        \tt abbacac & Да  & Да  \\
        \hline
\end{tabular}

\end{document}
