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

1. Дайте определение конечного автомата.

2. Чем отличается автомат Мили от автомата Мура?

5.2. Пример функционирования автомата Мили представ­лен табл. 5.2. На пересечении строк входных сигна­лов (x₁, x₂) и столбцов текущего состояния (u₀, u₁, u₂, u₃) в клетках располагается новое внутреннее состояние и зна­чение выходного сигнала и/у.

Показать функционирование этого автомата в виде графа.

Таблица 5.2

Таблица переходов-выходов автомата Мили

Входные сигналы	Внутреннее состояние
	u0	u1	u2	u3
x1	u1/y2	u3/y2	u1/y1	u0/y1
x2	u0/y1	u2/y1	u3/y1	u3/y3

Решение

Запись и₃/у₂ на пересечении столбца и₁ и строки х₁ означает, что под воздействием входного сигна­ла х₁ автомат Мили перейдет из состояния и₁ в состояние u₃ и выходной сигнал будет у₂. Заметим, что при разных входных сигналах и одинаковом внутреннем состоянии могут быть получены различные выходные сигналы. Так, из состояния и₂ под воздействием входного сигнала х₂ ав­томат Мили перейдет также в состояние и₃, но выходной сигнал будет у₁.

Функционирование этого же автомата Мили в виде графа показано на рис. 5.1.

Рис. 5.1. Функционирование в виде графа автомата Мили, заданного табл. 5.1

В узлах показаны состояния, а дуги показывают пере­ходы из одного состояния в другое. Дуги отмечаются па­рой символов: под действием какого входного сигнала со­вершается переход и какой при этом выдается выходной сигнал. В некоторых случаях автомат может сохранять предыдущее состояние (дуга х₂, у₃, из состояния U₃, воз­вращается в U₃ ).

По табл. 5.2 и рис. 5.1 можно определить выход­ную последовательность при любой заданной входной пос­ледовательности:

входная последовательность x₁, x₂, x₂, x₁, x₂, x₁, x₁, x₂,…;

внутреннее состояние u₀, u₁, и₂, и₃, и₀, и₀, u₁, u₃, и₃, ...;

выходная последовательность y₂, y₁, y₁, y₁, y₁, y₂, y₂, y₃,….

В автоматах Мура выходной сигнал у(t) жестко зави­сит от внутреннего состояния U(t). Поэтому значения выходного сигнала располагают рядом со значениями внут­реннего состояния. В клетках таблицы переходов-выхо­дов автомата Мура (табл. 5.3) указывают только новое внутреннее состояние.

Таблица 5.3

Таблица переходов-выходов автомата Мура

Входные сигналы	Выходные сигналы, внутреннее состояние
	у2	у3	у1	у4	у0
	u0	u1	u2	u3	u4
x1	u4	u1	u2	u2	u3
x2	u1	u2	u3	u4	u0

Состояние и₃ на пересечении столбца и₄ и строки x₁ означает, что при воздействии входного сигнала х₁ ав­томат Мура из и₄ перейдет в состояние и₃. Выходной сигнала у₃ возникает при нахождении автомата Мура в состоянии и₁. Табл. 5.3 соответствует граф (рис. 5.2).

Рис. 5.2. Функционирование в виде графа автомата Мура, заданного табл. 5.3

5.2. Минимизировать цифровое устройство, заданное табл. 5.4 и соответствующим графом (рис. 5.3).

Таблица 5.4

Таблица переходов-выходов автомата до минимизации

Входные сигналы	Внутреннее состояние
	u0	u1	u2
x1	u0/y3	u2/y1	u1/y1
x2	u1/y1	u0/y2	u0/y2

Рис. 5.3. Граф цифрового устройства, заданного табл. 5.3

Решение

Из анализа графа видно, что состояния и₁, и₂ являются эквивалентными. Под дей­ствием входного сигнала х₁ из обоих состояний на выходе возникает у₁, автомат переходит из u₁ в и₂ либо наоборот.

При воздействии сигнала х₂ из обоих состояний u₁, u₂ на выходе получаем у₂, автомат переходит к и₀. Выделяем два состояния (u₁, u₂) в подмножество, заменяем одним пред­ставителем (u₁). Получаем новую табл. 5.5 переходов-выходов и новый граф (рис. 5.4). По сравнению с исход­ным графом число состояний уменьшилось с 3 до 2, число внутренних связей с 6 до 4.

Таблица 5.5

Таблица переходов-выходов автомата после минимизации

Входные сигналы	Внутреннее состояние
	u0	u1
x1	u0/y3	u1/y1
x2	u1/y1	u0/y2

Рис. 5.4. Граф цифрового устройства после минимизации

5.3. Для автомата, заданного табл. 5.6, постройте диаграмму Мура.

Таблица 5.6

Таблица переходов-выходов автомата

5.4. Для автомата, заданного диаграммой Мура (рис. 5.5), выпишите соответственную таблицу.

Рис. 5.5. Диаграмма Мура к задаче 5.4

ОТВЕТЫ

1.2. 1) M_2n = {2, 4, 6,…, 100}; 2) 2  M_2n; б) если n N, то (n+2)  М_2n; в) n 98; 3) M_2n = {n: n – целое положительное число, не превышающее 100} или М_2n = {n: n  N и n/2  N, n 100}. 1.3.  (U) = {, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.  (U)  = 8. 1.4.  Y = {2, 3, 4}. 1.16. Указание. Нарисовать диаграмму Эйлера-Венна в виде трех кругов, обозначающих множество студентов, изучающих, соответственно французский, немецкий и испанский языки. В каждую из 8 областей вписать данные, используя приведенные цифры. Начинать с конца списка и двигаться к началу. 1) 20; 2) 30; 4) 38. 1.17. 1) 18; 2) ни одного; 3) 50.

2.5. , n₁ = 9, n₂ = 10. 2.6. n = 18. 2.7. а) б) 2.8. 2.9. 2.10. а) Р₄ = 4! = 24; б) 4 Р₄ = 96; в) Р₃ = 6; г) Р₅ – Р₃ = 114; д) 2 Р₄ = 48; е) 4 Р₃ = 24. 2.11. а) Р₃ = 6; б) 2.14. = 64. 2.15. 2.16. 2.17. 2ⁿ = 64, n = 6, к = 2,

3.9.

X	Y	Х  Y		(Х  Y) 	(Х  Y)   Y
0	0	1	1	1	0
0	1	0	1	1	1
1	0	0	0	1	0
1	1	1	0	0	0

3.10

Х1	Х2	Х3	Х1  Х2	Х1  Х2  Х3
0	0	0	0	1
0	0	1	0	1
0	1	0	1	0
0	1	1	1	1
1	0	0	1	0
1	0	1	1	1
1	1	0	1	0
1	1	1	1	1

3.11.

Х	Y	Е	Х  Е	Х  (Х  Е)	(Х  (Х  Е))  Y
0	0	1	1	0	1
0	1	1	1	0	0
1	0	1	1	1	1
1	1	1	1	1	1