Дискретная математика. Громов Ю.Ю - 99 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

99
Мощность
ЯМ
,, qpn
N
класса явно минимальных (n, p, q)-автоматов, не
содержащих изоморфных автоматов, определяется формулой
∏
−
=
−=
1
0
ЯМ
,,
)(
!
n
r
p
pn
qpn
rq
n
n
N
,
где отрицательные значения
ЯМ
,, qpn
N
принимаются равными нулю.
Задачи и упражнения
1. Постройте таблицу переходов для каждого конечного автомата
из упр. 1, а – в предыдущего параграфа и проверьте корректность его ра-
боты для некоторой случайной входной последовательности при задан-
ном начальном состоянии.
2. Постройте автомат, изоморфный автомату с приведённой ниже
таблицей переходов, посредством замены обозначений состояний 1, 2, 3,
4, 5 и 6 на 2, 3, 4, 5, 6 и 1 соответственно:
z
ν
s
ν+1
z
ν
s
ν+1
x
ν
s
ν
α β α β
x
ν
s
ν
α β α β
1 0 0 1 1 4 0 1 4 2
2 0 0 2 1 5 1 0 5 3
3 0 1 3 2 6 1 0 6 3
20. ГРАФ ПЕРЕХОДОВ КОНЕЧНОГО АВТОМАТА
Графом переходов (n, p, q)-автомата называется взвешенный ориенти-
рованный граф, вершины которого соответствуют состояниям σ
1
, σ
2
, ..., σ
n
этого автомата, а дуги − возможным переходам из одного состояния в
другое. Каждая дуга графа переходов вида (σ
i
, σ
j
) имеет вес, равный ло-
гической сумме
)/(
11
lk
ζξ
∨
)/(
22
lk
ζξ
∨
...
∨
)/(
rr
lk
ζξ
. Для любого сла-
гаемого вида
)/(
hh
lk
ζξ
, называемого парой вход-выход, верны равенства
h
l
ζ
= f
z
(
h
k
ξ
, σ
i
), σ
j
= f
s
(
h
k
ξ
, σ
i
), т.е. автомат, находясь в состоянии σ
i
, при
входе
h
k
ξ
выдаёт выходной символ
h
l
ζ
и переходит в состояние σ
j
.
На рисунке 53 изображён граф переходов автомата А1, соответст-
вующий табл. 23.

Страницы