Теория автоматов представляет собой раздел дискретной математики, изучающий модели преобразователей дискретной информации. Такими преобразователями являются как реальные устройства (компьютеры, живые организмы), так и воображаемые устройства (аксиоматические теории, математические машины). По сути конечный автомат можно охарактеризовать как устройство М , имеющее входной и выходной каналы при этом в каждый из дискретных моментов времени, называемых тактовыми моментами, оно находится в одном из конечных состояний.
По входному каналу в каждый момент времени t =1, 2, ... в устройство М поступают входные сигналы (из некоторого конечного множества сигналов). Задается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния устройства в текущий момент времени. Выходной сигнал зависит от состояния и входного сигнала в текущий момент времени (рис. 1).
Конечный автомат является математической моделью реальных дискретных устройств по переработке информации.
Конечным автоматом называется система А= (X , Q , Y , , ), где X , Q , Y - произвольные непустые конечные множества, а и функции, из которых:
множество X ={a 1 , ..., a m } называется входным алфавитом , а его элементы - входными сигналами , их последовательности - входными словами ;
множество Q ={q 1 , ..., q n } называется множеством состояний автомата, а его элементы - состояниями ;
множество Y ={b 1 , ..., b p } называется выходным алфавитом , его элементы - выходными сигналами , их последовательности - выходными словами ;
функция : X Q Q называется функцией переходов ;
функция :X Q Y называется функцией выходов .
Таким образом, (x , q )Q , (x , q )Y для x X , q Q .
С конечным автоматом ассоциируется воображаемое устройство, которое работает следующим образом. Оно может находиться в состоянии из множества Q , воспринимать сигналы из множества X и выдавать сигналы из множества Y .
Существует несколько эквивалентных способов задания абстрактных автоматов, среди которых можно назвать три: табличный , геометрический и функциональный .
Из определения автомата следует, что его всегда можно задать таблицей с двумя входами, содержащей т строк и п столбцов, где на пересечении столбца q и строки а стоят значения функций (a i , q j ), (a i , q j ).
|
q a |
q 1 |
q j |
q n |
||
|
a 1 |
(a 1 , q 1), (a 1 , q 1) |
(a 1 , q j ), (a 1 , q j ) |
(a 1 , q n ), (a 1 , q n ) |
||
|
a i |
(a i , q 1), (a i , q 1) |
(a i , q j ), (a i , q j ) |
(a i , q n ), (a i , q n ) |
||
|
a m |
(a m , q 1), (a m , q 1) |
(a m , q j ), (a m , q j ) |
(a m , q n ), (a m , q n ) |
Другой способ задания конечного автомата - графический, то есть с помощью графа. Автомат изображается в виде помеченного ориентированного графа Г (Q , D ) с множеством вершин Q и множеством дуг D ={(q j , (a i , q j ))| q j Q , a i X }, при этом дуга (q j , (a i , q j )) помечается парой (a i , (a i , q j )). Таким образом, при этом способе состояния автомата изображают кружками, в которые вписывают символы состояний q j (j = 1, …, n ). Из каждого кружка проводится т стрелок (ориентированных ребер) взаимно-однозначно соответствующих символам входного алфавита X ={a 1 , ..., a m }. Стрелке, соответствующей букве a i X и выходящей из кружка q j Q , приписывается пара (a i , (a i , q j )), причем эта стрелка ведет в кружок, соответствующий (a i , q j ).
Полученный рисунок называется графом автомата или, диаграммой Мура . Для не очень сложных автоматов этот способ более нагляден, чем табличный.
Можно выделить два класса языков для описания функционирования цифровых автоматов: начальные языки и стандартные или автоматные языки.
Начальные языки задают функцию переходов и функцию выходов в неявном виде. Поведение автомата описывается в терминах входных и выходных последовательностей, реализуемых оператором, или последовательностей управляющих сигналов, воздействующих на управляющий автомат.
Для описания функционирования абстрактных ЦА на начальном языке можно использовать:
Язык регулярных выражений алгебры событий;
Язык исчисления предикатов;
Язык логических схем алгоритмов (ЛСА);
Язык граф схем алгоритмов (ГСА).
Язык ГСА совместно с языком ЛСА называют одним общим термином: язык операторных схем алгоритмов (ОСА). На практике наиболее часто используется язык ГСА.
3.3.1 Задание цифровых автоматов на стандартных
языках
Стандартные или автоматные языки
задают функции переходов выходов в явном виде. К ним относятся таблицы, графы, матрицы переходов и выходов и их аналитическая интерпретация. Для того, чтобы задать автомат, необходимо описать все компоненты вектора
S =
(A, Z, W, d, l, a
1).
При табличном способе задания
автомат Мили описывается с помощью двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов задает функцию d
(табл.3.4.), таблица выходов функцию - l
(табл.3.5.). Каждому столбцу табл.3.4 и 3.5 поставлено в соответствие одно состояние из множества А
, каждой строке – один входной сигнал из множества Z
. На пересечении столбца a m
и строки z f
в табл.3.4 записывается состояние
a s
, в которое должен перейти автомат из состояния a m
, под действием входного сигнала z f
, т.е. a s = d
(a m , z f
).
На пересечении столбца a m
и строки z f
в табл.3.5 записывается выходной сигнал w g
, выдаваемый автоматом в состоянии a m
при поступлении на его вход сигнала z f
, т.е.
w g = l
(a m , z f
).
Таблица 3.4 Таблица 3.5
| Таблица переходов автомата Мили | Таблица выходов автомата Мили | |||||||||
| a 1 | a 2 | a 3 | a 4 | a 1 | a 2 | a 3 | a 4 | |||
| z 1 | a 2 | a 2 | a 1 | a 1 | z 1 | w 1 | w 1 | w 2 | w 4 | |
| z 2 | a 4 | a 3 | a 4 | a 3 | z 2 | w 5 | w 3 | w 4 | w 5 |
Для указанных таблиц А =
{ a
1 , a
2 , a
3 , a
4 }; Z =
{ z
1 , z
2 };
W =
{w
1 , w
2 , w
3 , w
4 , w
5 }.
Автомат Мили может быть задан также одной совмещенной таблицей переходов и выходов (табл.3.6), в которой каждый элемент a s /w g , записанный на пересечении столбца a m и строки z f , определяется следующим образом:
a s = d (a m , z f ); w g = l (a m , z f ).
Автомат Мура задается одной отмеченной таблицей переходов (табл.3.7), в которой каждому столбцу приписаны не только состояния a m
, но еще и выходной сигнал w g
, соответствующий этому состоянию, где w g = l
(a m
). Для табл. 3.7 A =
{a
4 , a
2 , a
3 , a
4 }; Z =
{z
1 , z
2 };
W =
{w
1 , w
2 , w
3 }.
Одним из преимуществ этого способа задания является то, что любая таблица переходов и выходов задает конечный автомат. При этом должны удовлетворяться два условия:
Условие однозначности (детерминированности), которое означает, что для любой пары a m z f задано единственное состояние перехода a s и единственный выходной сигнал w g , выдаваемый на переходе.
Условие полной определенности , которое означает, что для всех возможных пар a m z f всегда указано состояние и выходной сигнал.
Таблица 3.6 Таблица 3.7
| Совмещенная таблица переходов и выходов автомата Мили | Отмеченная таблица переходов и выходов автомата Мура | |||||||||
| a 1 | a 2 | a 3 | a 4 | w 3 | w 2 | w 3 | w 1 | |||
| z 1 | a 2 /w 1 | a 2 /w 1 | a 1 /w 2 | a 1 /w 4 | a 1 | a 2 | a 3 | a 4 | ||
| z 2 | a 4 /w 5 | a 3 /w 3 | a 4 /w 4 | a 3 /w 5 | z 1 | a 1 | a 3 | a 1 | a 4 | |
| z 2 | a 2 | a 4 | a 4 | a 1 |
Автомат называется неполностью определенным или частичным , если либо функция d определена не на всех парах (a m z f ) Î A x Z , либо функция l определена не на всех указанных парах в случае автомата Мили и на множестве не всех внутренних состояний для автомата Мура. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте неопределенных состояний и выходных сигналов ставится прочерк.
Граф автомата – это ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Дуга, направленная из вершины a m в вершину a s , задает переход в автомате из состояния a m в состояние a s . В начале этой дуги записывается входной сигнал z f Î Z , вызывающий данный переход: a s = d (a m , z f ). Для графа автомата Мили выходной сигнал w g Î W , формируемый на переходе, записывается в конце дуги, а для автомата Мура рядом с вершиной, отмеченной состоянием a m , в котором он формируется. Если переход в автомате из состояния a m в состояние a s производится под действием нескольких входных сигналов, то дуге графа, направленной из a m в a s , приписываются все эти входные и соответствующие выходные сигналы. Графы автоматов Мили и Мура, построенные по табл.3.6 и 3.7 приведены соответственно на рис.3.7. а, б.
Применительно к графу условия однозначности и полной определенности будут заключены в следующем:
Не существует двух ребер с одинаковыми входными пометками, выходящих из одной и той же вершины;
Для всякой вершины a m и для всякого входного сигнала z f имеется такое ребро, помеченное символом z f , которое выходит из a m .
Рис.3.7. Графы автоматов: a – Мили; б – Мура
При задании графов с большим числом состояний и переходов наглядность теряется, поэтому оказывается предпочтительным задавать этот граф в виде списка – таблицы переходов.
Прямая таблица переходов – таблица, в которой последовательно перечисляются все переходы сначала из первого состояния, затем из второго и т.д. Табл.3.8 – прямая таблица переходов автомата Мили, построенная по графу, приведенному на рис.3.7.а.
В ряде случаев оказывается удобным пользоваться обратной таблицей переходов, в которой столбцы обозначены точно так же, но сначала записываются все переходы в первое состояние, затем во второе и т.д. Табл.3.9 – обратная таблица переходов автомата Мили, построенная по графу, приведенному на рис.3.7,а.
Как и граф таблицы переходов должны удовлетворять условиям однозначности и полноты переходов.
| Таблица 3.8 Прямая таблица переходов автомата Мили | Таблица 3.9 Обратная таблица переходов автомата Мили | |||||||
| a m (t ) | z f (t ) | a s (t+ 1) | w g (t ) | a m (t ) | z f (t ) | a s (t+ 1) | w g (t ) | |
| a 1 | z 1 | a 2 | w 1 | a 3 | z 1 | a 1 | w 2 | |
| z 2 | a 4 | w 5 | a 4 | z 1 | w 4 | |||
| a 2 | z 1 | a 2 | w 1 | a 1 | z 1 | a 2 | w 1 | |
| z 2 | a 3 | w 3 | a 2 | z 1 | w 1 | |||
| a 3 | z 1 | a 1 | w 2 | a 2 | z 2 | a 3 | w 3 | |
| z 2 | a 4 | w 4 | a 4 | z 2 | w 5 | |||
| a 4 | z 1 | a 1 | w 4 | a 1 | z 2 | a 4 | w 5 | |
| z 2 | a 3 | w 5 | a 3 | z 2 | w 4 |
Прямая таблица переходов автомата Мура строится так же как и для автомата Мили. Разница лишь в том, что выходной сигнал w g (t ) приписывается состоянию автомата a m (t ) (табл. 3.10), либо выходной сигнал w g (t a s (t+ 1) (табл. 3.11).
Обратная таблица переходов автомата Мура строится так же как и для автомата Мили. Разница лишь в том, что выходной сигнал w g (t +1) приписывается состоянию автомата a s (t+ 1) (табл. 3.12).
В некоторых случаях для задания автомата используются матрицы переходов и выходов , которые представляют собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из a m под действием z f в a s с выдачей w g , то на пересечении строки a m и столбца a s записывается пара z f w g . Ясно, что не всякая матрица задает автомат. Как граф и таблица переходов и выходов она должна удовлетворять условиям однозначности и полноты переходов.
| Таблица 3.10 Прямая таблица переходов автомата Мура Вариант 1 | Таблица 3.11 Прямая таблица переходов автомата Мура Вариант 2 | |||||||
| a m (t ) | w g (t ) | z f (t ) | a s (t+ 1) | a m (t ) | z f (t ) | a s (t+ 1) | w g (t +1) | |
| a 1 | w 3 | z 1 | a 1 | a 1 | z 1 | a 1 | w 3 | |
| z 2 | a 2 | z 2 | a 2 | w 2 | ||||
| a 2 | w 2 | z 1 | a 3 | a 2 | z 1 | a 3 | w 3 | |
| z 2 | a 4 | z 2 | a 4 | w 1 | ||||
| a 3 | w 3 | z 1 | a 1 | a 3 | z 1 | a 1 | w 3 | |
| z 2 | a 4 | z 2 | a 4 | w 1 | ||||
| a 4 | w 1 | z 1 | a 4 | a 4 | z 1 | a 4 | w 1 | |
| z 2 | a 1 | z 2 | a 1 | w 3 |
| Таблица 3.12 Обратная таблица переходов автомата Мура Вариант 2 | |||
| a m (t ) | z f (t ) | a s (t+ 1) | w g (t +1) |
| a 1 | z 1 | a 1 | w 3 |
| a 3 | z 1 | ||
| a 4 | z 2 | ||
| a 1 | z 2 | a 2 | w 2 |
| a 2 | z 1 | a 3 | w 3 |
| a 2 | z 2 | a 4 | w 1 |
| a 3 | z 2 | ||
| a 4 | z 1 |
Системы канонических уравнений (СКУ) и системы выходных функций (СВФ) являются аналитической интерпретацией таблиц переходов и выходов или графов автоматов. СКУ – определяет функции переходов ЦА, а СВФ – определяет функции выходов ЦА.
Каждое состояние ЦА интерпретируется как событие, соответствующее множеству переходов в это состояние:
Для сокращения записи СКУ и СВФ будем в дальнейшем везде, где это возможно, опускать знаки конъюнкции и времени t в правой части уравнений типа (3.10).
Для автомата Мили, заданного табл.3.8 или табл. 3.9 запишем СКУ и СВФ (3.811и 3.12. соответственно):
| a 1 (t +1) = z 1 a 3 Ú z 1 a 4 ; a 2 (t +1) = z 1 a 1 Ú z 1 a 2 ; a 3 (t +1) = z 2 a 2 Ú z 2 a 4 ; a 4 (t +1) = z 2 a 1 Ú z 2 a 3 . | (3.11) | w 1 (t ) = z 1 a 1 Ú z 1 a 2 ; w 2 (t ) = z 1 a 3 ; w 3 (t ) = z 2 a 2 ; w 4 (t ) = z 1 a 4 Ú z 2 a 3; w 5 (t ) = z 2 a 1 Ú z 2 a 4. | (3.12) |
Запишем СКУ и СВФ для автомата Мура, заданного табл. 3.10 - 3.12, (3.13 и 3.14 соответственно).
Баранов Виктор Павлович. Дискретная математика. Раздел 6. Конечные автоматы
и формальные языки.
Лекция 31. Определение и способы задания конечного автомата. Задача синтеза. Элементарные автом а ты
Лекция 30. ОПРЕДЕЛЕНИЕ И СПОСОБЫ ЗАДАНИЯ КОНЕЧНОГО АВТОМАТА.
ЗАДАЧА СИНТЕЗА. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ
План лекции:
1. Определение конечного автомата.
2. Способы задания конечного автомата.
СФЭ не учитывают тот факт, что реальные устройства работают во времени. По сравнению с СФЭ конечный автомат является более точной моделью дискретного прео б разователя информации. При этом понятие конечного автомата, как и любая модель, св я зано с рядом упрощающих предположений.
Во-первых, предполагается, что вход и выход автомата в каждый момент времени может находиться только в одном из конечного числа различных состояний. Если реал ь ный преобразователь имеет непрерывный входной сигнал, то для его описания с помощью конечного автомата необходимо провести квантование этого сигнала. В формальном определении автомата конечный набор состояний входа и выхода автомата называется соо т ветственно входным и выходным алфавитом , а отдельные состояния буквами этих алф а витов.
Во-вторых, предполагается, что время изменяется дискретно. Состояния входа и выхода соответствуют дискретной временной последовательности Поскол ь ку момент времени однозначно определяется его индексом, то с целью упрощения будем считать, что время принимает значения 1, 2, …, … Временной промежуток называется тактом .
Работа автомата представляется следующим образом.
На вход автомата поступают сигналы из входного алфавита, что приводит к появлению сигналов на выходе из входного алфавита. З а висимость выходной последовательности от входной зависит от внутреннего устройства автомата. Заметим, что в отличие от СФЭ, которые не обладают памятью, автомат пре д ставляет собой устройство с памятью, т. е. выход автомата определяется не тол ь ко входом, но и предысторией. Учет предыстории осуществл я ется зависимостью выходного сигнала не только от входа, но и от текущего состояния, которое обозначим.
Дадим формальное определение автомата.
Конечным автоматом называют пятерку объектов
, (1)
где
входным алфавитом ; одно из возможных состояний входа;
конечное множество, называемое выходным алфавитом ; элеме н ты этого множества определяют возможные состояния выхода;
конечное множество, называемое алфавитом внутренних состо я ний ;
функция переходов автомата: ; эта функция каждой паре «вход-состояние» ставит в соответствие состояние;
функция выходов автомата: ; эта функция каждой паре «вход-состояние» ставит в соответствие значение выхода.
Закон функционирования автомата: автомат изменяет свои состояния в соотве т ствии с функцией и вырабатывает выходные сигналы в соответствии с фун к цией:
1 . Табличный способ задания. Поскольку для функций и области определ е ния и значений принадлежат конечному множеству, то их задают при помощи таблиц.
Пример 1. Зададим автомат следующим образом: , .Функцию определим с помощью таблицы переходов, а функцию с помощью таблицы выходов .
Таблица 1. Таблица переходов Таблица 2. Таблица выходов
|
Вход |
Состояние |
||
|
Вход |
Состояние |
||
Если известна последовательность сигналов на входе автомата, то таблицами пер е ходов и выходов однозначно определяется выходная последовательность.
2 . Графический способ задания. Используется диаграмма переходов-выходов. Она представляет собой ориентированный мультиграф, в котором каждому вну т реннему состоянию автомата соответствует вершина. Переходы автомата из состояния в состояние изображаются стрелками, на каждой из которых пишутся входной символ, в ы зывающий данный переход, и выходной символ, вырабатываемый автоматом.
| | |
Рис.1 Диаграмма переходов-выходов
Пример 2. Требуется построить автомат, который работал бы следующим обр а зом: в каждый такт на вход автомата поступают очередные двоичные разряды слагаемых, а в томат вырабатывает соответствующий двоичный разряд их суммы. Для двухра з рядных слагаемых имеем: , .
Автомат находится в состоянии 1, если при сложении предыдущих разрядов возн и кает перенос, и в состоянии 0 в противном случае. Диаграмма переходов-выходов пок а зана на рис. 2.
00|0 11|1 01|0
01|1 10|0
10|1 00|1 11|1
Рис. 2
По аналогии с задачей синтеза СФЭ можно поставить задачу синтеза для автом а тов. Имеется неограниченный набор базисных автоматов. Требуется собрать автомат с наперед заданным функционированием. При этом задача синтеза сталкивае т ся с определенными проблемами.
Допустим, что нужно присоединить выход автомата к входу автомата. Это возможно при условии, так как иначе вт о рой автомат не поймет сигналы, поступающие с первого. Это приводит к запутанной с и туации, когда некоторые соединения невозможны.
Чтобы преодолеть это препятствие, вводится понятие структурного автомата, в к о тором все алфавиты (входной, выходной и внутренних состояний) кодируются двоичными словами.
Пусть конечное множество из элементов, а множ е ство двоичных слов длины, где. Произвольное инъективное отображение будем называть кодированием множества двоичными словами.
Произведем кодирование алфавитов для произвольного автомата:
Обозначим закодированные вход, выход и состояние автомата в момент времени соответственно. Тогда закон функционирования представится в виде
(2)
Полученный после кодирования автомат называют структурным . Будем считать, что структурный автомат имеет двоичных входов, двоичных выходов, а внутреннее состояние автомата задается двоичным словом длины. На рис. 3 показан абстрактный автомат и соответствующий ему структурный автомат.
… …
Рис. 3
Переход к структурному автомату обеспечивает два важных для синтеза преимущ е ства.
1 . Совместимость входов и выходов, так как через них передается двоичная и н формация. Мы не будем давать общее определение схемы из структурных автоматов оно аналогично СФЭ.
2 . Запишем соотношения (2) в «координатах»:
(3)
Из (3) следует, что закон функционирования структурного автомата задается с и стемой булевых функций .
Выделим простейшие структурные автоматы и дадим им название.
Отметим сначала, что функциональный элемент, имеющий только одно состояние, можно рассматривать как автомат без памяти.
Перейдем к автоматам с двумя состояниями. Пусть автомат имеет один двоичный вход и один двоичный выход, совпадающий с внутренним состоянием: :
Рис. 4.
Для задания автомата, показанного на рис. 4, достаточно задать только таблицу п е реходов:
Таблица 3
|
Вход |
Состояние |
|
Вместо звездочек нужно поставить 0 и 1. Это можно сделать 16 способами, однако, не все они приемлемы. Допустим, например, что в первом столбце таблицы 3 оба элеме н ты нули. Такой автомат, оказавшись в состоянии 0, более из него не выйдет, то есть будет работать как функциональный элемент. Анализ аналогичный ситуаций показывает, что для того чтобы получился автомат, не сводящийся к автомату без памяти, надо потреб о вать, чтобы в каждом столбце таблицы 3 встречались и ноль и единица. Таких таблиц вс е го ч е тыре.
Таблица 4 Таблица 5
|
Вход |
Состояние |
|||||
|
Вход |
Состояние |
|||||
Таблица 6 Таблица 7
|
Вход |
Состояние |
|
|
Вход |
Состояние |
|
Имеем только два простейших автомата, так как 7 получается из 4, а 6 из 5 путем инверсии внутренних состояний.
Автомат, задаваемый таблицей 4, называется задержкой или -триггером :
то есть этот автомат задерживает сигнал на один такт.
Автомат, задаваемый таблицей 5, называется триггером со счетным входом или -триггером . Состояние автомата меняется на противоположное, если на вход поступает 1, и остается без изменения, если на вход поступает 0:
Пусть в начальный момент времени - триггер находится в состоянии 0. Если в н е который момент времени - триггер находится в состоянии 0, то это означает, что на вход автомата поступило четное число единиц. Если в состоянии 1, то нечетное. Таким обр а зом, - триггер считает количество единиц на входе, но так как он имеет всего два состо я ния, то и считает до двух.
При физической реализации триггеров используют два выхода: прямой и инвер с ный (рис. 5). Если поменять их местами, то из - триггера получится автомат, задаваемый таблицей 7, а из - триггера автомат, задаваемый таблицей 6.
Рис. 5.
Набор структурных автоматов называется полным (или автоматным б а зисом), если из них можно построить любой наперед заданный структурный автомат.
Усилия математиков для получения аналога теоремы Поста для автоматов не уве н чались успехом. В 1964 г. М.И. Кратко доказал несуществование алгоритма для определ е ния полноты системы. В этом случае представляют интерес варианты теоремы о полноте с дополнительными предположениями о системе. Рассмотрим наиболее популярный из них.
Теорема. Система автоматов, содержащая полный набор ФЭ и - триггер (или -триггер) является полной.
Доказательство. Рассмотрим произвольный автомат, заданный соотнош е ниями (2), и опишем его схему из указанных автоматов, называемую канонической структурой (рис. 6) .
Схема состоит из двух частей.
…
…
…
Рис. 6.
Левая половина называется запоминающей частью. Она состоит из триггеров, набор состояний которых образует состояние автомата: если в момент времени
, …,
то это означает, что автомат находится в состоянии.
Правая половина называется комбинационной частью и представляет СФЭ. Входы этой схемы:
Выходы:
Покажем, что сигналы управления памятью являются булевыми функциями от тех же переменных, что и выход автомата, а, значит, они могут быть реализованы полной с и стемой ФЭ.
В каждый момент времени сигналы управления памятью должны переводить а в томат из состояния в состояние. Для этого надо изменить состояние каждого триггера
, .
Используемые в канонической схеме -триггеры или -триггеры обладают сл е дующим свойством: для любой пары состояний существует входной сигнал, пер е водящий автомат из состояния в состояние. Обозначим этот сигнал через. Для -триггера, так как состояние, в которое устанавливается -триггер, равно входному сигналу. Для -триггера: при на вход надо п о дать 0, чтобы состояние не изменилось; при 1, чтобы триггер «перевернулся».
Итак, или в векторной форме
Выразим из закона функционирования автомата (2). Тогда
Теорема доказана.
Рассмотрим этот метод на конкретном примере.
Пример. На конвейере, по которому двигаются детали двух типов и, устано в лен автомат, задачей которого является такая сортировка деталей, чтобы после прохожд е ния мимо автомата они образовывали группы. Неподходящую деталь автомат ста л кивает с конвейера. Требуется построить схему такого автомата, используя -триггер и элементы «И», «ИЛИ», «НЕ».
Синтез автомата разбивается на следующие этапы.
1 . Построение абстрактного автомата.
Входной алфавит . Выходной алфавит , где С сталкив а ние детали, П ее пропуск. Внутренние состояния автомата отражают его память о том, какую часть группы он уже сформировал: . По мере формирования группы автомат циклически перемещается по этим состояниям, не изменяя состояния при поступлении неподходящей детали. Диаграмма переходов-выходов показана на рис. 7.
| | |
Рис. 7.
2 . Кодирование алфавитов.
Один из возможных вариантов кодирования приведен в сл е дующих таблицах.
Вход Выход Состояние
3 . Построение канонической структуры автомата.
Каноническая структура разрабатываемого автомата показана на рис. 8.
Рис. 8.
Найдем зависимости выходов СФЭ, от переменных сначала в табличном виде (таблица 8), по к о торым далее построим формулы
, .
Таблица 8
Эти функции называются частично определенными , так как они не определены при. Для представления этих функций формулами их доопределяют таким образом, чтобы получить более простой вид формул.
4 . Представление функций выхода автомата и функций управления памятью фо р мулами.
Используя методы минимизации булевых функций, строим по возможности эк о номное представление функций, формулами в базисе:
5 . Реализация СФЭ и окончательная схема автомата (рис. 9).
Рис. 9.
СФЭ
СФЭ
НЕ
ИЛИ
Для описания конечных цифровых автоматов можно использовать стандартные (автоматные) языки и начальные языки.
Стандартные или автоматные языки описания.
Они описывают функции переходов и выходов в явном виде, а именно в виде:
Таблиц переходов и выходов;
Из определения автомата следует, что его всегда можно задать таблицей с двумя входами, содержащей m строк и n столбцов, где на пересечении столбца q(состояния автомата) и строки а (входные сигналы) стоят значения функций φ(l) (a i ,q j) (функция переходов); \|/ (m )(a i ,q j)(функция выходов).
Таблица 1
2) графа, представляющего наглядно функции l и m ..
Другой способ задания конечного автомата - графический. При этом способе состояния автомата изображают кружками, в которые вписывают символы состояний q j (j= 1,..., п). Из каждого кружка проводится m стрелок
(ориентированных рёбер) взаимно-однозначно соответствующих символам входного алфавита X(V). Стрелке, соответствующейбукве а i X и выходящей из кружка q j Q(S), приписывается пара (а i , \|/ (a i ,q j) , причем эта стрелка ведет в кружок, соответствующий φ (a i ,q j)
Полученный рисунок называется графом автомата или, диаграммой Мура. Для не очень сложных автоматов этот способ более нагляден, чем табличный.
Автомат Мура
Абстрактный автомат Мура это частный случай автомата Мили (4), когда выходной символ зависти только от состояния автомата, а именно функция выходов автомата Мура:
w =m (s ) (5)
Для каждого автомата Мили можно построить эквивалентный автомат Мура, реализующий точно такой же алфавитный оператор. Пусть A = <V,W,S,l,m,s (0)> автомат Мили. В качестве состояний эквивалентного автомата Мура возьмем пары . Тогда функция выходов эквивалентного автомата Мура
а функция переходов
Задание конечного автомата системой булевых функций
Третий способ задания конечного автомата А = (X;Q;Y; φ ;\|/), заданного таблицей или диаграммой Мура, состоит в определении системы булевых функций.
X-входной алфавит;
Q-множество состояний автомата;
Y-выходной алфавит;
φ -функция перехода;
\|/-функция выходов.
Изложим алгоритм этого способа задания.
1.Находим числа k, r, s,
удовлетворяющие условиям 2 k -1 < т
< 2 k ;
2 r
- 1 < п ≤ 2 r ;
2 s - 1
Очевидно, что k,r, s соответственно равны числу разрядов в двоичном представлении чисел т, п, р. Например, если т - 5, п = 17, р = 3, то k= 3, r= 5,s = 2.
2. Кодирование состояний входных и выходных символов исходного
автомата.
Каждому q j Q взаимно-однозначно ставим в соответствие двоичную последовательность длины r - двоичный код = z 1 z 2 z r . Аналогично каждому а i X и b k Y ставим взаимно однозначно в соответствие двоичные последовательности =x 1 x 2 x k ; =y 1 y 2 y s .
Отметим, что кодирование состояний, входных и выходных символов можно провести многими способами. При этом некоторые последовательности (коды) могут оказаться неиспользованными.
| . |
3.Составляем следующую таблицу:
Эта таблица содержит k + r + r + s столбцов и 2 k + r строк. В первых k + r столбцах выписаны все наборы длины k + r. Каждый такой набор соответствует паре (), где -возможный код некоторого состояния, код входного символа.
4.Заполнение последних столбцов в таблице (предыдущий шаг).
Для каждой пары (a i ,q j), где а i X; q j Q, находим код и . По таблице автомата (или диаграмме Мура) определяем и \|/(а; q) = Y. Затем находим код = " 1 " 2 ... ",. и код .
В строку таблицы соответствующую набору
дописываем набор
5. Определение системы булевых функций.
После выполнения предыдущего шага может оказаться, что все строки в таблице заполнены. Это произойдет в том случае, если хотя б одно из чисел m, n не является степенью 2. Таким образом, функции окажутся не полностью определенными – на некоторых наборах их значения не определены. Тогда мы их доопределяем произвольным образом. Как правило, доопределение функций проводят так, чтобы получившиеся полностью определенные функции удовлетворяли тем или иным условиям оптимальности, например представлялись минимальными ДНФ.
После выполнения этого шага исходный автомат будет задавать системой полностью определенных булевых функций
3.2 Начальные языки .
Они описывают автомат на поведенческом уровне. К начальным языкам относятся:
1) языки логических схем и граф схем алгоритмов;
2) язык регулярных выражений алгебры событий;
3) формальные и автоматные грамматики.
Если задано описание (4) полностью определенного автомата в стандартной форме, то для любого начального состояния автомата s (0) и последовательности входных символов v (0)v (1)v (2)…v (t ) можно вычислить реакцию автомата в виде последовательности выходных символов w (0)w (1)…w (t ).
Примеры.
Пример 1 . Автомат ПРОДАВЕЦ газет получает монеты достоинством в 1 рубль и 2 рубля. Если сумма монет равна 3 рублям, то автомат выдает газету. Если сумма больше 3 рублей, то автомат возвращает все деньги. Введем обозначения входных и выходных символов и состояний автомата.
Входные символы:
v 1 - опущена монета достоинством 1 рубль;
v 2 - опущена монета достоинством 2 рубля.
Выходные символы:
w 1 - сообщение "Принята сумма 1 руб.";
w 2 - сообщение "Принята сумма 2 руб.";
w 3 - выдача газеты;
w 4 - возврат денег.
Состояния автомата:
s 0 - принята сумма 0 руб. (начальное состояние);
s 1 - принята сумма 1 руб.;
s 2 - принята сумма 2 руб.
Функцию переходов представим таблицей 2, а функцию выходов - таблицей 3.
Этот же автомат можно задать в виде отмеченного орграфа, вершины которого соответствуют состояниям автомата, а дуги - переходам (рис.3).
|
Ниже приведен пример реакции автомата ПРОДАВЕЦ на входную последовательность v 1 v 1 v 2 v 2 v 1 v 2 v 2 v 1 v 1 v 1 …:
| t | … | |||||||||||
| v(t) | … | v 1 | v 1 | v 2 | v 2 | v 1 | v 2 | v 2 | v 1 | v 1 | v 1 | … |
| s(t) | … | s 0 | s 1 | s 2 | s 0 | s 2 | s 0 | s 2 | s 0 | s 1 | s 2 | s 0 |
| w(t) | … | w 1 | w 2 | w 4 | w 2 | w 3 | w 2 | w 4 | w 1 | w 2 | w 3 | … |
Пример 2. Для рассмотренного выше автомата ПРОДАВЕЦ можно построить эквивалентный автомат Мура, характеризуемый таблицей переходов/выходов (табл 4).
Таблица 4
| Новое состояние | |
| Входной символ | Текущее состояние/выходной символ |
| v 1 v 2 | s 1 v 1 s 2 v 1 s 2 v 1 s 0 v 1 s 0 v 1 s 0 v 1 s 1 v 2 s 2 v 2 s 2 v 2 s 0 v 2 s 0 v 2 s 0 v 2 |
На рис.4 представлен граф переходов/выходов автомата ПРОДАВЕЦ, соответствующий табл.4. Начальное состояние эквивалентного автомата Мура включает входной символ v (0). Поэтому приходится смещать поток входных символов: .
| t | … | ||||||||||
| … | v 1 | v 2 | v 2 | v 1 | v 2 | v 2 | v 1 | v 1 | v 1 | … | |
| … | s 01 | s 11 | s 12 | s 02 | s 21 | s 02 | s 22 | s 01 | s 11 | s 21 | |
| w(t) | … | w 1 | w 2 | w 4 | w 2 | w 3 | w 2 | w 4 | w 1 | w 2 | … |
Опишем поведение родителя, отправившего сына в школу. Сын приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит очередную двойку, и выбирает более тонкую тактику воспитания. Задавать автомат удобно графом, в котором вершины соответствуют состояниям, а ребро из состояния s в состояние q, помеченное х/у, проводится тогда, когда автомат из состояния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией у. Граф автомата, моделирующего умное поведение родителя, представлен на рис. 5.
Рис. 5. Автомат, описывающий поведение «умного» отца
Этот автомат имеет четыре состояния {s0, s1, s2, s3} и два входных сигнала - оценки, полученные сыном в школе: {2,5}. Начиная с начального состояния s0(оно помечено входной стрелкой), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы - реакции на входы. Выходы автомата {у0,..., у5} будем интерпретировать как действия родителя так:
y0: - брать ремень;
yl: - ругать сына;
у2: - успокаивать сына;
уЗ: - надеяться;.
у4: - радоваться;
у5: - ликовать.
Сына, получившего одну и ту же оценку - двойку, ожидает дома совершенно различная реакция отца в зависимости от предыстории его учебы. Отец помнит, как его сын учился раньше, и строит свое воспитание с учетом его предыдущих успехов и неудач. Например, после третьей двойки в истории 2,2, 2 сына встретят ремнем, а в истории 2, 2, 5, 2 - будут успокаивать. Каждая предыстория определяет текущее состояние автомата, при этом некоторые входные предыстории эквивалентны (именно те, которые приводят автомат в одно и то же состояние): история 2, 2, 5 эквивалентна пустой истории, которой соответствует начальное состояние.
Текущее состояние автомата представляет все то, что автомат знает о прошлом с точки зрения его будущего поведения - реакций на последующие входы. Эта история в концентрированном виде определена текущим состоянием, и все будущее поведение автомата, как реакция его на последующие входные сигналы, определено именно текущим состоянием, но не тем, как автомат пришел в него.
Итак, конечный автомат - это устройство, работающее в дискретные моменты времени (такты). На вход конечного автомата в каждом такте поступает один из возможных входных сигналов, а на его выходе появляется выходной сигнал, являющийся функцией его текущего состояния и поступившего входного сигнала. Внутреннее состояние автомата также меняется. Моменты срабатывания (такты) определяются либо принудительно тактирующими синхросигналами, либо асинхронно, наступлением внешнего события - прихода сигнала.
Определим конечный автомат формально.
Кроме графического представления для автомата можно использовать и табличное, задавая функции переходов и выходов в виде таблиц. Автомат примера будет представлен следующими таблицами.
Таблица 5, а определяет функцию переходов так:
а табл. 5, б определяет функцию выходов : .(s0, 2) = у2; (s2, 5) = у3; ....
ПЛАН ЛЕКЦИИ
1. Табличный способ
2. Графический способ задания автомата
Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d , l } , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l . При этом среди множества A = {a 0 ,a 1 ,…, a n } необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.
При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.
Таблица переходов
|
x j \a j |
|||
|
d (a 0 ,x 1) |
d (a n ,x 1) |
||
|
x m |
d (a 0 ,x m) |
d (a n ,x m ) |
Таблица выходов
|
x j \a j |
|||
|
l (a 0 ,x 1) |
l (a n ,x 1) |
||
|
x m |
l (a 0 ,x m) |
l (a n ,x m ) |
Строки этих таблиц соответствуют входным сигналам x (t ), а столбцы – состояниям. На пересечении столбца a i и строки x j в таблице переходов ставится состояние a s = d [ a i ,x j ], в которое автомат перейдет из состояния a i под воздействием сигнала x j ; а в таблице выходов – соответствующий этому переходу выходной сигнал y g = l [ a i ,x j ].
Совмещенная таблица переходов и выходов автомата Мили:
|
x j \a i |
|||
|
d (a 0 ,x 1)/ l (a 0 ,x 1) |
d (a n ,x 1)/ l (a n ,x 1) |
||
|
x m |
d (a 0 ,x m)/ l (a 0 ,x m) |
d (a n ,x m )/ l (a n ,x m ) |
Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но и также все три алфавита: входной, выходной и алфавит состояний.
Для задания автомата Мура требуется одна таблица, поскольку в этом автомате выходной сигнал однозначно определяется состоянием автомата.
|
y g |
l (a 0) |
l (a n) |
|
|
x j \a c |
|||
|
d (a 0 ,x 1) |
d (a n ,x 1) |
||
|
x m |
d (a 0 ,x m) |
d (a n ,x m ) |
Автомат Мили
|
x j \a i |
||||
|
a 1 /y 1 |
a 2 /y 3 |
А 3 /y 2 |
a 0 /y 1 |
|
|
a 0 /y 2 |
a 0 /y 1 |
A 3 /y 1 |
a 2 /y 3 |
Автомат Мура
|
x j \x j |
|||||
В этой таблице каждому столбцу приписан, кроме состояния a i , еще и выходной сигнал y (t ) = l (a (t )), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.
Приведем примеры табличного задания автоматов Мили и Мура :
По этим таблицам можно найти реакцию автомата на любое входное слово. Например.
Для автомата Мили:Для автомата Мура :
x 1 x 2 x 2 x 2 x 1 …x 1 x 2 x 2 x 2 x 1 …
a 0 a 1 a 0 a 0 a 0 a 1 a 0 a 2 a 4 a 1 a 4
y 1 y 1 y 2 y 2 y 1 y 2 y 1 y 2 y 1 y 2
2. Графический способ задания автомата (задание автомата с помощью графа)
Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a i и a s соединяются дугой, направленной от a i к a s , если в автомате имеется переход из a i в a s , т.е. a s =d (a i , x j ). В автомате Мили дуга отмечается входным сигналом x j , вызвавшим переход, и выходным сигналом y g , который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).
