diff options
Diffstat (limited to 'Теория автоматов/2_6-2_7/presentation.tex')
| -rw-r--r-- | Теория автоматов/2_6-2_7/presentation.tex | 225 |
1 files changed, 225 insertions, 0 deletions
diff --git a/Теория автоматов/2_6-2_7/presentation.tex b/Теория автоматов/2_6-2_7/presentation.tex new file mode 100644 index 0000000..12f84fd --- /dev/null +++ b/Теория автоматов/2_6-2_7/presentation.tex @@ -0,0 +1,225 @@ +\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} |