Добавил лекции и домашку по автоматам

1 files changed, 286 insertions, 0 deletions

diff --git a/Теория автоматов/fsm-hw/fsm-hw.tex b/Теория автоматов/fsm-hw/fsm-hw.tex
new file mode 100644
index 0000000..9ffaf83
--- /dev/null
+++ b/Теория автоматов/fsm-hw/fsm-hw.tex
@@ -0,0 +1,286 @@
+\documentclass[a4paper,oneside,12pt]{extarticle}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T2A]{fontenc}
+\usepackage[english,russian]{babel}
+\usepackage[
+  left=3cm, right=3cm,
+  top=2cm, bottom=2cm
+]{geometry}
+
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{mathtools}
+\usepackage{amsfonts}
+\usepackage{enumitem}
+\usepackage{amsthm}
+\usepackage{minted}
+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
+\usepackage{graphicx}
+\graphicspath{ {./images/} }
+\usepackage{float}
+\usepackage{underscore}
+\usepackage{braket}
+
+\usepackage{enumitem}
+\makeatletter
+\AddEnumerateCounter{\asbuk}{\russian@alph}{щ}
+\makeatother
+
+\newtheorem{theorem}{Теорема}[subsection]
+\newtheorem*{theorem*}{Теорема}
+
+% --- Определение --- %
+\theoremstyle{definition}
+\newtheorem{definition}{Определение}[subsection]
+\newtheorem*{definition*}{Определение}
+% ------------------- %
+
+\title{{Теория автоматов}}
+\author{Гущин Андрей, 431 группа, 1 подгруппа}
+\date{\the\year{} г.}
+
+\begin{document}
+
+\maketitle
+
+\section*{Тема 2}
+
+\subsection*{Задача 2.30 (41)}
+
+Обязательно ли изоморфные автоматы эквивалентны? Доказать или привести
+контрпример. Тот же вопрос в обратную сторону.
+
+\subsection*{Решение}
+
+Два состояния $s_i$ и $s_j$ являются эквивалентными тогда и только тогда, когда,
+наблюдая внешние выходы, нельзя отличить автомат $M_1$ в начальном состоянии
+$s_i$ от автомата $M_2$ в начальном состоянии $s_j$.
+
+Автоматы $M_1$ и $M_2$ являются эквивалентными если каждому состоянию $s_i$ из
+$M_1$ соответствует, по крайней мере, одно эквивалентное состояние в автомате
+$M_2$ и каждому состоянию $s_j$ из $M_2$ соответствует, по крайней мере, одно
+эквивалентное состояние в автомате $M_1$.
+
+Определение эквивалентности автоматов означает, что два автомата, имеющих
+одинаковые таблицы переходов, графы или матрицы должны быть эквивалентны.
+Кроме того, поскольку эквивалентность пары состояний не зависит от обозначений
+состояний, то два изоморфных автомата также должны быть эквивалентными.
+
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.9\textwidth]{2_isomorph}
+  \caption{Изоморфные графы}
+\end{figure}
+
+Обратное в общем случае неверно. Например:
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.8\textwidth]{2_equiv}
+  \caption{Эквивалентные, но не изоморфные графы}
+\end{figure}
+
+
+\newpage
+\section*{Тема 3}
+
+\subsection*{Задача 3.23 (32)}
+
+Постройте автомат, от которого никаким экспериментом длины 4 нельзя отличить
+автомат на рисунке, в предположении, что автоматы не эквивалентны.
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.5\textwidth]{3_23_problem}
+\end{figure}
+
+\subsection*{Решение}
+
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.9\textwidth]{3_23_solution}
+\end{figure}
+
+
+\newpage
+\section*{Тема 4}
+
+\subsection*{Задача 4.23 (а, б, в)}
+
+Постройте автомат с двумя состояниями, отвечающий следующим требованиям:
+\begin{enumerate}[label=(\asbuk*)]
+  \item чтобы он не был автоматом с конечной памятью;
+  \item чтобы он был автоматом с конечной памятью, но не зависящим от выхода;
+  \item чтобы он был не зависящим от выхода автоматом.
+\end{enumerate}
+
+\subsection*{Решение}
+
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.9\textwidth]{4_a}
+  \caption{Задача (а)}
+\end{figure}
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.9\textwidth]{4_b}
+  \caption{Задача (б)}
+\end{figure}
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.8\textwidth]{4_v}
+  \caption{Задача (в)}
+\end{figure}
+
+
+
+\newpage
+\section*{Тема 5}
+
+\subsection*{Задача 5.2}
+
+Преобразуйте следующий НКА в эквивалентный ДКА.
+
+\begin{table}[H]
+  \centering
+  \begin{tabular}{c||c|c}
+                    & 0             & 1            \\ \hline \hline
+    $\rightarrow p$ & $\set{q, s}$  & $\set{q}$    \\
+    $^*q$           & $\set{r}$     & $\set{q, r}$ \\
+    $r$             & $\set{s}$     & $\set{p}$    \\
+    $^*s$           & $\varnothing$ & $\set{p}$    \\
+  \end{tabular}
+\end{table}
+
+\subsection*{Решение}
+
+Изобразим данный НКА в виде графа:
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.5\textwidth]{5_nondet}
+\end{figure}
+
+Построим ДКА, эквивалентный данному НКА следующим образом:
+состояниями в ДКА будут являться множества состояний, в которых может
+находиться НКА. Переходами между этими состояниями будут переходы в НКА,
+которые переводят одно множество состояний в другое множество состояний.
+
+Таким образом, получим следующий автомат:
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.8\textwidth]{5_det}
+\end{figure}
+
+
+
+
+\newpage
+\section*{Тема 6}
+
+\subsection*{Задача 6.1}
+
+Вариант 6 --- $6_{10} = 0020_3$, $0020_3 + 2121_3 = 2111_3$
+
+Найти кратчайшую синхронизирующую последовательность для вашего варианта
+автомата или доказать, что ее не существует.
+
+Матрица автомата по варианту:
+\begin{table}[H]
+  \centering
+  \begin{tabular}{|c|c|c|}
+    \hline
+      & a & b \\ \hline
+    0 & 0 & 2 \\ \hline
+    1 & 0 & 1 \\ \hline
+    2 & 2 & 1 \\ \hline
+    3 & 0 & 1 \\ \hline
+  \end{tabular}
+\end{table}
+
+\subsection*{Решение}
+
+Изобразим данный автомат в виде графа:
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.65\textwidth]{6_graph}
+\end{figure}
+
+Можно заметить, что все переходы с символом $b$ ведут в сторону состояния 1.
+
+\begin{itemize}
+  \item
+    Пусть автомат находится в состоянии 1 --- если ввести слово $bb$, то
+    автомат останется в состоянии 1;
+  \item
+    Пусть автомат находится в состоянии 0 --- если ввести слово $bb$, то
+    автомат перейдёт сначала в состояние 2, а потом в состояние 1;
+  \item
+    Пусть автомат находится в состоянии 2 --- если ввести слово $bb$, то
+    автомат перейдёт в состояние 1 и после этого останется в нём.
+\end{itemize}
+
+Таким образом, автомат синхронизируем последовательностью $bb$.
+
+
+\newpage
+\section*{Тема 7}
+
+\subsection*{Задача}
+
+Вариант 6 --- $6_{10} = 0110_2 \implies x_1 = 0, x_2 = 1, x_3 = 1, x_4 = 0$.
+
+Рассмотрим в качестве клеточного автомата (\textbf{бесконечную во все
+стороны}) плоскость, разбитую на квадраты равного размера (\textbf{клетки}).
+\textbf{Клетки} могут быть окрашены черным либо белым цветом, что составляет
+их состояние в моменты 0, 1, 2, \dots. Состояние автомата в момент $t$ --- это
+совокупность состояний всех клеток плоскости. \textbf{Невырожденным состоянием}
+назовем любое состояние автомата, при котором и черные, и белые клетки.
+
+Окрестностью клетки двумерного клеточного автомата назовем объединение этой
+клетки с окрестностью Мура (8 соседей, $6 \pmod{3} = 0$):
+\begin{figure}[H]
+  \centering
+  \includegraphics[width=0.2\textwidth]{7_moore}
+\end{figure}
+
+\textbf{Зададим правило перехода}: в момент $t + 1$ клетка приобретает тот
+цвет, который имело четное ($x_2 = 1$) количество клеток из ее окрестности
+в момент $t$ (где 0 также считается четным числом). Требуется найти такое
+\textbf{невырожденное} начальное состояние, при котором черные клетки в какой-то
+момент исчезнут, но потом появятся ($x_3 x_4 = 10$).
+
+Если искомого невырожденного состояния не существует, доказать это. Исследуемый
+процесс изобразить графически.
+
+\subsection*{Решение}
+
+Чёрные клетки никогда не исчезнут.
+
+Допустим, мы установили в поле одну клетку чёрного цвета, оставив всю остальную
+бесконечную плоскость заполненную белыми клетками. В следующий момент
+времени все клетки, кроме окрестности чёрной клетки перекрасятся в чёрный,
+первоначальная точка станет белой, а её окрестность останется неизменной. То
+есть получится квадрат со стороной в 3 клетки полностью состоящий из белых клеток.
+
+В следующий шаг изначальная клетка снова перекрасится в чёрный, её окрестности
+станут белыми, а клетки на углах окрестности станут чёрными. Все остальные клетки
+снова станут белыми.
+
+В следующий шаг это снова повторится и первоначальная клетка будет чередовать
+свой цвет в каждый момент времени.
+
+Так как клетки с обоими цветами ведут себя симметрично, если закрасить всю
+плоскость чёрными клетками, кроме одной, получится симметричный вариант
+чередования цветов первоначальной клетки.
+
+При этом если предположить, что мы закрашиваем только некоторую конечную часть
+плоскости, то на бесконечной плоскости всегда найдётся клетка с противоположным
+цветом с одной и клеток внутри этой конечной части.
+
+То есть в любой момент времени на плоскости есть клетки с противоположными
+цветами, если начальное состояние плоскости было невырожденным.
+
+Видео с демонстрацией данного процесса приложено к письму.
+
+
+\end{document}
+