\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{fancyhdr}
\usepackage{caption}

\usepackage{listings,longtable,amsmath,amsfonts,graphicx,tikz,tabularx,pgf}
\usetikzlibrary{arrows,automata}

\captionsetup{labelsep=period}
\pagestyle{fancy}

\lstset{
    basicstyle=\footnotesize,
    breakatwhitespace=false,
    breaklines=true,
    extendedchars=true,
    keepspaces=true,
    keywordstyle=\bfseries,
    numbers=left,
    numbersep=3pt,
    numberstyle=\tiny,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    stepnumber=1,
    stringstyle=\emph,
    tabsize=2
}

\usepackage[left=1.5cm,right=1.5cm,top=2cm,bottom=1.5cm,bindingoffset=0cm]{geometry}

\captionsetup{labelsep=period}
\pagestyle{fancy}

\renewcommand{\headrulewidth}{0pt}
\fancyfoot[L] {\thepage\bf}
\fancyfoot[C] {}

\graphicspath{ {img/} }

\begin{document}
    \begin{titlepage}
        \begin{center}
            \large
            САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ \\


            \vspace{3cm}


            Кафедра вычислительной техники
            \vspace{4cm}

            \textsc{ \textbf{Отчёт по лабораторной работе  № 1} \\
            по дисциплине <<Теория автоматов>>\\}
            Вариант №4\\[8mm]

            \bigskip
        \end{center}
        \vspace{3cm}

        \hfill\begin{flushright}
             Студент: \\ Куклина М. \\ P3301 \\ 
             \vfill
             Преподаватель:\\ Ожиганов А.А.
        \end{flushright}
        \vfill
        \vfill
        \vfill
        \vfill
        \vfill
        \begin{center}
            Санкт-Петербург \\2017 г.
        \end{center}
    \end{titlepage}
\newpage

\section*{Цель и постановка задачи}
    \subsection*{Цель}
        Цель -- практическое освоение методов взаимного преобразования автоматных
        моделей Милли и Мура. Проверка абстрактных автоматов Мили и Мура на эквивалентность.
    \subsection*{Постановка задачи}
        Исходный абстрактный автомат задан графическим способом. При переходе
        от автомата Мура к Мили и наоборот учесть, что их входные и выходные алфавиты
        должны совпадать.

\section*{Графы исходного и преобразованного автоматов}
    \subsection*{Исходный граф автомата Мили}
        \begin{tikzpicture}[->,>=stealth',shorten >=2pt,auto,node distance=4cm, semithick] 
            \tikzstyle{every state}=[draw=black,text=black,fill=white,thick,scale=1]

            \node[state] (A1)                   {$a_1$};
            \node[state] (B2)[below left of=A1] {$a_2$};
            \node[state] (C5)[below of=B2]      {$a_5$};
            \node[state] (E3)[below right of=A1]{$a_3$};
            \node[state] (D4)[below of=E3]      {$a_4$};

            \path (A1) edge[loop above] node {$z_3/w_2$} (A1)
                  (A1) edge[bend left]  node {$z_1/w_2$} (E3)
                  (A1) edge             node[pos=0.35] {$z_2/w_2$} (C5)
                  (B2) edge[bend left]  node {$z_1/w_1$} (A1)
                  (B2) edge[bend left]  node[pos=0.7] {$z_2/w_2$} (E3)
                  (B2) edge             node[pos=0.7,left] {$z_3/w_1$} (D4)
                  (E3) edge             node[pos=0.9,right] {$z_1/w_1$} (C5)
                  (D4) edge[bend right] node[pos=0.7,right] {$z_1/w_1$} (E3)
                  (D4) edge[loop below] node {$z_2/w_2$} (D4)
                  (C5) edge[loop below] node {$z_1/w_1$} (C5)
                  (C5) edge[bend left]  node {$z_2/w_1$} (B2);
        \end{tikzpicture}
    \subsection*{Преобразованный автомат Мура}    
        \begin{tikzpicture}[->,>=stealth',shorten >=2pt,auto,node distance=3cm, semithick] 
            \tikzstyle{every state}=[draw=black,text=black,fill=white,thick,scale=1]
            \foreach \s in {1,2,6,8,9} {
                \node[state] (b\s) at ({360/9 *(\s+1)}:0.25\textwidth) {$b_\s$};
            }
            \node[state] (b3) at ({360/9 *(4+1)}:0.25\textwidth) {$b_3$};
            \node[state] (b4) at ({360/9 *(7+1)}:0.25\textwidth) {$b_4$};
            \node[state] (b7) at ({360/9 *(5+1)}:0.25\textwidth) {$b_7$};
            \node[state] (b5) at ({360/9 *(3+1)}:0.25\textwidth) {$b_5$};

            \path (b1) edge             node[pos=0.1,above] {$z_1$} (b5)
                  (b1) edge[bend left]  node[pos=0.2] {$z_2$} (b9)
                  (b1) edge[bend right] node[pos=0.2,above] {$z_3$} (b2)
                  (b2) edge             node[pos=0.15] {$z_1$} (b5)
                  (b2) edge             node[pos=0.1] {$z_2$} (b9)
                  (b2) edge[loop left]  node[pos=0.2] {$z_3$} (b2)
                  (b3) edge             node[pos=0.1] {$z_1$} (b1)
                  (b3) edge[bend left]  node[pos=0.2] {$z_2$} (b5)
                  (b3) edge             node[pos=0.1] {$z_3$} (b6)
                  (b4) edge[bend right] node[pos=0.2] {$z_3$} (b8)
                  (b5) edge             node[pos=0.1] {$z_3$} (b8)
                  (b6) edge             node[pos=0.2] {$z_1$} (b4)
                  (b6) edge[bend left]  node[pos=0.2] {$z_2$} (b7)
                  (b7) edge             node[pos=0.1] {$z_1$} (b4)
                  (b7) edge[loop left]  node[pos=0.2] {$z_2$} (b7)
                  (b8) edge[loop right] node[pos=0.2] {$z_1$} (b8)
                  (b8) edge             node[pos=0.1] {$z_2$} (b3)
                  (b9) edge[bend left]  node[pos=0.2] {$z_1$} (b8)
                  (b9) edge             node[pos=0.1] {$z_2$} (b3)
            ;
        \end{tikzpicture}
\section*{Этапы преобразования автоматов}
        $S_b = (A_b, Z_b, W_b, {\delta}_b, {\lambda}_b, a_{1b})$
        Где \\
        $A_b$ -- множество состояний автомата Мили; \\
        $Z_b$ -- входной алфавит; \\
        $W_b$ -- выходной алфавит; \\
        ${\delta}_b$ -- функция переходов автомата; \\
        ${\lambda}_b$ -- функция выходов автомата; \\
        $a_{1b}$ -- начальное состояние.

        В эквивалентном автомате Мура $Z_b = Z_a$, $W_b = W_a$.

        Построим таблицу автомата Мили.

        \begin{table}[!h]
            \begin{tabular} {|c|c|c|c|c|c|}
                \hline
                $\delta$ & $a_1$ & $a_2$ & $a_3$ & $a_4$ & $a_5$ \\ \hline
                $z_1$  & $a_3$ & $a_1$ & $a_5$ & $a_3$ & $a_5$ \\ \hline
                $z_2$  & $a_5$ & $a_3$ &       & $a_4$ & $a_2$ \\ \hline
                $z_3$  & $a_1$ & $a_4$ &       &       &       \\ \hline
            \end{tabular}
            \caption{Таблица переходов автомата Мили}
        \end{table}
        \begin{table}[!h]
            \begin{tabular} {|c|c|c|c|c|c|}
                \hline
                $\lambda$ & $a_1$ & $a_2$ & $a_3$ & $a_4$ & $a_5$ \\ \hline
                $z_1$  & $w_2$ & $w_1$ & $w_1$ & $w_1$ & $w_1$ \\ \hline
                $z_2$  & $w_2$ & $w_2$ &       & $w_2$ & $w_1$ \\ \hline
                $z_3$  & $w_2$ & $w_1$ &       &       &       \\ \hline
            \end{tabular}
            \caption{Таблица выходов автомата Мили}
        \end{table}
    
        По таблице определим пары $(a_s, w_g)$, определяющие эквивалентные состояния в автомате Мура. \\
        $A_1 = \{ (a_1, w_1), (a_1, w_2) \} = \{ b_1, b_2 \}$ \\
        $A_2 = \{ (a_2, w_1) \} = \{ b_3 \}$ \\
        $A_3 = \{ (a_3, w_1), (a_3, w_2) \} = \{ b_4, b_5 \}$ \\
        $A_4 = \{ (a_4, w_1), (a_4, w_2) \} = \{ b_6, b_7 \}$ \\
        $A_5 = \{ (a_5, w_1), (a_5, w_2) \} = \{ b_8, b_9 \}$


        Составим таблицу переходов для автомата Мура. Для этого смотрим на состояние в исходной паре,
        ищем следующее множество состояний для автомата Мура из функции $\delta(a_s, z_f)$ и определяем
        состояние для автомата Мура из функции $\lambda(a_s, z_f)$ для автомата Мили. 

        \begin{table}[!h]
            \begin{tabular} {|c|c|c|c|c|c|c|c|c|c|}
                \hline
                $\delta$  & $b_1$ & $b_2$ & $b_3$ & $b_4$ & $b_5$ & $b_6$ & $b_7$ & $b_8$ & $b_9$ \\ \hline
                $\lambda$ & $w_1$ & $w_2$ & $w_1$ & $w_1$ & $w_2$ & $w_1$ & $w_2$ & $w_1$ & $w_2$ \\ \hline
                $z_1$     & $b_5$ & $b_5$ & $b_1$ & $b_8$ & $b_8$ & $b_4$ & $b_4$ & $b_8$ & $b_8$ \\ \hline
                $z_2$     & $b_9$ & $b_9$ & $b_5$ & x     & x     & $b_7$ & $b_7$ & $b_3$ & $b_3$ \\ \hline
                $z_3$     & $b_2$ & $b_2$ & $b_6$ & x     & x     & x     & x     & x     & x     \\ \hline
            \end{tabular}
            \caption{Таблица выходов автомата Мили}
        \end{table}

\section*{Реакции автоматов на входное слово}
        \subsection*{Входное слово минимальной длины}
        Путём перебора находим слово миинимальной длины: \\
            $z_3 z_1 z_1 z_1 z_2 z_1 z_2 z_2 z_2 z_1 z_2 z_3 z_2 z_1$
        \subsection*{Реакция автоматов}
        \begin{table}[!h]
            \begin{tabular}{|c|c|c|c|c|c|c|c|}
                \hline
                Состояние & $(a_1, z_3)$& $(a_1, z_1)$ & $(a_3, z_1)$ & $(a_5, z_1)$& $(a_5, z_2)$ & $(a_2, z_1)$ & $(a_1, z_2)$\\ \hline
                Слово     & $w_2$       & $w_2$        & $w_1$ 		  & $w_1$		& $w_1$		   & $w_1$		  & $w_2$ 		\\ \hline
                Состояние & $(a_5,z_2)$ & $(a_2,z_2)$ & $(a_3,z_1)$ & $(a_5,z_2)$ & $(a_2,z_3)$ & $(a_4,z_2)$ & $(a_4,z_1)$ \\ \hline
                Слово     & $(w_1)$     & $w_2$       & $w_1$       & $w_1$       & $w_1$       & $w_2$       & $w_1$		\\ \hline
            \end{tabular}
            \caption{Реакция автомата Мили}
        \end{table}
        \begin{table}[!h]
            \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
                \hline
                Состояние & $(b_1, z_3)$& $(b_2, z_1)$ & $(b_5, z_1)$ & $(b_8, z_1)$& $(b_8, z_2)$ & $(b_3, z_1)$ & $(b_1, z_2)$&		\\ \hline
                Слово     & x           & $w_2$        & $w_2$ 		  & $w_1$		& $w_1$		   & $w_1$		  & $w_1$ 		&		\\ \hline
                Состояние & $(b_9,z_2)$ & $(b_3,z_2)$  & $(b_5,z_1)$  & $(b_8,z_2)$ & $(b_3,z_3)$  & $(b_6,z_2)$  & $(b_7,z_1)$ & $b_4$ \\ \hline
                Слово     & $(w_2)$     & $w_1$        & $w_2$        & $w_1$       & $w_1$        & $w_1$        & $w_2$		& $w_1$ \\ \hline
            \end{tabular}
            \caption{Реакция автомата Мура}
        \end{table}

		Результаты: \\
        Реакция автомата Мили: $w_2 w_2 w_1 w_1 w_1 w_1 w_2 w_1 w_2 w_1 w_1 w_1 w_2 w_1$. \\
        Реакция автомата Мура: $w_2 w_2 w_1 w_1 w_1 w_1 w_2 w_1 w_2 w_1 w_1 w_1 w_2 w_1$. \\
		Реакции двух автоматов совпадают, следовательно, два постренных автомата эквивалентны.


\section*{Вывод}
    В ходе выполнения лабораторной работы были изучены автоматы Мили и Мура и способы преобразования. В ходе работы
    использовался табличный способ преобразования автоматов. В результате преобразования автомата Мили
    в эквивалентный автомат Мура выяснилось, что автомат Мура обладает большим количеством состояний, так что в данном
    случае использование автомата Мили выглядит более целесообразным.  
\end{document}
