Практическая работа № 13

Решение задач по теме: «Конечные автоматы».

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

Теория

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

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

3 Автоматом Мили называется система A = (U, Q, V, δ ,λ), где множество

U={ u₁ ,...,u_n } – входной алфавит, его элементы – входные сигналы, Q= { q₁,...q_m}

– множество внутренних состояний, множество V ={v₁,...,v_k } – выходной алфавит, его элементы – выходные сигналы, δ:U×Q→Q – функция переходов, λ :U×Q →V- функция выхода.

4 С конечным автоматом ассоциируется воображаемое устройство, которое может находиться в состоянии из множества Q, воспринимать сигналы из множества U и выдавать сигналы из множества V.

5 Схема называется комбинационной, если каждую из ее выходов можно представить, как булеву функцию входных переменных, типа И-НЕ, И, ИЛИ, ИЛИ-НЕ и т.д.

6 Графическое изображение комбинационной схемы, при котором показаны связи между различными элементами (вентелями), а сами элементы представлены условными обозначениями, называется функциональной схемой.

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

Задания

1 Для автоматов, заданных таблицами, построить диаграммы состояний.

2 Задать табличным способом автомат, заданный диаграммой состояний.

Пример выполнения: Задание 1

Исходные данные:

Для автоматов, заданных таблицами, построить диаграммы состояний.

Решение:

– Автомат имеет четыре состояния, его множество состояний Q = {1, 2, 3, 4}, следовательно, граф автомата будет с четырьмя вершинами.

– Входной алфавит U = {0, 1}, а выходной алфавит V = {x, y}

– В каждой ячейке два объекта, первый соответствует направлению дуги из текущей вершины графа

– Над дугой записываем пару значений: значение входного алфавита и выходной символ из ячейки

Получим граф:

(1;у)

1 2

(0;у)

Задание2

(0;х)

(1;у)

(0;у)

4

(1;х)

(0;у)

(1;х)

3

Исходные данные:

Задать табличным способом автомат, заданный диаграммой состояний

Решение:

– Автомат имеет три состояния, его множество состояний Q = {1, 2, 3}, сле- довательно, в таблице четыре колонки.

– Над дугами пары объектов, первый – элемент входного алфавита, второй – выходного, значит входной алфавит U = {a, b}, а выходной алфавит V = {x, y}, в первой колонке две строки а и b

– В каждой ячейке два объекта, первый соответствует направлению дуги из текущей вершины графа, а второй – второму числу над соответствующей дугой

– Получим таблицу

U/Q	1	2	3
a	1, x	1, x	2, x
b	3, y	3, y	1, y

Задания к практической работе. Задание 1

Задание 2

1	(а;х) (b;у) 1 2 (b;у) (a;у) (а;х) 4 3 (b;х)	15	(x;х) (x;у) (y;у) 1 2 (y;у) (z;х) (z;х)
2	(c;х) (a;x) (c;x) 0 (b;у) 1 (a;y) (b;y)	16	(r;х) (s;у) (s;у) 1 2 (r;х) (r;у) (s;х) 3
3	(a;х) (b;у) (b;у) 1 (d;х) 2 (a;у) (c;х) (d;y) (c;х)	17	(k;х) (l;у) (l;у) 1 2 (k;х) (k;у) 3 (l;х)
4	(а;y) (a;x) 1 2 (b;у) (a;у) (b;у) 4 (а;х) 3 (a;y) (b;х) (b;х)	18	(d;y) (d;y) 1 (c;у) 2 (d;x) (c;у) (c;x) 4 (d;х) 3 (b;х)

5	(а;h) (b;p) 1 2 (b;p) (а;h) (a;h) 4 (b;p) (а;p) 3 (b;h)	19	(a;x) 0 (b;x) 1 (b;x) (a;y) (a;y) (a;x) 3 (b;y) 2 (b;х)
6	(f;y) (f;y) (r;x) 1 2 (f;х) (r;у) (r;x) 4 (f;х) 3 (r;y)	20	(l;y) 1 (l;y) 2 (k;x) (k;y) (l;х) (k;у) (k;x) 4 3 (l;x)
7	(μ;a) 1 (γ;b) 2 (γ;b) (μ;b) (μ;b) (μ;a) 4 (γ;a) 3 (γ;a)	21	(α;z) (β;у) 1 2 (α;y) (β;z) (α;z) (β;z) (α;y) 4 (β;у) 3
8	(h;х) 1 (p;у) 2 (p;у) (p;х) (h;у) (p;х) (h;х) 4 (h;y) 3 (b;х)	22	(r;x) 1 (s;y) 2 (s;y) (r;y) (r;x) (r;y) 4 (s;x) 3 (s;x)
9	(a;x) (b;y) 1 2 (b;y) (a;y) (a;y) (a;x) 4 (b;x) 3 (b;x)	23	(a;х) (b;у) (b;у) 1 (a;у) 2 (c;х) (c;х)
10	(a;х) (b;у) (c;z) 1 (a;у) 2 (c;z) (b;y)	24	(ξ;a) (η;a) (η;b) 1 2 (ξ;b) (ξ;b) 3 (η;b)

11	(b;у) 1 (b;у) 2 (a;х) (a;у) (a;х) (b;х) 3	25	(k;x) (l;у) 1 2 (l;х) (k;х) (k;у) (l;y) 3
12	(b;y) (a;y) (a;x) 1 2 (a;x) (b;x) (b;y) 3
13	(1;у) (1;y) 1 2 (0;x) (0;у) (0;x) 4 3 (1;x) (0;y) (1;х)
14	(j;y) 1 (j;y) 2 (i;x) (i;y) (i;y) (i;x) 4 (j;x) 3 (j;x)