Теория автоматов

 

Для частичных автоматов функции  переходов и выходов определены не для всех пар (a_m,z_f). В клетке неопределенности ставится прочерк.

Автомат называется детерминированным, если выполнено условие однозначности переходов. Автомат, заданный таблицей переходов, всегда детерминированный. В графе детерминированного автомата из одной вершины не могут  выходить две и более дуги, отмеченные одним и тем же выходным сигналом.

Выделение в множестве состояний  начального состояния объясняется  чисто практическими соображениями, связанными с необходимостью фиксировать условия начала работы дискретного устройства. Автомат с выделенным начальным состоянием называется инициальным.

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

Выходной сигнал в автомате Мили зависит как от входного сигнала, так и от текущего состояния автомата. Поэтому, если заключительное состояние автомата определено, то выходной сигнал на последнюю букву входного слова появляется в момент появления этой буквы.

Выходной сигнал автомата Мура зависит  только от текущего состояния автомата. Поэтому в начальный момент времени выход автомата не связан со значением входного сигнала, так как начальное состояние автомата никак не связано со значением входного сигнала.  Выходной сигнал автомата в ответ на последнее входное слово появляется в следующем такте автоматного времени после прихода последнего входного слова, если определено заключительное состояние, соответствующее входному слову.

Абстрактный автомат может быть также задан матрицей соединений. Матрица соединений абстрактного автомата является квадратной и содержит столько столбцов (строк), сколько  различных состояний имеет рассматриваемый автомат. Каждый столбец (строка) матрицы соединений помечается буквой состояния автомата. Если автомат инициальный, то первый слева столбец и первая сверху строка матрицы помечаются буквой его  начального состояния. На пересечении i-й строки и j-го столбца записывается входной сигнал или дизъюнкция входных сигналов, инициирующих переход из состояния a_i в состояние a_j. Если матрицей соединений задается автомат Мили, то рядом с буквой  входного сигнала в скобках указывается имя выходного сигнала. В случае автомата Мура выходными сигналами помечаются состояния автомата, идентифицирующие строки матрицы соединений.

При графическом способе задания  автомат представляется орграфом. Состояниям автомата соответствует множество вершин графа, а дугами обозначаются переходы в автомате. Входные сигналы, инициирующие переход, и выходные сигналы, вырабатываемые на этом переходе (для автомата Мили), помечают дугу соответствующего перехода. В графе автомата Мура входные сигналы помечают дуги, а выходной сигнал записывается непосредственно у вершины, обозначающей состояние автомата. Это отражает тот факт, что в автомате Мура входной сигнал определяется только текущим состоянием автомата и вырабатывается в течение всего времени, пока автомат находится в этом состоянии.

Разработка реальных автоматов  требует их задания вначале на абстрактном уровне с последующим  переходом на структурный уровень, учитывающий используемые в автомате логические элементы и связи между ними.

В заключение определим синхронные и асинхронные автоматы.

Состояние автомата называется устойчивым, если для любого входа z_fÎZ такого, что d(a_i,z_f) = a_s, имеет место d(a_s,z_f) = a_s. Это означает, что если автомат пришел в некоторое состояние под воздействием входного сигнала z_f, то выйти их этого состояния он может только при поступлении на вход другого сигнала. Автомат называется асинхронным, если каждое его состояние устойчиво. В противном случае автомат называется синхронным.

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

 

Совмещенная модель автомата (С-автомат)

В С-автомате реализуются две функции  выходов: автомата Мили и автомата Мура. Это оказывается удобным в ряде приложений. Так, при проектировании ЭВМ часть сигналов устройства управления: передача из регистра в регистр, наращивание счетчика и другие - совпадают по длительности с входным сигналом, тактированным  синхроимпульсом, тогда как, например, сигналы  подачи на комбинационный сумматор или дешифратор памяти обычно значительно длиннее и определяются временами срабатывания сумматора и дешифратора.  Эти сигналы удобно отождествлять с состоянием. Таким образом, соображения практического характера приводят к целесообразности рассмотрения С-автомата - совмещенной модели автоматов Мили и Мура.

При задании С-автомата используют табличный или графический методы. В первом случае отмеченная таблица переходов-выходов дополняется строкой, в которой каждому состоянию автомата сопоставляется выходной сигнал, как в автомате Мура.

Функционирование цифрового  автомата во времени

Пусть алфавит входных сигналов состоит из двух элементов Z={0,1}. Множество состояний также представлено двухэлементным множеством A={0,1}. Входное слово абстрактного автомата - это цепочка входных символов, т.е. двоичное слово конечной длины, например, (101001). Автомат Мура задан отмеченной таблицей переходов-выходов:

A Z	0	1	W
0	1	1	1
1	0	0	0

Таблица 19Таблица переходов-выходов автомата Мура

Последовательность состояний, проходимая автоматом при поступлении на вход входного слова, и значения выходных сигналов представлены в табл. 4.

t	z(t)	a(t)	a(t+1)	w(t)
0	1	0	-	-
1	0	0	0	1
2	1	1	1	0
3	0	0	0	1
4	0	1	1	0
5	1	0	0	1
6	-	0	0	1

 Таблица 20 Функционирование во времени автомата Мура

Автомат применим к слову, если в  каждом последующем такте автоматного  времени определена функция переходов для пары (a_i,z_j). При этом значение состояния, вырабатываемого  автоматом при поступлении последнего входного сигнала, называется функцией заключительного состояния. Выходной сигнал, соответствующий последнему входному воздействию, называется функцией заключительного вывода.

Пример. Определить функцию заключительного состояния и заключительного выхода для автомата, заданного таблицей переходов-выходов, применительно к  данному слову:

Автомат Мили задан таблицей

A Z	a0	a1	a2	a3
z1	a1/w1	a2 /w3	a3 /w3	-
z2	a2/w2	-	a0/-	a1/w2

Входное слово  (z₁,z₁,z₂,z₁,z₂), начальное состояние a₀.

Таблица 21 Функционирование во времени автомата Мили

t	a t	zt	wt
1	a0	z1	w1
2	a1	z1	w3
3	a2	z2	*
4	a0	z1	w1
5	a1	z1	w3
6	a2

Функция заключительного выхода определена и равна w₂. Функция заключительного состояния также определена и для данного слова на входе равна a₂.

Канонический метод структурного синтеза цифровых автоматов

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

В отличие от абстрактного автомата, имеющего один входной и один выходной  сигналы, структурный автомат  имеет конечное множество входов и выходов, на которые подаются сигналы в структурном алфавите автомата. Набор всевозможных значений сигналов, подаваемых на один  входной  (выходной) узел, образует структурный входной (выходной)  алфавит автомата. В настоящее время наиболее распространенным структурным алфавитом является двоичный, что объясняется простотой его представления в современных элементах и приборах. Кроме того, для двоичного алфавита  наиболее разработан аппарат булевых функций, позволяющий формализовать многие операции над схемой автомата. В этом случае каждый входной  и выходной сигнал автомата кодируется двоичным вектором, длина которого определяется мощностью исходного множества входных слов автомата.

На этапе структурного синтеза  предварительно выбираются элементарные автоматы, из которых затем путем их композиции строится структурная схема полученного на этапе абстрактного синтеза автомата Мили или Мура  или С-автомата. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.

Теоретическим основанием  канонического  метода структурного синтеза автоматов является теорема о структурной полноте³

Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов-выходов и какую-либо функционально полную систему логических элементов, является структурно полной.

Существует общий конструктивный прием (канонический метод структурного синтеза), позволяющий в рассматриваемом случае свести задачу структурного синтеза произвольных автоматов к задаче синтеза комбинационных схем.

Результатом канонического метода структурного синтеза является система  логических уравнений, определяющих выходные сигналы автомата и функции возбуждения элементов памяти. Эти уравнения называются каноническими.

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

С учетом определения функций  выхода автомата Мили и автомата Мура структурные схемы этих двух типов цифровых автоматов различаются, как показано на Рис. 3.

Рисунок 3 Структурные схемы автоматов Мили и Мура