Б.1.В.ОД.5 «Теория конечных автоматов»

 

Направление подготовки

Автоматизация технологических процессов и производств».

 

Квалификация выпускника

Бакалавр

 

Форма обучения

Очная

 

Москва

Содержание

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

ЗАДАНИЕ № 02-18 НА РАЗРАБОТКУ ПРОЕКТА КА

«СИСТЕМА ТРАНСПОРТИРОВАНИЯ СЫПУЧЕГО МАТЕРИАЛА

Пример конкретного выполнения

ЗАДАНИЕ № 03-18 НА РАЗРАБОТКУ ПРОЕКТА КА

 «СИСТЕМА МЕХАНИЧЕСКОЙ ОБРАБОТКИ ДЕТАЛИ «

Пример конкретного выполнения.

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

Понятие конечного автомата

 

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

По входному каналу в каждый момент времени t =1, 2,... в устройство М поступают входные сигналы (из некоторого конечного множества сигналов). Задается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния устройства в текущий момент времени. Выходной сигнал зависит от состояния и входного сигнала в текущий момент времени (рис. 1).

 

 

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

Конечным автоматом называется система А=(X, Q, Y, j, y), где X, Q, Y — произвольные непустые конечные множества, а j и y - функции, из которых:

1) множество X={ a ₁,..., a_m } называется входным алфавитом, а его элементы — входными сигналами, их последовательности — в ходными словами;

2) множество Q={ q ₁,..., q_n } называется множеством состояний автомата, а его элементы — состояниями;

3) множество Y ={ b ₁,..., b_p } называется выходным алфавитом, его элементы — выходными сигналами, их последовательности — выходными словами;

4) функция j: X´Q® Q называется функцией переходов;

5) функция y:X´Q® Y называется функцией выходов.

Таким образом, j (x, q)ÎQ, y (x, q)Î Y для " x ÎX, " q ÎQ.

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

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

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

2.1.Табличное задание автомата

Из определения автомата следует, что его всегда можно задать табли­цей с двумя входами, содержащей т строк и п столбцов, где на пересечении столбца q и строки а стоят значения функций j (a_i, q_j), y (a_i, q_j).

q a	q 1	…	qj	…	qn
a 1	j (a 1, q 1), y (a 1, q 1)	…	j (a 1, qj), y (a 1, qj)	…	j (a 1, qn), y (a 1, qn)
…	…	…	…	…	…
ai	j (ai, q 1), y (ai, q 1)	…	j (ai, qj), y (ai, qj)	…	j (ai, qn), y (ai, qn)
…	…	…	…	…	…
am	j (am, q 1), y (am, q 1)	…	j (am, qj), y (am, qj)	…	j (am, qn), y (am, qn)

 

Задание автомата диаграммой Мура

Другой способ задания конечного автомата — графический, то есть с помощью графа. Автомат изображается в виде помеченного ориентированного графа Г (Q, D) с множеством вершин Q и множеством дуг D ={(q_j, j (a_i, q_j))| q_j ÎQ, a_i ÎX}, при этом дуга (q_j, j (a_i, q_j)) помечается парой (a_i, y (a_i, q_j)). Таким образом, при этом способе состояния автомата изображают кружками, в которые вписывают символы состояний q_j (j=1, …, n). Из каждого кружка проводится т стрелок (ориентированных ребер) взаимно-однозначно соответствующих символам входного алфавита X={ a ₁,..., a_m }. Стрелке, соответствующей букве a_i ÎX и выходящей из кружка q_j ÎQ, приписывается пара (a_i, y (a_i, q_j)), причем эта стрелка ведет в кружок, соответствующий j (a_i, q_j).

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

 

Задание конечного автомата системой булевых функций

Третий способ задания конечного автомата А=(X, Q, Y, j, y), задан­ного таблицей или диаграммой Мура, состоит в определении системы булевых функций.

Изложим алгоритм этого способа задания.

(1)  Находим числа k, r, s, удовлетворяющие условиям 2^k-1< m <2^k, 2^r-1< n ≤2^r, 2^s-1< m <2^s, где m =| Х |, п=| Q |, p=| Y |.

Очевидно, что k, r, s соответственно равны числу разрядов в двоичном представлении чисел т, п, р. Например, если m =5, n=17, р=3, то k=3, r =5, s =2.

(2) Кодирование состояний входных и выходных символов исходного автомата.

Каждому q_j ÎQ взаимно однозначно ставим в соответствие двоичную последовательность длины r — двоичный код a (q)=z₁z₂...z_r. Аналогично каждому a_i ÎX и каждому b_k ÎY ставим взаимно однозначно в соответствие двоичные последовательности b (a)=x₁x₂...x_k, g (b)=y₁y₂...y_s.

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

(3) Составляем следующую таблицу:

Код входного символа

Код текущего состояния

Код следующего состояния

Код выходного символа

x1

x2

...

xk

z1

z2

...

zr

j1

j2

...

jr

y1

y2

...

ys

0

0

…

0

0

0

…

0

b1

b2

...

bk

a1

a2

...

ar

g1

g2

...

gs

1

1

…

1

1

1

…

1

 

Эта таблица содержит k+ r + r +s столбцов и 2 ^{k + r} строк. В первых k+ r столбцах выписаны все наборы длины k+ r. Каждый такой набор соответ­ствует паре (b, a), где a — возможный код некоторого состояния, b —код входного символа.

(4)     Заполнение последних столбцов в таблице (предыдущий шаг). Для каждой пары (a_i, q_j), где a_i ÎX, q_j ÎQ, находим код b (a) и a (q).

По таблице автомата (или диаграмме Мура) определяем j (a, q)= q ¢ и y (a, q)= b. Затем находим код a (q ¢)= …  и код g (b)=g₁g₂…g _s. В строку таблицы, соответствующую набору

b₁, b₂, …, b _k, a₁, a₂, …, a _r,

дописываем набор

, , …, , g₁, g₂, …, g _s.

(5) Определение системы булевых функций.

После выполнения предыдущего шага может оказаться, что не все строки в таблице заполнены. Это произойдет в том случае, если хотя бы одно из чисел т, п не является степенью 2. Таким образом, функции j₁, j₂, …, j_r, y₁, y₂, …, y_s окажутся не полностью определенными — на некоторых наборах их значения не определены. Тогда мы их доопределяем произвольным образом. Как правило, доопределение функций производят так, чтобы получившиеся полностью определенные функции удовлетворяли тем или иным условиям оптимальности, например представлялись минимальными ДНФ.

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

{j₁, j₂, …, j_r, y₁, y₂, …, y_s }.

 

 

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

 

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

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

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

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

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

 

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

Зададим элемент задержки таблицей, где а₁=0, а ₂=1, q₁=0, q ₂=1,

j (a ₁, q ₁)= j (0, 0)=0, y (a ₁, q ₁)= y (0, 0)=0;

j (a ₁, q ₂)= j (0, 1)=0, y (a ₁, q ₂)= y (0, 1)=1;

j (a ₂, q ₁)= j (1, 0)=1, y (a ₂, q ₁)= y (1, 0)=0;

j (a ₂, q ₂)= j (1, 1)=1, y (a ₂, q ₂)= y (1, 1)=1;

q a	0	1
0	j =0, y =0	j =0, y =1
1	j =1, y =0	j =1, y =1

Диаграмма Мура изображена на рис. 3

 

 

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

Обратим внимание на то, что т=п=р=2. Тогда k= r = s =1, и поэтому элемент задержки задается двумя функциями j и y. Таблица истинности этих функций содержит 2 ^{k + r} =2²=4 строки и k+ r + r +s=4 столбца:

x	z	j	y
0	0	0	0
0	1	0	1
1	0	1	0
1	1	1	1

 

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

Данный сумматор последовательного действия представляет собой устройство, осуществляющее сложение двух чисел в двоичной системе исчисления. На входы сумматора подаются числа х₁ и x₂, начиная с младших разрядов. На выходе формируется последовательность, соответствующая записи числа х₁+x₂ в двоичной системе исчисления (рис. 4).

 

 

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

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

q a	q 0	q 1
00	q 0, 0	q 0, 1
01	q 0, 1	q 1, 0
10	q 0, 1	q 1, 0
11	q 1, 0	q 1, 1

 

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

Заметим, что входные и выходные символы уже закодированы. Состояния закодируем следующим образом: a (q ₀)=0, a (q ₁)=1. Поэтому сумматор последовательного действия задается двумя булевыми функциями, таблица истинности которых следующая:

x 1	x 2	z	j	y
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. Схема сравнения на равенство.

Схема сравнения на равенств представляет собой устройство, срав­нивающее два числа х₁ и x₂, заданное в двоичной системе исчисления. Это устройство работает следующим образом. На вход устройства после­довательно, начиная со старших, подаются разряды чисел х₁ и x₂. Эти разряды сравниваются. При совпадении разрядов на выходе схемы формируется выходной сигнал 0, в противном случае на выходе появляется сигнал 1. Ясно, что появление 1 в выходной последовательности означает, что сравниваемые числа х₁ и x₂ различны. Если же выходная последовательность является нулевой и ее длина совпадает с числом разрядов сравниваемых чисел, то х₁ и x₂.

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

Функционирование схемы определяется двумя состояниями. Состояние q₀ соответствует равенству сравниваемых в данный момент разрядов. При этом автомат остается в этом же состоянии. Если в следующий момент сравниваемые разряды будут различны, то автомат перейдет в новое состояние q₁ и в нем остается, так как это означает, что числа различны. Таким образом, схему сравнения можно задать таблицей:

q x	q 0	q 1
00	q 0, 0	q 1, 1
01	q 1, 1	q 1, 1
10	q 1, 1	q 1, 1
11	q 0, 0	q 1, 1

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

	Рис. 6

Кодирование состояний произведем следующим образом: a (q ₀)=0, a (q ₁)=1. Автомат будет задаваться двумя функциями.

 

x1	x2	z	j	y
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. Схема сравнения на неравенство.

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

y₁(t)=y₂(t)=0, если x₁(t)=x₂(t);

y₁(t)=1, y₂(t)=0, если x₁(t)>x₂(t), то есть x₁(t)=1, x₂(t)=0;

y₁(t)=0, y₂(t)=1, если x₁(t)<x₂(t), то есть x₁(t)=0, x₂(t)=1.

Таким образом, при подаче на вход схемы сравнения на неравенство чисел x₁=x₁(l)…x₁(t) и x₂=x₂(l)…x₂(t) последовательно сравниваются разряды этих чисел, начиная со старших. Выходные сигналы формулируются согласно вышеуказанным правилам. При этом, если выходная последовательность состоит из нулевых пар, то x₁=x₂. Если первая, отличная от нулевой, пара имеет вид , () то x₁>x₂ (x₁<x₂).

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

X={00, 01, 10, 11}, Y ={00, 01, 10}.

Состояние схемы определяется следующим образом. Предположим, что в начальный момент времени t=1 автомат находится в состоянии q₁. Если сравниваемые разряды чисел х₁ и х₂ совпадают, то автомат остается в этом состоянии. Заметим, что на выходе при этом появится сигнал 00. Если же разряд числа х₁ будет меньше (больше) соответствующего разряда числа х₂, то автомат перейдет в состояние q₂ (q₃). При этом на выходе появится сигнал 01 (10). В дальнейшем при подаче оставшихся разрядов чисел х₁ и х₂ на входы автомата автомат будет оставаться в состоянии q₂ (q₃) и вырабатывать выходной символ 10 (01). Из вышеизложенного следует, что схему сравнения на неравенство можно задать таблицей:

q x	q 1	q 2	q 3
00	q 1, 00	q 2, 01	q 3, 10
01	q 2, 01	q 2, 01	q 3, 10
10	q 3, 10	q 2, 01	q 3, 10
11	q 1, 00	q 2, 01	q 3, 10

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

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

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

	x1	x2	z1	z2	j1	j2	y1	y2
	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	1	1	0	1	0
*	1	1	1	1	1	1	1	1

В таблице символами * отмечены наборы переменных x₁, x₂, z₁, z₂, на которых функции j₁, j₂, y₁, y₂ не определены. Положим значения функций j₁, j₂, y₁, y₂ на этих наборах равными 1.