ВУЗ:
Составители:
5
ψ
[z
i
, х
i
].
Примеры табличного способа задания F-автомата
Мили с тремя состояниями, двумя входными и двумя
выходными сигналами приведены в таблице 1.1, а для F-
автомата Мура - в таблице 1.2.
Таблица 1.1
z
k
x
i
z
1
z
2
z
3
Переходы
x
1
z
2
z
3
z
3
x
2
z
3
z
2
z
1
Выходы
x
1
y
1
y
1
y
2
x
2
y
1
y
2
y
1
Таблица 1.2
y
j
y
1
y
1
y
2
x
i
z
1
z
2
z
3
x
1
z
3
z
3
z
2
x
2
z
1
z
1
z
3
При графическом способе задания конечного
автомата применяется направленный граф, вершины
которого соответствуют состояниям автомата, дуги -
переходам.
На рисунке 1.1, а, б приведены заданные ранее
таблицами F-автоматы Мили и Мура соответственно.
При матричном задании конечного автомата
применяют квадратную матрицу С=||c
ij
||, строки которой
соответствуют исходным состояниям, а столбцы -
состояниям перехода. Элемент c
ij
=x
k
/y
S
, соответствует
входному сигналу x
k
, вызывающему переход из состояния z
i
в состояние z
j
, и выходному сигналу у
S
, выдаваемому при
этом переходе. Для автомата Мили, рассмотренного выше,
6
матрица соединений имеет вид:
−
−
−
=
2111
2122
1211
1
//
//
//
yxyx
yxyx
yxyx
C
.
Для F-автомата Мура элемент c
ij
равен множеству
входных сигналов на переходе (z
i
,z
j
), а выход описывается
вектором выходов. Для рассмотренного выше F-автомата
Мура матрица соединений и вектор выходов имеют вид:
;
21
12
12
2
−
−
−
=
xx
xx
xx
C
.
2
1
1
=
y
y
y
Y
Задание
Придумать F-автомат, представив его в табличном,
графическом и матричном видах, и составить программу,
x
2
, y
1
y
1
x
1
x
1
, y
2
x
1
, y
1
x
2
, y
2
x
2
, y
1
z
1
z
2
z
3
x
1
, y
1
а
x
2
x
1
x
2
z
1
z
2
z
3
б
y
1
x
2
y
2
Рис. 1.1. Г
р
а
ф
ы автоматов Мили
(
а
)
и М
ур
а
(
ψ[zi, хi]. матрица соединений имеет вид:
Примеры табличного способа задания F-автомата − x1 / y1 x2 / y1
Мили с тремя состояниями, двумя входными и двумя C1 = − x2 / y 2 x1 / y 2 .
выходными сигналами приведены в таблице 1.1, а для F- x / y − x1 / y 2
автомата Мура - в таблице 1.2. 1 1
Таблица 1.1
xi zk x2, y2 x2
z1 z2 z3 x1, y1 x2 y1
Переходы z1 z2 z1 z2
x1 z2 z3 z3
x2 z3 z2 z1 y1
x1
x2, y1
Выходы
x1 y1 y1 y2 x1, y1 x1
x2 y1 y2 y1 x2, y1
Таблица 1.2
z3 z3
yj y2
xi y1 y1 y2
z1 z2 z3 x1, y2
x2
x1 z3 z3 z2 а б
x2 z1 z1 z3
Рис. 1.1. Графы автоматов Мили (а) и Мура (
При графическом способе задания конечного
автомата применяется направленный граф, вершины Для F-автомата Мура элемент cij равен множеству
которого соответствуют состояниям автомата, дуги - входных сигналов на переходе (zi,zj), а выход описывается
переходам. вектором выходов. Для рассмотренного выше F-автомата
Мура матрица соединений и вектор выходов имеют вид:
На рисунке 1.1, а, б приведены заданные ранее x2 − x1 y1
таблицами F-автоматы Мили и Мура соответственно.
При матричном задании конечного автомата C 2 = x2 − x1 ; Y = y1 .
применяют квадратную матрицу С=||cij||, строки которой − x x y
1 2 2
соответствуют исходным состояниям, а столбцы -
состояниям перехода. Элемент cij=xk/yS, соответствует Задание
входному сигналу xk, вызывающему переход из состояния zi
в состояние zj, и выходному сигналу уS, выдаваемому при Придумать F-автомат, представив его в табличном,
этом переходе. Для автомата Мили, рассмотренного выше, графическом и матричном видах, и составить программу,
5 6
