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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

98
Автомат, имеющий n состояний, p входных и q выходных символов,
называется (n, p, q)-автоматом. Мощность N
n, p, q
класса (n, p, q)-
автоматов определяется формулой
N
n, p, q
= (qn)
pn
.
Явно минимальным (n, p, q)-автоматом называется (n, p, q)-автомат
такой, когда для каждого i и каждого j ≠ i существует k, при котором
f
z
(ξ
k
, σ
i
) ≠ f
z
(ξ
k
, σ
j
). В z
ν
-подтаблице явно минимального (n, p, q)-авто-
мата все строки различны. Мощность
qpn
N
,,
′
класса явно минимальных
(n, p, q)-автоматов равна
∏
−
=
−=
′
1
0
,,
)(
n
r
ppn
qpn
rqnN
,
где отрицательные значения
qpn
N
,,
′
считаются равными нулю.
Явно сократимым (n, p, q)-автоматом называется (n, p, q)-автомат
с таблицей переходов, в которой существует по крайней мере одна пара
строк, например σ
i
и σ
j
, которые одинаковы в обеих подтаблицах или ста-
новятся одинаковыми при замене каждого символа σ
i
на символ σ
j
(или
σ
j
на σ
i
). Оценка мощности
qpn
N
,,
′′
класса явно сократимых (n, p, q)-авто-
матов определяется неравенством
[
]
∏
−
=
−−≥
′′
1
0
,,
)()(
n
r
ppn
qpn
rqnqnN
.
Два автомата, у которых характеристические функции одинаковы, за
исключением возможных различий в обозначениях состояний, называют-
ся изоморфными друг другу. Таблицей 24 представлен автомат, изо-
морфный автомату A1. Он получен заменой первоначальных обозначений
состояний 1, 2, 3, 4 и 5 на 5, 4, 3, 2 и 1 соответственно.
Таблица 24
z
ν
s
ν+1
x
ν
s
ν
d n u π λ d n u π λ
1 0 0 0 1 0 1 2 2 5 2
2 0 0 0 0 0 1 2 2 5 2
3 0 0 0 0 0 4 2 4 5 4
4 0 0 0 0 0 4 4 4 5 4
5 0 0 0 0 0 4 4 3 5 4

Страницы