Практическое занятие № 15
Тема: «Нахождение канонических уравнений автоматов»
Цель: для автомата, заданного каноническими уравнениями, научится строить диаграмму Мура, задавать автомат системой булевых функций
Теория
Каноническое уравнение автомата
Если в момент времени t=1, 2,… на вход автомата A=(X; Q; Y; φ; ψ) последовательно подаются входные символы x(t) ϵ X и при этом автомат находится в состоянии q(t) ϵ Q, то под воздействием символа x(t) автомат перейдет в новое состояние q(t+1) ϵ Q и выдаст выходной сигнал y(t).
Величины x(t), y(t), q(t), q(t+1) связаны между собой следующими уравнениями:
t=1,
2, …, n, …
Эти уравнения называются каноническими уравнениями автомата А. При задании автомата системой булевых функций эти уравнения записываются в координатной форме:
z1(t+1)=φ1(x1(t), …, xk(t), z1(t), …, zr(t))
…
zr(t+1)=φr(x1(t), …, xk(t), z1(t), …, zr(t))
y1(t)=ψ1(x1(t), …, xk(t), z1(t), …, zr(t))
…
ys(t)=ψs(x1(t), …, xk(t), z1(t), …, zr(t))
t=1, 2, …
для построения канонических уравнений автомата А необходимо для данной булевой функции найти минимальную ДНФ, которая, вообще говоря, определяется неоднозначно. Аналитический алгоритм построения этой ДНФ следующий:
1. Для данной функции f (x1, …, xn) строим СКНФ.
2. В построенной СКНФ раскрываем скобки, используя правило:
3. Полученное выражение упрощаем, применяя тождества вида:
В результате получим СДНФ, являющуюся дизъюнкцией всех простых импликат данной функции f(x1, …, xn).
Для рассмотренных выше примеров автоматов канонические уравнения задаются следующими формулами:
пример 1: 
пример 2: 
пример 3: 
пример 4: 
В качестве иллюстрации изложенного выше алгоритма рассмотрим пример 3.
Таблица истинности булевых функций следующая:
|
x1 |
x2 |
z |
φ |
ψ |
|
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 |
1.
Строим
СКНФ функции φ(x1,x2,z). Так как эта функция задана
набором своих значений 
,
то её СКНФ будет иметь вид 
2. Раскрываем скобки
Упрощаем последнее выражение:
Таким образом,
получим 
Аналогично строится
функция y(t). При этом из таблицы истинности выписываем набор значений функции
ψ(x1, x2, z) 
,
который совпадает с набором значений функции φ(x1,x2,z).
Ход работы
Задача 1. Для автомата, заданного таблицей, постройте диаграмму Мура. Задайте этот автомат системой булевых функций.
а)
|
q a |
0 |
1 |
2 |
3 |
|
0 |
(1;1) |
(3;0) |
(2;0) |
(2;0) |
|
1 |
(2;1) |
(2;0) |
(3;0) |
(3;0) |
б)
|
q a |
0 |
1 |
2 |
3 |
|
0 |
(1;0) |
(3;1) |
(2;0) |
(1;0) |
|
1 |
(3;0) |
(1;1) |
(0;1) |
(3;1) |
в)
|
q a |
0 |
1 |
2 |
3 |
|
0 |
(0;0) |
(1;1) |
(3;1) |
(2;0) |
|
1 |
(2;0) |
(0;1) |
(3;1) |
(1;0) |
г)
|
q a |
0 |
1 |
2 |
3 |
|
0 |
(2;0) |
(0;0) |
(3;1) |
(1;0) |
|
1 |
1;0) |
(0;0) |
(0;0) |
(3;0) |
д)
|
q a |
0 |
1 |
2 |
3 |
|
0 |
(3;0) |
(2;0) |
(1;1) |
(0;1) |
|
1 |
(0;1) |
(1;1) |
(2;0) |
(3;0) |
е)
|
q a |
0 |
1 |
2 |
3 |
|
0 |
(2;1) |
(2;1) |
(2;1) |
(2;1) |
|
1 |
(1;1) |
(3;1) |
(0;0) |
(1;0) |
Задача 2. Для автомата, заданного диаграммой Мура, выпишите соответственную таблицу булевых функций.
а) См. рис. 8.
Рис. 8.
б) См. рис. 9.
в) См. рис. 10.
Задача 3. Для автомата, заданного каноническими уравнениями, постройте диаграмму Мура и соответствующую таблицу:
Рис. 9
Рис. 10
а) 
б) 
в) 
г) 
д) 
е) 
ж) 
Индивидуальные задания
|
Вариант |
задание1 |
задание 2 |
задание3 |
|
1 |
1 |
18 |
22 |
|
2 |
10 |
14 |
25 |
|
3 |
8 |
13 |
24 |
|
4 |
6 |
16 |
24 |
|
5 |
7 |
19 |
22 |
|
6 |
3 |
17 |
25 |
|
7 |
2 |
13 |
23 |
|
8 |
8 |
15 |
22 |
|
9 |
11 |
14 |
24 |
|
10 |
5 |
18 |
23 |
|
11 |
1 |
20 |
25 |
|
12 |
9 |
21 |
24 |
|
13 |
3 |
15 |
23 |
|
14 |
12 |
21 |
22 |
|
15 |
4 |
16 |
25 |
Контрольные вопросы
1. Что включает в себя понятие «конечный автомат»?
2. Какие основные термины связаны с введением понятия конечного автомата?
3. Дайте определение конечного автомата.
4. Укажите способы задания конечного автомата.
5. Каково табличное задание конечного автомата? Укажите способы задания конечного автомата.
6. Как строится диаграмма Мура?
7. Изложите алгоритм задания конечного автомата системой булевых функций.
8. Приведите примеры конечных автоматов.
9. Какие уравнения называются каноническими уравнениями конечного автомата?
10. Как построить каноническое уравнение конечного автомата?
Практическое занятие № 15 Тема: «Нахождение канонических уравнений автоматов»
В качестве иллюстрации изложенного выше алгоритма рассмотрим пример 3
Ход работы Задача 1. Для автомата, заданного таблицей, постройте диаграмму
Задача 2. Для автомата, заданного диаграммой
Рис. 9
Рис. 10
Индивидуальные задания
Контрольные вопросы 1.
© ООО «Знанио»
С вами с 2009 года.
