diff options
Diffstat (limited to 'Теория автоматов/fsm-hw')
| -rw-r--r-- | Теория автоматов/fsm-hw/fsm-hw.pdf | bin | 0 -> 4812730 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/fsm-hw.tex | 286 | ||||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/2_equiv.jpeg | bin | 0 -> 830195 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/2_isomorph.jpeg | bin | 0 -> 728788 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/3_23_problem.png | bin | 0 -> 78196 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/3_23_solution.jpeg | bin | 0 -> 985384 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/4_a.jpeg | bin | 0 -> 201146 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/4_b.jpeg | bin | 0 -> 162979 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/4_v.jpeg | bin | 0 -> 149885 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/5_det.jpeg | bin | 0 -> 631843 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/5_nondet.jpeg | bin | 0 -> 637376 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/6_graph.jpeg | bin | 0 -> 288948 bytes | |||
| -rw-r--r-- | Теория автоматов/fsm-hw/images/7_moore.png | bin | 0 -> 11489 bytes | |||
| -rwxr-xr-x | Теория автоматов/fsm-hw/maker.sh | 35 |
14 files changed, 321 insertions, 0 deletions
diff --git a/Теория автоматов/fsm-hw/fsm-hw.pdf b/Теория автоматов/fsm-hw/fsm-hw.pdf Binary files differnew file mode 100644 index 0000000..2873b86 --- /dev/null +++ b/Теория автоматов/fsm-hw/fsm-hw.pdf 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} + diff --git a/Теория автоматов/fsm-hw/images/2_equiv.jpeg b/Теория автоматов/fsm-hw/images/2_equiv.jpeg Binary files differnew file mode 100644 index 0000000..ae1cd39 --- /dev/null +++ b/Теория автоматов/fsm-hw/images/2_equiv.jpeg diff --git a/Теория автоматов/fsm-hw/images/2_isomorph.jpeg b/Теория автоматов/fsm-hw/images/2_isomorph.jpeg Binary files differnew file mode 100644 index 0000000..7d1f7ec --- /dev/null +++ b/Теория автоматов/fsm-hw/images/2_isomorph.jpeg diff --git a/Теория автоматов/fsm-hw/images/3_23_problem.png b/Теория автоматов/fsm-hw/images/3_23_problem.png Binary files differnew file mode 100644 index 0000000..c368554 --- /dev/null +++ b/Теория автоматов/fsm-hw/images/3_23_problem.png diff --git a/Теория автоматов/fsm-hw/images/3_23_solution.jpeg b/Теория автоматов/fsm-hw/images/3_23_solution.jpeg Binary files differnew file mode 100644 index 0000000..8d2b4f5 --- /dev/null +++ b/Теория автоматов/fsm-hw/images/3_23_solution.jpeg diff --git a/Теория автоматов/fsm-hw/images/4_a.jpeg b/Теория автоматов/fsm-hw/images/4_a.jpeg Binary files differnew file mode 100644 index 0000000..c1382da --- /dev/null +++ b/Теория автоматов/fsm-hw/images/4_a.jpeg diff --git a/Теория автоматов/fsm-hw/images/4_b.jpeg b/Теория автоматов/fsm-hw/images/4_b.jpeg Binary files differnew file mode 100644 index 0000000..997f44e --- /dev/null +++ b/Теория автоматов/fsm-hw/images/4_b.jpeg diff --git a/Теория автоматов/fsm-hw/images/4_v.jpeg b/Теория автоматов/fsm-hw/images/4_v.jpeg Binary files differnew file mode 100644 index 0000000..4d7e179 --- /dev/null +++ b/Теория автоматов/fsm-hw/images/4_v.jpeg diff --git a/Теория автоматов/fsm-hw/images/5_det.jpeg b/Теория автоматов/fsm-hw/images/5_det.jpeg Binary files differnew file mode 100644 index 0000000..630d5a4 --- /dev/null +++ b/Теория автоматов/fsm-hw/images/5_det.jpeg diff --git a/Теория автоматов/fsm-hw/images/5_nondet.jpeg b/Теория автоматов/fsm-hw/images/5_nondet.jpeg Binary files differnew file mode 100644 index 0000000..72cd309 --- /dev/null +++ b/Теория автоматов/fsm-hw/images/5_nondet.jpeg diff --git a/Теория автоматов/fsm-hw/images/6_graph.jpeg b/Теория автоматов/fsm-hw/images/6_graph.jpeg Binary files differnew file mode 100644 index 0000000..4b21a58 --- /dev/null +++ b/Теория автоматов/fsm-hw/images/6_graph.jpeg diff --git a/Теория автоматов/fsm-hw/images/7_moore.png b/Теория автоматов/fsm-hw/images/7_moore.png Binary files differnew file mode 100644 index 0000000..d1e6323 --- /dev/null +++ b/Теория автоматов/fsm-hw/images/7_moore.png diff --git a/Теория автоматов/fsm-hw/maker.sh b/Теория автоматов/fsm-hw/maker.sh new file mode 100755 index 0000000..e847acf --- /dev/null +++ b/Теория автоматов/fsm-hw/maker.sh @@ -0,0 +1,35 @@ +#!/bin/sh + +watch() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode -pvc $1 +} + +doc() { + [ -z "$1" ] && echo "Необходимо указать название основного документа" && help + set -o xtrace + latexmk -pdf -f -shell-escape -interaction=nonstopmode $1 +} + +clean() { + set -o xtrace + rm -rf _minted-* + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc +} + +help() { + echo "Использование:" + echo "./maker.sh watch <main-doc>.tex -> Запуск процесса, пересобирающего документ при изменениях" + echo "./maker.sh doc <main-doc>.tex -> Пересобрать документ" + echo "./maker.sh clean -> Удаление сгенерированных файлов" + exit 1 +} + +case "$1" in + watch) watch $2 ;; + doc) doc $2 ;; + clean) clean ;; + *) help ;; +esac |
