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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

94
X
(1)
= {0, 1}, X
(2)
= {1, 2, 3},
Z
(1)
= {0, 1, 2, 3, 4, 5, 6}, Z
(2)
= {0, 1, 2, 3}
и, следовательно,
X
= {(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3)},
Z
= {(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3),
(2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3),
(4, 0), (4, 1), (4, 2), (4, 3), (5, 0), (5, 1), (5, 2), (5, 3),
(6, 0), (6, 1), (6, 2), (6, 3)}.
Значения промежуточных переменных системы определяют со-
стояние системы. Состояние системы в момент времени t
ν
будем обозна-
чать через s
ν
. Совокупность всех возможных состояний системы, которые
ей присущи, называется множеством состояний системы и обозначается
через S. Состояние s
ν
вместе с входным символом x
ν
в ν-й тактовый мо-
мент времени определяет выходной символ z
ν
системы в данный момент
и её состояние s
ν + 1
в следующий (ν + 1)-й момент.
Формирование множества состояний в общем случае является
сложной задачей, которая решается не обязательно однозначно. Так как
не существует общих правил её решения, часто прибегают к методу по-
следовательных приближений путём проб и ошибок. Затраты времени на
выбор множества S зависят от интуиции исследователя и степени знания
им исследуемой системы.
Конечным автоматом M (автоматом Мили) называется синхрон-
ная система с конечным входным алфавитом X = {ξ
1
, ξ
2
, ..., ξ
p
}, с конеч-
ным выходным алфавитом Z = {ζ
1
, ζ
2
, ..., ζ
q
}, с конечным множеством со-
стояний S = {σ
1
, σ
2
, ..., σ
n
} и двумя характеристическими функциями:
z
ν
= f
z
(x
ν
, s
ν
),
s
ν + 1
= f
s
(x
ν
, s
ν
),
где x
ν
, z
ν
и s
ν
− соответственно входной символ, выходной символ и со-
стояние автомата M в момент времени t
ν
(ν = 1, 2, 3, ...).
Если характеристическая функция f
z
конечного автомата M зависит
только от его состояния, т.е. f
z
(x
ν
, s
ν
) = f
z
(s
ν
), автомат называется авто-
матом Мура.
Если характеристическая функция f
z
конечного автомата M зависит
только от входного символа, т.е. f
z
(x
ν
, s
ν
) = f
z
(x
ν
), автомат называется
тривиальным автоматом (автоматом без памяти или комбинационным
устройством).
Далее под конечным автоматом будем понимать автомат Мили, если
не оговорена его модификация.

Страницы