lab_4.tex

\chapter{Лабораторная работа №4\\Конечные автоматы} 

\par{Когда мы проектировали секундомер, у нас возникла необходимость выделить признак того, что в данный момент секундомер работает. Для этого мы создали специальный регистр для хранения этого признака и описали схему управления этим регистром. В других блоках секундомера мы могли проверить признак работы (содержание регистра) и, в зависимости от него, разрешить, запретить или изменить работу.}

\par{Похожий подход применяется и в других случаях, когда необходимо выделить разные режимы работы цифрового устройства или обеспечить последовательное выполнение некоторых операций.}

\par{Действительно, ведь цифровое устройство существует целиком в один момент времени. Тогда как возможно добиться от него последовательного выполнения каких-то действий?}

\par{Вариант только один – описать ещё один блок, который будет управлять работой всей остальной части цифрового устройства.}

\par{Блок, который используется для этого, называется \quotes{конечный автомат}.}

\par{Существует целый раздел математики, посвященный автоматам (и в частности конечным автоматам), который, вполне ожидаемо, называется \quotes{теория автоматов}.}

\par{Но, так как нас, прежде всего, интересует прикладное применение конечных автоматов, мы рассмотрим их с точки зрения цифровой схемотехники.}

\par{\textbf{\textit{В цифровой схемотехнике, конечным автоматом называется цифровая схема, которая отслеживает текущее состояние и обеспечивает переход от одного состояния к другому в зависимости от входных воздействий.}}}

\par{Например, в случае секундомера, который мы проектировали в прошлой лабораторной работе, конечный автомат, который мог бы управлять им, переключался бы между двумя состояниями: \quotes{остановлен} и \quotes{работает}.}

\par{Для удобства проектирования конечный автомат представляют в виде графа. Вершины графа - это состояния, а рёбра графа - это воздействия, которые приводят к изменению состояния. Этот граф называют графом переходов конечного автомата.}

\par{Обычно граф переходов выглядит подобным образом:}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/graph_1}
  \caption{Граф переходов конечного автомата}
\end{figure}

\par{Граф переходов – это основной источник информации о конечном автомате. Он дает наглядное представление о том, как управляется и работает конечный автомат.}

\par{Обратите внимание – конечный автомат всегда пребывает в одном из своих состояний. Конечный автомат не может пребывать в двух состояниях одновременно.  Чем-то граф переходов может напомнить вам игровую доску, где фишка находится на одном из полей и, в зависимости от выполненных условий, может перейти в одно из полей, соединённых с текущим.}

\par{Классическим примером, наглядно демонстрирующим работу конечных автоматов, может служить конечный автомат управления светофором. Попробуем разработать такой автомат.}

\par{Можно легко выделить состояния светофора: \quotes{горит зеленый} - \quotes{мигает зеленый} - \quotes{горит желтый} - \quotes{горит красный} - \quotes{горит желтый и красный} - \quotes{мигает желтый}.}

\par{Обратите внимание: автомат управления не может находиться в двух состояниях одновременно и, поэтому, чтобы описать ситуацию когда горят одновременно желтый и красный сигналы, нам потребовалось ввести новое состояние - \quotes{горит желтый и красный}.}

\par{Обозначим все вершины графа – состояния конечного автомата:}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/light_vert}
  \caption{Вершины графа переходов конечного автомата}
\end{figure}

\par{Теперь стрелками отметим на графе все возможные переходы из каждого состояния.}

\par{Например, из состояния \quotes{мигает зеленый} светофор может переключиться в состояние \quotes{горит желтый} или, если регулирование закончилось, в состояние \quotes{мигает желтый}.}

\par{Над каждой стрелкой подпишем условие, которое должно выполниться, чтобы переход произошел. Т.е. над стрелкой от \quotes{мигает зеленый} к \quotes{горит желтый} напишем условие: \quotes{прошло 5 секунд}, а над стрелкой от \quotes{мигает зеленый} к \quotes{мигает желтый} напишем условие \quotes{конец регулирования}.}

\par{В итоге получим полный граф переходов конечного автомата:}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/light_graph}
  \caption{Граф переходов конечного автомата для управления светофором}
\end{figure}

\par{Изучите его работу. Проследите, как можно попасть в то или иное состояние.}

\par{Обратите внимание, что одни и те же входные воздействия могут приводить к разным переходам, если они возникают в разных состояниях конечного автомата.}

\par{Итак, для того чтобы реализовать в цифровой схемотехнике такое устройство, нам понадобятся регистр для хранения состояния (назовём его \textbf{\quotes{регистр состояния}}).}

\par{Также понадобится схема, которая будет принимать решение о том, какое состояние будет следующим. Посмотрите на граф: входом такой схемы должно быть текущее состояние и входные воздействия. Имея эту информацию можно определить, какое состояние будет следующим.}

\par{Регистр состояния, очевидно, синхронная схема. То есть, переход между состояниями может произойти только по положительному фронту тактового сигнала. Но как определить сам момент, когда необходимо переключиться? Ведь он зависит от входных воздействий – переход должен состояться, когда будут выполнены необходимые условия.}

\par{В такой ситуации поступают следующим образом: \textbf{регистр состояний меняет текущее состояние на следующее каждый такт вне зависимости ни от каких условий.} При этом следующее состояние, пока условия не выполнены, равно текущему. Таким образом, значение регистра не меняется, пока не будут выполнены условия перехода.}

\par{Схема определения следующего состояния - асинхронная.}

\par{Входами этой схемы служат текущее состояние и все возможные входные сигналы (условия переходов). Выходом этой схемы будет следующее состояние.}

\par{Так как мы знаем все переходы, мы, фактически, определяем таблично заданную ФАЛ. Значит, эта схема является \textbf{дешифратором}.}

\par{Структура конечного автомата будет выглядеть следующим образом:}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/decoder_sm}
  \caption{Структура конечного автомата}
\end{figure}

\par{Так как в составе конечного автомата присутствует триггер, \textbf{конечный автомат является синхронным цифровым устройством.} Состояния конечного автомата меняются по положительному фронту сигнала синхронизации.}

\par{Используя такую структуру в качестве основы, опишем на языке \eng{Verilog} автомат, реализующий работу светофора.}

\lstinputlisting[caption={Конечный автомат, реализующий работу светофора}, ]{./code_examples/lab_4/lights.v}

\par{Итак, мы реализовали конечный автомат. Но как им пользоваться? Как с помощью автомата управлять работой цифровой схемы?}

\par{Возможно, вы уже догадались, что для управления работой цифрового устройства используют анализ текущего состояния. Текущее состояние, в подавляющем большинстве случаев, и является выходом конечного автомата.}

\par{Анализируя состояние, можно переключать мультиплексоры, подавать (с помощью ФАЛ) необходимые входные воздействия или наборы данных, разрешать или запрещать работу блоков и модулей. Таким образом, можно существенно изменить поведение цифрового устройства.}

\par{Рассмотрим на конкретных примерах, как управлять работой светофора с помощью конечного автомата.}

\par{Управление светодиодами может осуществляться выходами компараторов.}

\par{Например, в состоянии \quotes{Горит зеленый}, компаратор будет выдавать единицу, поступающую на зеленую лампочку.}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/comp}
  \caption{Компаратор для управления светодиодами}
\end{figure}

\par{В состоянии \quotes{Мигает зеленый} все немного сложнее.}

\par{Существуют разные варианты решения этой задачи.}

\par{Один из возможных – следующий: разработать схему, вырабатывающую периодические импульсы, и подключить через вентиль \textbf{И} к сигналу управления зеленой лампой светофора. При этом сам сигнал управления подавать уже не в одном, а в двух состояниях автомата.}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/pulse}
  \caption{Схема управления миганием зелёного светодиода}
\end{figure}

\par{Схема работает следующим образом:}

\begin{figure}[H]
\begin{tikztimingtable}[
    timing/dslope=0.1,
    timing/.style={x=2.8ex,y=2ex},
    very thick,
    x=3ex,
    timing/rowdist=3.3ex,
    timing/d/text/.append style={font=\scriptsize},
    timing/name/.style={font=\sffamily\scriptsize}
]
& 3D {\shortstack{Горит Красный\\и Жёлтый}} 4D{Горит Зелёный} 3.5D{Мигает Зелёный} 2.5D{Горит Жёлтый}\\
& 3L 7.5H 2.5L\\
& 7H 7{c} 2.5H\\
& 7L 3.5H 2.5L\\
& 3L 4H 6{c} 3L\\
    \extracode
    \begin{pgfonlayer}{background}
            \node [align=center,scale=0.7,text width=30ex] at (-10ex, 1.2ex)   {Состояние автомата};
            \node [align=center,scale=0.7,text width=30ex] at (-10ex, -1.8ex)  {Подсветка Зелёной лампы\\К вентилю \quotes{И}};
            \node [align=center,scale=0.7,text width=30ex] at (-10ex, -5.5ex)  {Пульсация Зелёной лампы\\К вентилю \quotes{И}};
            \node [align=center,scale=0.7,text width=30ex] at (-10ex, -9.2ex)  {Разрешение\\пульсации};
            \node [align=center,scale=0.7,text width=30ex] at (-10ex, -12.2ex) {Управление зелёной\\лампой};
        \begin{scope}[semitransparent ,semithick]
        \end{scope}
    \end{pgfonlayer}
\end{tikztimingtable}
\caption{Временная диаграмма работы схемы управления зелёным светодиодом}
\end{figure}

\par{Схему пульсации можно использовать также для того чтобы мигать желтой лампой светофора.}

\par{Вспомним, что в цифровой схемотехнике нельзя закорачивать выходы цифровых блоков. Для того чтобы соединить выходы, необходимо использовать подходящие логические вентили.}

\par{Также вспомним, что автомат может прибывать только в одном своем состоянии.}

\par{Тогда общая схема будет выглядеть следующим образом:}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/pulse_full}
  \caption{Схема управления миганием светодиодов}
\end{figure}

\par{Несмотря на внушительный вид это довольно простая схема:}

\par{Схема пульсации включается, когда автомат находится в состоянии \quotes{Мигает Зеленый} \textbf{ИЛИ} \quotes{Мигает Желтый}.}

\par{Зеленая лампа подсвечивается, когда автомат находится в состоянии \quotes{Горит Зеленый} \textbf{ИЛИ} \quotes{Мигает Зеленый} \textbf{И} при этом выход схемы пульсации равен единице.}

\par{Для желтой лампы ситуация аналогична ситуации для зеленой лампы.}

\par{В форме поведенческого кода данная схема выглядит еще проще для понимания:}

\lstinputlisting[caption={Описание схемы пульсации лампы светофора}, ]{./code_examples/lab_4/pulse.v}

\par{Хотелось бы сразу отметить некоторую особенность реализации конечного автомата в виде цифрового устройства. Взгляните на следующий граф переходов:}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/simple_graph}
  \caption{Граф переходов конечного автомата с двумя состояниями}
\end{figure}

\par{Несмотря на свою примитивность на его примере хорошо видно реакцию конечного автомата на внешнее воздействие.}

\par{Регистр состояния защелкивает новое состояние каждый такт, поэтому для того, чтобы автомат переключился из состояния \quotes{1} в состояние \quotes{2}, требуется, чтобы входное воздействие \quotes{a} имело единичную длительность.}

\par{В противном случае автомат переключится из состояния \quotes{1} в состояние \quotes{2}, затем, на следующий такт автомат переключится из состояния \quotes{2} в состояние \quotes{1} и так далее, пока не закончится входное воздействие.}

\par{Сравните временные диаграммы ниже, чтобы лучше почувствовать разницу.}

\begin{figure}[H]
\centering
\begin{tikztimingtable}[%
    timing/dslope=0.1,
    timing/.style={x=5ex,y=2ex},
    very thick,
    x=3ex,
    timing/rowdist=3.3ex,
    timing/name/.style={font=\sffamily\scriptsize},
]
  clk & 16{c} \\
  a & 1.5L 1H 5.5L\\
  state & 2.5D{1} 5.5D{2}\\
    \\
  clk & 16{c} \\
  a & 1.5L 5H 1.5L\\
  state & 2.5D{1} 1D{2} 1D{1} 1D{2} 1D{1} 1.5D{2}\\
\extracode
\end{tikztimingtable}
\caption{Временные диаграммы конечного автомата с различной продолжительностью входного воздействия}
\end{figure}

\par{Кроме разделения режимов работы конечные автоматы позволяют цифровым устройствам \quotes{выполнять} некоторые алгоритмы действий. Ведь мы можем и не ставить условий для перехода из некоторых состояний в другие. Посмотрите на граф ниже - он очень напоминает алгоритм программы.}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/graph_exam}
  \caption{Граф переходов, показывающий алгоритм выполнения программы}
\end{figure}

\par{Мы вполне можем описать автомат, реализующий этот граф переходов:}

\lstinputlisting[caption={Описание конечного автомата для приведенного графа переходов}, ]{./code_examples/lab_4/sm_example.v}

\par{Отметим некоторые особенности таких автоматов. Обратите внимание на условия переходов. Условия присутствуют практически во всех состояниях, даже если переход между ними линеен. Например, переход из состояния \qeng{calc\_checksum} в состояние \qeng{send\_data}. Если для вычисления контрольной суммы требуется более одного такта, то без проверки выполнена ли операция нельзя покидать состояние вычисления контрольной суммы.}

\par{Разберем структуру цифрового устройства, которым будет управлять приведенный выше конечный автомат.}

\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/struct}
  \caption{Структура устройства для обмена данными}
\end{figure}

\par{Как разработать подобную структуру?}

\par{Первое, что необходимо понимать, что блоки цифровых устройств существуют вне зависимости от того, используются ли они в данный момент или нет.}

\par{Теперь мы постараемся разбить устройство на блоки, определить функционал каждого из этих блоков и соединить их между собой.}

\par{Начинается разработка схемы с конечного автомата.}

\par{Наш конечный автомат уже разработан. Его мы помещаем в центр будущей структуры. Выходом конечного автомата служит текущее состояние. Именно его анализируют все остальные блоки устройства.}

\par{Теперь, когда мы поместили конечный автомат, приступим к проектированию периферии. Сначала регистр для того, чтобы защелкнуть и сохранить данные, которые в дальнейшем будем обрабатывать и передавать.}

\par{Когда необходимо защелкнуть данные? В самом начале работы. Т.е. в состоянии \qeng{idle}, в момент, когда на вход пришел сигнал \qeng{new\_data}.}

\par{Идем дальше по алгоритму работы автомата. Теперь автомат переключился в состояние \qeng{calc\_checksum}. В структуру устройства необходимо добавить модуль, который будет считать контрольную сумму. Этот модуль будет производить вычисления, только когда автомат находится в состоянии \qeng{calc\_checksum}. После окончания вычисления контрольная сумма должна быть на выходе этого модуля и больше не должна меняться. Также этот модуль после завершения вычисления контрольной суммы должен выработать признак \qeng{checksum\_calc\_complete} для конечного автомата. Контрольную сумму можно сбросить в состоянии \qeng{idle}.}

\par{Теперь автомат переходит в состояние \qeng{send\_data}. Для отправки уже должен быть сформирован пакет из данных и контрольной суммы (например, в виде объединенных шин).}

\par{Чаще всего контроллеры работают следующим образом. По сигналу разрешения записи данные с входа помещаются во внутренний регистр и, затем, начинается их отправка.}

\par{Именно поэтому мы использовали состояние, в котором наш конечный автомат проводит только один такт. Именно в этом состоянии происходит загрузка и запуск передатчика, а именно выработка сигнала \quotes{разрешение записи} для него.}

\par{Далее автомат попадает в состояние ожидание ответа. Для получения ответа, нам понадобится модуль приемника. Модуль приемника будет выставлять на шину значение принятых данных, а также он должен будет вырабатывать сигнал \qeng{answer\_received} для работы конечного автомата.}

\par{Для функционирования конечного автомата нам также понадобится сигнал \qeng{waiting\_too\_long}, который сигнализирует об отсутствии ответа в течение слишком большего времени. Чтобы выработать такой сигнал, поместим в устройство счётчик, который будет работать все время, пока автомат находится в состоянии \qeng{waiting\_for\_answer}. Счётчик, при достижении максимального значения (которое мы зададим самостоятельно) будет вырабатываться сигнал \qeng{waiting\_too\_long}. Обычно его называют \quotes{сторожевой счётчик}.}

\par{Итак, если ответ получен, то его надо обработать. Мы разработали конечный автомат так, что обработка должна произойти за один такт, ведь в состоянии \qeng{analyse\_answer} нет условий, говорящих о конце обработки. Внесем в устройство модуль, анализирующий ответ, полученный модулем приемника.}

\par{Осталось только одно состояние, в котором мы не определили входные данные для конечного автомата. Это состояние \qeng{try\_second\_time}. Нам понадобится схема, вырабатывающая сигнал \qeng{already\_tried}. }

\par{Это довольно простая схема: регистр, на вход которого подается единица. Регистр сбрасывается в состоянии \qeng{idle}, а запись в него разрешена только в состоянии \qeng{try\_second\_time}. Выход этого регистра и есть \qeng{already\_tried}.}

\par{Когда мы попадаем в состояние \qeng{try\_second\_time}, мы видим, что в регистре записан \quotes{0}, и переходим в состояние \qeng{send\_data} для повторной отправки данных. В этот же момент времени происходит запись \quotes{1} в регистр. Теперь, если мы снова окажемся в состоянии \qeng{try\_second\_time}, мы увидим в регистре \quotes{1} и не будем осуществлять повторную отправку данных. }

\par{Таким образом, мы закончили описание структуры нашего цифрового устройства. Мы знаем, из каких модулей оно должно состоять и как должен функционировать каждый из этих модулей.}

\par{В рамках данной лабораторной работы нас не интересует конкретная реализация модулей. Но стоит заметить, что начав описание тех или иных из них, разработчик может столкнуться с необходимостью добавить новые управляющие сигналы, ввести новые состояния конечного автомата или добавить новые связи.}

\par{Эти случаи вовсе не редкость. При проектировании цифровых устройств, практически каждый разработчик неоднократно корректирует изначально разработанную им структуру. Как правило, по мере получения опыта уменьшается количество подобных правок.}

\par{Вы увидели, как разрабатывается структура цифровых устройств, включающих конечные автоматы.}

\par{Вы убедились, что структуры, необходимые для реализации тех или иных действий существуют одновременно, поэтому исполнение некоторых алгоритмов может быть связано с очень большими аппаратными затратами.}

\par{В таких случаях используют другие подходы к построению цифровых устройств, например, использование вычислительных ядер с программным управлением, с устройством которых вы познакомитесь в курсе \quotes{Микропроцессорные системы и средства}.}

\par{Тем не менее, выполнение простых алгоритмов, например, алгоритмов управления с малым количеством ветвлений, часто перекладывается на конечные автоматы с целью минимизации программного кода и ускорения работы.}

\section{Задание лабораторной работы}

\begin{enumerate}[noitemsep,topsep=0pt, after=\vspace{2pt}]
\item{Изучить разработку к лабораторной работе.}
\item{Реализовать конечный автомат, согласно индивидуальному заданию.}
\item{Ответьте на вопросы к защите лабораторной работы.}
\end{enumerate}


\begin{figure}[H]
  \centering
  \def\svgwidth{\columnwidth}
  \includesvg{images/lab_4/graph_2}
  \caption{Пример задания лабораторной работы}
\end{figure}


\clearpage
\section{Варианты индивидуальных заданий}


\begin{enumerate}
  

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (2) edge [bend left]   node {$a$} (3);
      \path (3) edge    node {$b$} (1);
      \path (1) edge    node {$c$} (2);
      \path (3) edge  [bend left]  node {$a$} (4);
      \path (4) edge  [bend left]  node {$b$} (3);
      \path (3) edge  [bend left]  node {$c$} (2);

    \end{tikzpicture}

  }


  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (2) edge  [bend left]  node {$a$} (1);
      \path (4) edge    node {$b$} (2);
      \path (1) edge  [bend left]  node {$c$} (2);
      \path (4) edge  [bend left]  node {$a$} (3);
      \path (4) edge    node {$c$} (1);
      \path (3) edge  [bend left]  node {$b$} (4);

    \end{tikzpicture}

  }

  \clearpage

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (1) edge  [bend left]  node {$a$} (4);
      \path (3) edge  [bend left]  node {$b$} (2);
      \path (2) edge  [bend left]  node {$c$} (3);
      \path (4) edge  [bend left]  node {$a$} (1);
      \path (3) edge    node {$c$} (1);
      \path (4) edge    node {$b$} (3);

    \end{tikzpicture}

  }

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (3) edge    node {$a$} (1);
      \path (3) edge  [bend left]  node {$b$} (2);
      \path (1) edge  [bend left]  node {$c$} (4);
      \path (2) edge  [bend left]  node {$a$} (3);
      \path (4) edge  [bend left]  node {$c$} (1);
      \path (1) edge    node {$b$} (2);

    \end{tikzpicture}

  }

  \clearpage

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (2) edge  [bend left]  node {$a$} (3);
      \path (3) edge  [bend left]  node {$b$} (4);
      \path (2) edge    node {$c$} (1);
      \path (4) edge  [bend left]  node {$a$} (3);
      \path (3) edge  [bend left]  node {$c$} (2);
      \path (1) edge    node {$b$} (3);

    \end{tikzpicture}

  }

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (3) edge    node {$a$} (4);
      \path (1) edge    node {$b$} (2);
      \path (1) edge  [bend left]  node {$c$} (3);
      \path (2) edge    node {$a$} (3);
      \path (3) edge  [bend left]  node {$c$} (1);
      \path (4) edge    node {$b$} (1);

    \end{tikzpicture}

  }


  \clearpage

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (3) edge    node {$a$} (4);
      \path (2) edge    node {$b$} (3);
      \path (1) edge  [bend left]  node {$b$} (4);
      \path (1) edge    node {$a$} (2);
      \path (1) edge    node {$c$} (3);
      \path (4) edge  [bend left]  node {$c$} (1);

    \end{tikzpicture}

  }

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (1) edge    node {$a$} (3);
      \path (3) edge  [bend left]  node {$b$} (4);
      \path (3) edge    node {$c$} (2);
      \path (2) edge  [bend left]  node {$a$} (1);
      \path (4) edge  [bend left]  node {$c$} (3);
      \path (1) edge  [bend left]  node {$b$} (2);

    \end{tikzpicture}

  }


  \clearpage

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (1) edge    node {$a$} (2);
      \path (1) edge    node {$b$} (3);
      \path (4) edge  [bend left]  node {$c$} (3);
      \path (4) edge    node {$a$} (1);
      \path (2) edge    node {$c$} (3);
      \path (3) edge  [bend left]  node {$b$} (4);

    \end{tikzpicture}

  }

  \item{

    Граф конечного автомата:\\

    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=3.5cm,
            scale = 1.2,transform shape]

      \node[state] (1)              {$1$};
      \node[state] (2) [right of=1] {$2$};
      \node[state] (3) [below of=2] {$3$};
      \node[state] (4) [below of=1] {$4$};

      \path (1) edge    node {$a$} (3);
      \path (4) edge  [bend left]  node {$b$} (1);
      \path (3) edge    node {$c$} (4);
      \path (2) edge    node {$a$} (3);
      \path (1) edge  [bend left]  node {$c$} (4);
      \path (1) edge    node {$b$} (2);

    \end{tikzpicture}

  }


\end{enumerate}

\clearpage

\section{Вопросы к защите лабораторной работы}

\begin{enumerate}[noitemsep,topsep=0pt, after=\vspace{2pt}]
  \item{Что такое конечный автомат?}
  \item{Для чего конечные автоматы используются в цифровых устройствах?}
  \item{Из каких цифровых блоков состоит конечный автомат?}
  \item{Конечный автомат это синхронное или асинхронное устройство?}
  \item{Работу какого цифрового блока конечного автомата определяет граф переходов?}
  \item{Почему для верного функционирования конечного автомата важна длительность управляющих сигналов?}
  \item{Изучите рисунок структуры цифрового устройства на стр.10. Назовите значение состояния автомата, анализируемое каждым из компараторов.}

\end{enumerate}