path: root/Теория автоматов/fsm-hw/fsm-hw.tex

\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}