Дискретная математика (стр. 11 )

Определение. Абстрактным конечным автоматом называется шестерка объектов

,

где – конечное непустое множество состояний;

– начальное состояние;

– конечное непустое множество входных сигналов;

– множество выходных сигналов;

– функция переходов;

– функция выходов.

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

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

4.1.2. Автоматы Мили и Мура

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

где – длительность такта.

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

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

4.1.3. Способы задания конечных автоматов

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

В [1] приведен пример автомата, описывающего поведение отца, отправившего сына в школу. Сын приносит двойки и пятерки. Но отец не наказывает сына за каждую двойку. Он понимает, что она может быть и случайной, поэтому выбрана более гибкая тактика, которая описывается автоматом, граф которого представлен на рис. 4.1.

Рис. 4.1. Автомат, описывающий поведение отца,
отправившего сына в школу

Автомат имеет четыре состояния и два входных сигнала – оценки, получаемые сыном в школе: {2,5}. Начиная с начального состояния (оно помечено входной стрелкой), автомат под действием входных сигналов переходит из одного состояния в другое и формирует выходные сигналы – реакции на входы. Выходы автомата будем интерпретировать как действия отца следующим образом: – брать ремень; – ругать сына; – успокаивать сына; – надеяться; – радоваться; – ликовать.

Сына, получившего двойку, ожидает дома совершенно разная реакция отца, в зависимости от предыстории его учебы. Отец помнит предысторию учебы сына и строит свое поведение с учетом этой предыстории. Например, после третьей двойки во входной истории 2,2,2 сына встретят ремнем, а в истории 2,2,5,2 – будут успокаивать. Каждая предыстория определяет текущее состояние автомата (отца), при этом некоторые предыстории эквивалентны (те, что приводят автомат в одно и то же состояние). История 2,2,5 эквивалентна пустой истории. Текущее состояние автомата представляет все то, что автомат знает о прошлом с точки зрения его будущего поведения.

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

Кроме того, рассмотренный автомат является, очевидно, автоматом Мили, т. к. реакция зависит как от состояния отца, так и от полученной оценки.

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

Для рассмотренного примера матрица смежности задана табл. 4.1.

Таблица 4.1

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

Для автомата Мили таблица переходов в общем виде приведена ниже.

Таблица 4.2

Таблица выходов получается из таблицы переходов заменой функций на .

Табличное описание автомата Мура можно записать как табл. 4.3.

Таблица 4.3

Для рассмотренного примера, который представляет собой автомат Мили, таблицы переходов и выходов имеют вид табл. 4.4 и табл. 4.5.

Таблица 4.4

(5)
(2)

Таблица 4.5

(5)
(2)

4.1.4. Реализация конечных автоматов

Рассмотрим два вида реализации конечного автомата: программную и аппаратную.

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

Аппаратная реализация требует применения устройств памяти для запоминания текущего состояния автомата. Обычно на практике, используют двоичные элементы памяти. Функциональный блок автомата реализуется как конечный функциональный преобразователь. Таким образом, общий подход к аппаратной реализации конечного автомата совпадает с общей процедурой синтеза логических схем, описанной в разд. 2.3, и включает следующие шаги:

· входные и выходные сигналы и внутренние состояния автомата кодируются двоичными кодами;

· по таблицам переходов и выходов составляются кодированные таблицы переходов и выходов – фактически табличное задание отображений и ;

· по кодированным таблицам переходов и выходов формируются аналитические выражения логических функций и проводится их минимизация;

· полученные минимальные формы реализуются в заданном элементном базисе;

· решаются схемотехнические вопросы синхронизации – привязки моментов выдачи выходного сигнала и изменения состояния внутренней памяти к моментам поступления входных сигналов на вход автомата.

Рассмотрим реализацию автомата из рассмотренного примера. Входных сигналов два; мы их закодируем так: , . Выходных сигналов шесть. Закодируем их: , , …, . Внутренних состояний четыре. Закодируем их: , , , . Таким образом, имеем: , , . Структурная схема этого автомата после двоичного кодирования имеет вид, показанный на рис. 4.2, где – функциональный преобразователь без памяти, реализующий отображения и , БП – блок памяти.

Рис. 4.2. Структурная схема автомата

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

Таблица 4.6

0	0	0	0	1	0	1	0
0	0	1	1	0	0	0	1
0	1	0	1	0	0	0	0
0	1	1	0	1	0	1	0
1	0	0	1	1	1	0	0
1	0	1	0	0	0	1	1
1	1	0	0	0	0	1	1
1	1	1	1	1	1	0	1

После записи логической формулы и минимизации в классе ДНФ, как это рассмотрено в разд. 2.4, получим аналитические выражения для всех двоичных функций, реализация которых показана на рис. 4.3.