Элементы теории автоматов

48. Примеры конечных автоматов

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

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

Приведем несколько примеров конечных автоматов.

Диаграмма Мура изображена на рис. 7.3. (щ = 0; у(а! = 0; q_x = 0) = 0)

Пример I. Элемент задержки (элемент памяти).

Э

x(t)

М

y(t) = x(t - 1)

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

Рис. 7.2

Предположим, что входной и, следовательно, выходной алфавит есть X = {0,1}; Y = {0,1}. Тогда Q = {0,1}. Под состоянием элемента задерж­ки в момент времени t понимается содержание элемента памяти в данный момент. Таким образом q(t) = X(t — 1), a Y(t) = q(t) = X(t — 1).

З

9(ai;gi) = cp(0, О) = О; Ф(«1;Ы = ф(0,1) = О;

ф(а2;91> = ф(1,0)= 1;

ф(а2;д2) = ф(1Д) = 1;

ф(«ъ <Zi) = 9(0, 0) = 0; V(«b?2> = ф(0,1) = 1; ¥(«2,9i) = 9(1,0) = 0; V(«2,<Z2) = ¥(!>!) = 1,

ададим элемент задержки таблицей, где а\ = О, = 1, q\ = О, = 1,

	0	1
0	Ф = 0; ц/ = 0	Ф = 0; у = 1
1	о II Э- тН II э-	ф= 1; vj/= 1

Для представления этого автомата системой булевых функций ис­пользуем таблицу автомата и вышеизложенный алгоритм. При этом ко­дирование производить не нужно, так как входной и выходной алфавиты и состояния уже закодированы.

Обратим внимание на то, что т = п = р = 2. Тогда k = г = s = 1, и поэтому элемент задержки задается двумя функциями ф и у. Таблица

истинности этих функций содержит 2^к+г = 2² = 4 строки и/г + г + г + в = 4 столбца:

X	Z	ф	V
0	0	0	0
0	1	0	1
1	0	1	0
1	1	1	1

Пример 2. Двоичный сумматор последовательного действия.

Д

Xi = Xi(l)...Xi(f)

х₂ = х₂{1 )...x₂(t)

y(t+ l )...y(t)

Рис. 7.4

анный сумматор последовательного действия представляет собой устройство, осуществляющее сложение двух чисел в двоичной системе исчисления. На входы сумматора подаются числа Xi и х%, начиная с млад­ших разрядов. На выходе формируется последовательность, соответству­ющая записи числа Х\ + х% в двоичной системе исчисления (рис. 7.4).

Входной и выходной алфавиты определены однозначно: X = {00; 01; 10; 11}; У = {0, 1}. Множество состояний определяется значением пере­носа при сложении соответствующих разрядов чисел Х\ и х₂. Если при сложении некоторых разрядов образовался перенос, то будем считать, что сумматор перешел в состояние q\. При отсутствии переноса будем считать, что сумматор находится в состоянии до-

Сумматор задается таблицей.

	7о	gi
00	до; о	до; 1
01	до; 1	дв о
10	до; 1	дво
11	дв о	дв 1

Диаграмма Мура сумматора последовательного действия изображена на рис. 7.5.

З аметим, что входные и выходные символы уже закодированы. Со­стояния закодируем следующим образом: ос(до) ⁼ 0; a(gi) = 1. Поэтому

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

Х\	х2	2	ф	¥
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Пример 3. Схема сравнения на равенство.

Схема сравнения на равенство представляет собой устройство, срав­нивающее два числа Х\ и^, заданные в двоичной системе исчисления. Это устройство работает следующим образом. На вход устройства после­довательно, начиная со старших, подаются разряды чисел х\ и х%. Эти разряды сравниваются. При совпадении разрядов на выходе схемы фор­мируется выходной сигнал О, в противном случае на выходе появляется сигнал 1. Ясно, что появление 1 в выходной последовательности означа­ет, что сравниваемые числа Х\ и х^ различны. Если же выходная после­довательность является нулевой и ее длина совпадает с числом разрядов сравниваемых чисел, toxi = х₂.

Для этого автоматах = {00; 01; 10; 11}; Y = {0,1}.

Функционирование схемы определяется двумя состояниями. Состоя­ние qo соответствует равенству сравниваемых в данный момент разрядов. При этом автомат остается в этом же состоянии. Если в следующий мо­мент сравниваемые разряды будут различны, то автомат перейдет в новое состояние <7i и в нем остается. Так как это означает, что числа различны.

Таким образом, схему сравнения можно задать таблицей:

	<7о	qi
00	<7о; о	qi; i
01	?i; 1	qi; i
10	qw 1	9i; i
11	о о с?	qn г

Диаграмма Мура схемы сравнения на равенство изображена на рис. 7.6.

Рис. 7.6

Кодирование состояний произведем следующим образом: ос(уо) ⁼ 0; <7.(e/i) = 1. Автомат будет задаваться двумя функциями.

X]	x2	2	Ф	V
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	0	0
1	1	1	1	1

Пример 4. Схема сравнения на неравенство.

Схема сравнения на неравенство представляет собой устройство, по­зволяющее выяснить, равны ли сравниваемые Х\ и х₂, и если они не рав­ны, выяснить, какое из них больше другого. Это устройство имеет два входа и два выхода. Выходные сигналы yi(t) и у₂(1) определяются по сле­дующим правилам:

yi(t) = У At) = 0, если *i(f) = x₂(t);

У2(*) ⁼ О» если X\(t) > Х2(t); т. е. Xi(l) = 1; Xz(t) = О;

y

yi(t) = l; yi(t) = 0;

zit) = 1, если xy(t) < Xz(ty, т. е. Xi(£) = О; #г(0⁼1-

Таким образом, при подаче на вход схемы сравнения на неравенство чисел Х\ = xi(l)...xi(f) и Х2 — Х2(1). -Х2(t) последовательно сравниваются разряды этих чисел, начиная со старших. Выходные сигналы формули­руются согласно вышеуказанным правилам. При этом, если выходная последовательность состоит из нулевых пар, то х± = Х2- Если первая,

о

) ТО Х\ > Х2 (xi < Х2).

тличная от нулевой, пара имеет вид

Из описания схемы следует, что

Х= {00; 01; 10; 11}; У = {00; 01; 10}.

Состояние схемы определяется следующим образом. Предположим, что в начальный момент времени t = 1 автомат находится в состоянии qi. Если сравниваемые разряды чисел X] и Х2 совпадают, то автомат остается в этом состоянии. Заметим, что на выходе при этом появится сигнал 00. Если же разряд числа Xi будет меньше (больше) соответствующего разря­да числа Х2, то автомат перейдет в состояние 6/2 (<?з). При этом на выходе появится сигнал 01 (10). В дальнейшем при подаче оставшихся разрядов чисел х\ и Х‘2 на входы автомата автомат будет оставаться в состоянии <?2 (<7з) ^и вырабатывать выходной символ 10 (01). Из вышеизложенного следует, что схему сравнения на неравенство можно задать таблицей:

	Qi	У2	4з
00	0 0	42', 01	4з', Ю
01	Ч2\ 01	42', 01	4з; Ю
10	Ч:й Ю	42', 01	4з; ю
11	qi; 00	42', 01	4з', 10

Соответствующая диаграмма Мура изображена на рис. 7.7.

Входной и выходной алфавиты здесь уже закодированы. Состояния qi, 92 и q_s закодируем: ai(gi) = 00; a(q₂) = 01; a(g₃) = 10.

С

Х\	Х2	Zi	22	Ф1	ф2	VI	V2
0	0	0	0	0	0	0	0
0	0	0	1	0	1	0	1
0	0	1	0	1	0	1	0
0	0	1	1	1	1	1	1
0	1	0	0	0	1	0	1
0	1	0	1	0	1	0	1
0	1	1	0	0	1	0	1
0	1	1	1	1	1	1	1
1	0	0	0	1	0	1	0
1	0	0	1	0	1	0	1
1	0	1	0	1	0	1	0
1	0	1	1	1	1	1	1
1	1	0	0	0	0	0	0
1	1	0	1	0	1	0	1
1	1	1	0	1	0	1	0
1	1	1	1	1	1	1	1

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

*

*

*

функции частично определены и задаются таблицей истинности