Добавил реферат по теории перевода, первую презентацию по теории автоматов

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}