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

UptoLike

ВУЗ: 

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

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

Рубрика: 

51
Если
22211
ххххх=ξ
, то получим:
).x),x,q((
~
)xx,q(
~
)xx),x,q((
~
)xxx,q(
~
)xxx),x,q((
~
)xxxx,q(
~
)xxxx),x,q((
~
)xxxxx,q(
~
222
2222224222422213
22213222112222112
δδ=
=δ=δδ=δ=δδ=
=δ=δδ=δ
Функция
),q(
~
2
ξδ при
22211
ххххх=ξ
не определена, так как в таблице 3.9 не
определена функция переходов
)х,q(
22
δ .
Таким образом, автомат А
1
переходит в заключительное состояние ),q(
~
m
ξδ из
состояния q
m
только под действием определенного входного слова о .
Функция заключительного выхода
),q(
~
m
оλ
модели автомата Мили определя-
ется в множестве
}){(EхQ ε∪
следующим образом:
),,q(
~
определена не если ,определена не
;определена ),q(
~
если ,x),x),,q(
~
(
),q(
~
m
mikikm
m
ξ
′
δ
−ξ
′
δξ
′
=ξξ
′
δλ
=λ о
где
1ik1iik1ik1i
x...x ;xx...x
−−
=
ξ
′
=
ξ
.
Таким образом, в модели автомата Мили
),q(
~
m
оλ
– выходной сигнал, выдавае-
мый на последнем переходе (переходе в заключительное состояние). Он появляется
на выходе в тот же момент времени, когда приходит последняя буква входного слова
о.
Пример 2
Пусть автомат А
2
, задан таблицей 3.10, найдем
)xxxx,q(
~
11211
λ
.
Таблица 3.10
δ: Q x X → Q; λ: X →Y
q
1
q
2
q
3
x
1
q
2
/y
1
q
3
/y
3
q
2
/ y
3
x
2
q
3
/y
2
q
2
/y
1
q
1
/ y
1
.q)x,q()x,q(
~
)x),x,q((
~
)xx,q(
~
)xx),x,q((
~
)xxx,q(
~
)xxx),x,q((
~
)xxxx,q(
~
213131121121122
21221121121211
=δ=δ=δδ=δ=δδ=
=δ=δδ=δ
Последним в этой последовательности переходов является переход (q
3
, x
1
), по-
этому
.y)x,q()xxxx,q(
~
31311211
=λ=λ
Функцию ω(q
m
, ξ) – реакцию автомата в состоянии q
m
на входное слово
ξ = x
i1
… x
ik
определим в множестве }){(ExQ
ε
∪ следующим образом:
ω(q
m
, ξ) – не определена, если не определена )',q(
~
m
ξδ ,
где
ikiki
xетxx
ξξξ
′
==
′
−
. .,...
11
.
Иначе, если
)',q(
~
m
ξδ определена, то
ω(q
m
, ξ) = λ(q
m
,
x
i1
) ω( δ( q
m
, x
i1
), x
i2
... x
ik
) = λ(q
m
, x
i1
) λ(q
i2
,
x
i2
) ... λ(q
ik
, x
ik
) = y
i1
... y
ik
,
где q
i2
= δ( q
m
, x
i1
); y
ij
= λ(q
ij
,
x
ij
); j = 2, 3, ..., k; y
i1
= λ(q
m
,
x
i1
).

Страницы