path: root/Теория автоматов/2_6-2_7/presentation.tex

\documentclass{beamer}

\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{multirow}
\graphicspath{ {./images/} }

\usetheme{Madrid}

\title[Разложение автоматов]{Классификация состояний и подавтоматов. Разложение
автоматов и расщепляемый автомат}
\author[А.~Ю.~Гущин]{Андрей~Гущин}
\institute[СГУ]{Саратовский Государственный Университет}
\date{16 февраля 2023 г.}


\AtBeginSection[]{
  \begin{frame}
  \vfill
  \centering
  \begin{beamercolorbox}[sep=8pt,center,shadow=true,rounded=true]{title}
    \usebeamerfont{title}\insertsectionhead\par%
  \end{beamercolorbox}
  \vfill
  \end{frame}
}

\begin{document}

\maketitle


\section{Классификация состояний и подавтоматов}

\begin{frame}{Классификация дуг}
  \begin{minipage}[t]{0.48\linewidth}
    Дуга относительно данного состояния $\sigma_i$ может быть
    \begin{itemize}
      \item
        \emph{заходящей} в $\sigma_i$, если она направлена к $\sigma_i$ из
        другого состояния,
      \item
        \emph{исходящей} из $\sigma_i$, если она направлена от $\sigma_i$ к
        другому состоянию,
      \item 
        \emph{петлёй}, если она выходит из $\sigma_i$ и входит в $\sigma_i$.
    \end{itemize}
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.48\linewidth}
    \vspace{25pt}
    \begin{figure}[H]
      \includegraphics[width=\textwidth]{edges}
    \end{figure}
  \end{minipage}
\end{frame}

\begin{frame}{Классификация состояний}
  Состояние, в котором отсутствуют заходящие и (или) исходящие дуги, может быть
  одним из следующих типов:
  \begin{itemize}
    \item
      \emph{преходящее состояние} --- состояние, которое не имеет заходящих
      дуг, но имеет, по крайней мере, одну исходящую дугу;
    \item
      \emph{тупиковое состояние} --- состояние, которое не содержит исходящих
      дуг, но содержит, по крайней мере, одну заходящую дугу;
    \item
      \emph{изолированное состояние} --- состояние, которое не содержит ни
      заходящих, ни исходящих дуг.
  \end{itemize}
\end{frame}

\begin{frame}{Подавтомат}
  \begin{minipage}[t]{0.48\linewidth}
    Подавтомат --- любое подмножество множества состояний автомата. Рассматривая
    каждый подавтомат как одно <<сверхсостояние>>, преходящий, тупиковый или
    изолированный подавтоматы могут быть определены точно так же, как преходящее,
    тупиковое и изолированное состояние с заменой слова <<состояние>> на
    <<подавтомат>>.
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.48\linewidth}
    \vspace{10pt}
    \begin{figure}[H]
      \includegraphics[width=\textwidth]{subauto}
    \end{figure}
  \end{minipage}
\end{frame}

% \begin{frame}{}
%   Пусть $G_k(S_i)$ обозначает множество всех состояний автомата $M$, в
%   которые можно попасть из любых состояний множества $S_i = \{\sigma_{i_1},
%   \sigma_{i_2}, \dots, \sigma_{i_r}\}$ при подаче на вход последовательности
%   длины $k$ или меньше. В частности, $G_0(S_i) = S_i$. Множество $G_1(S_i)$
%   есть объединение $S_i$ и всех состояний, указанных в строках $\sigma_{i_1},
%   \sigma_{i_2}, \dots, \sigma_{i_r}$, подтаблицы $s_{v + 1}$ таблицы переходов
%   $M$. С другой стороны, $G_1(S_i)$ может быть определено путем просмотра графа
%   переходов автомата $M$. Если задано $G_{k - 1}(S_i)$, $k \geq 1$, то
%   $G_k(S_i)$ может быть определено из соотношения
%   \begin{equation*}
%     G_k(S_i) = G_1(G_{k - 1}(S_i))
%   \end{equation*}

%   Если $G_k(S_i) = G_{k - 1}(S_i)$, то $G_{k + u}(S_i) = G_{k - 1}(S_i)$ для
%   всех неотрицательных целых $u$; следовательно, $G_k(S_i)$ составляет множество
%   всех состояний, в которые можно попасть из $S_i$ если на вход подавать
%   последовательности любой длины. Определение этого множества, обозначаемого
%   просто $G(S_i)$ может быть теперь описано при помощи следующего алгоритма.
% \end{frame}

\begin{frame}{}
  Пусть $G_k(S_i)$ обозначает множество всех состояний автомата $M$, в
  которые можно попасть из любых состояний множества $S_i = \{\sigma_{i_1},
  \sigma_{i_2}, \dots, \sigma_{i_r}\}$ при подаче на вход последовательности
  длины $k$ или меньше. В частности, $G_0(S_i) = S_i$. Если задано $G_{k -
  1}(S_i)$, $k \geq 1$, то $G_k(S_i)$ может быть определено из соотношения
  \begin{equation*}
    G_k(S_i) = G_1(G_{k - 1}(S_i))
  \end{equation*}

  Если $G_k(S_i) = G_{k - 1}(S_i)$, то $G_{k + u}(S_i) = G_{k - 1}(S_i)
  \; (\forall u \geq 1)$; следовательно, $G_k(S_i)$ составляет множество
  всех состояний, в которые можно попасть из $S_i$ если на вход подавать
  последовательности любой длины. Такое множество можно обозначить просто
  $G(S_i)$.
\end{frame}

\begin{frame}{}
  \begin{block}{Алгоритм}
    Дано $S_i$; найти $G(S_i)$.
    \begin{enumerate}
      \item Пусть $G_0(S_i) = S_i$. Полагаем $k = 1$.
      \item Определяем $G_k(S_i) = G_1(G_{k - 1}(S_i))$
      \item
        \begin{itemize}
          \item
            Если $G_k(S_i) \neq G_{k - 1}(S_i)$, увеличиваем $k$ на 1 и
            возвращаемся к (2).
          \item Если $G_k(S_i) = G_{k - 1}(S_i)$, то $G_k(S_i) = G(S_i)$.
        \end{itemize}
    \end{enumerate}
  \end{block}
  
\end{frame}
\begin{frame}
  Если $G_k(S_i) \neq G_{k - 1}(S_i)$, то $G_k(S_i)$ должно содержать, по
  крайней мере, на один элемент больше, чем $G_{k - 1}(S_i)$. Так как
  мощность $G_k(S_i)$ не может превышать общее число $n$ состояний автомата
  $M$, то $G_k(S_i)$ должно равняться $G_{k - 1}(S_i)$ для $k \leq n - r + 1$,
  где $r$ --- мощность множества $S_i$. Следовательно,
  \begin{equation}
    G(S_i) = G_{n - r}(S_i)
  \end{equation}

  Это значит, что алгоритм требует не более чем $n - r$ итераций пункта 2.
\end{frame}

\begin{frame}{Достижимость в автоматах}
  \begin{block}{Определение}
    Если $S_i$, состоит из одного состояния $\sigma_i$, то $G(\sigma_i)$
    называется $\sigma_i$-достижимым множеством и представляет собой множество
    всех состояний, в которые можно попасть из состояния $\sigma_i$.
  \end{block}

  \begin{block}{Теорема}
    Пусть $\sigma_i$ и $\sigma_j$ --- два состояния в автомате с $n$
    состояниями. Если $\sigma_j$ вообще достижимо из $\sigma_i$, то оно
    достижимо при подаче входной последовательности длиной не более $n - 1$.
  \end{block}
\end{frame}


\section{Разложение автоматов и расщепляемый автомат}

\begin{frame}
  Пусть $H_k(S_i)$ обозначает множество всех состояний автомата $M$, соединённых
  с состояниями $S_i = \{\sigma_{i_1}, \sigma_{i_2}, \dots, \sigma_{i_r}\}$
  посредством $k$ или меньшего числа дуг, причём направление дуг несущественно.
  В частности, $H_0(S_i) = S_i$. $Н(S_i)$ составляет множество всех состояний,
  связанных с $S_i$ цепью рёбер любой длины.
\end{frame}

\begin{frame}{Разложимость автомата}
  \begin{minipage}[t]{0.48\linewidth}
    Автомат или подавтомат, который содержит два или большее число изолированных
    подавтоматов, будем называть разложимым. Если $Н(\sigma_i) \neq S$, то
    $H(\sigma_i)$ составляет неразложимый изолированный подавтомат автомата $M$.
    Если $Н(\sigma_i) = S$, то можно заключить, что автомат $M$ неразложим.

    Максимальное разложение автомата --- разложение автомата на максимально
    возможное число изолированных подавтоматов.
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.48\linewidth}
    \vspace{20pt}
    \begin{figure}[H]
      \includegraphics[width=\textwidth]{composite}
    \end{figure}
  \end{minipage}
\end{frame}

\begin{frame}{Расщепляемость автомата}
  \begin{minipage}[t]{0.48\linewidth}
    Два или большее число автоматов называются сравнимыми, если они имеют
    одинаковые входные алфавиты. Пусть $M_1, M_2, \dots, M_N$ --- сравнимые
    автоматы, представляющие $N$ различных систем, и пусть $М$ --- автомат,
    который состоит из изолированных подавтоматов $M_i, i = \overline{1, N}$. $M$
    называется расщепляемым автоматом автоматов $M_i$ и обозначается $\Delta(M_1,
    M_2, \dots, M_N)$.
  \end{minipage}
  \hfill
  \begin{minipage}[t]{0.48\linewidth}
    \vspace{-10pt}
    \begin{figure}[H]
      \includegraphics[width=\textwidth]{splitted}
    \end{figure}
  \end{minipage}
\end{frame}


\end{document}