Синтез цифровых автоматов. Захаров Н.Г - 51 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

50
Оператор автомата Мили (автомата с памятью) полностью описывается функ-
цией переходов q(t +1) и функцией выходов y(t).
Закон функционирования автомата Мили задается уравнениями:
q (t+1) = δ(q(t), x(t)),
y (t) = λ(q(t), x(t)), где t = 0, 1, 2, …
Как отмечалось в п. 3.1.1, конечный автомат А описывается выражением:
А = (Q, X, Y, δ, λ, q
0
),
в котором заданы входной и выходной алфавиты, алфавит состояния, а также функ-
ции переходов и выходов.
Выделение в множестве состояний конечного автомата А начального состояния
q
0
объясняется чисто практическими соображениями, связанными, в первую очередь,
с необходимостью фиксировать условия начала работы дискретного устройства. Ав-
томат с выделенным начальным состоянием q
0
называется инициальным.
Многие же задачи можно решать, описывая автомат без начального состоя-
ния q
0
:
А = (Q, X, Y, δ, λ).
Функцию переходов δ и функцию выходов λ определим на их множестве пар
<состояние – входное слово>.
Пусть
ξ = x
i1
x
i2
…x
ik
– входное слово длины k; Е – множество всех конечных вход-
ных слов ненулевой длины; ε – входное слово нулевой длины (пустое слово);
mm
q),q(
~
=εδ для всех Qq
m
∈ .
Тогда функцию заключительного состояния
),q(
~
m
ξδ определим в множест-
ве
}){(EхQ ε∪
следующим образом:
==δδ=δδ
=
=δ=ξδ
−
случае. противном в определена не
;qq k;1,...,jвсех для определена )x,q( если ),x,q()x,)x...x,q(
~
(
)x...x,q(),q(
mi1ijijikikik
q
1ik1im
ik1im
~
m
~
ik
444344421
Пример 1
Пусть автомат А
1
задан совмещенной таблицей 3.9.
Таблица 3.9
δ : Q x X →Q,
λ
: Q x X → Y
q
1
q
2
q
3
q
4
x
1
q
2
/y
1
q
3
/y
3
q
4
/y
3
−
x
2
q
3
/y
2
−
q
2
/−
q
2
/y
2
Требуется найти
),q(
~
2
ξδ , при
21211
ххххх
=
ξ
.
.q)x,q()x,q(
~
)x),x,q((
~
)xx,q(
~
)xx),x,q((
~
)xxx,q(
~
)xxx),x,q((
~
)xxxx,q(
~
)xxxx),x,q((
~
)xxxxx,q(
~
22323212
2122124212421213
21213212112212112
=δ=δ=δδ=
=δ=δδ=δ=δδ=
=δ=δδ=δ

Страницы