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

UptoLike

ВУЗ: 

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

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

Рубрика: 

53
Пример 4
Определим реакцию
)xxxx,q(
21121
=ω автомата Мура, заданного отмеченной
таблицей переходов 3.11.
ω(q
1
, x
2
x
1
x
1
x
2
) = λ(δ(q
1
, x
2
))ω(δ(q
1
,x
2
), x
1
x
1
x
2
) = λ(q
4
)ω( q
4
, x
1
x
1
x
2
) =
= y
2
λ(δ(q
4
, x
1
))ω(δ(q
4
,x
1
), x
1
x
2
) = y
2
λ(q
3
)ω(q
3
, x
1
x
2
) = y
2
y
3
λ(δ(q
3
, x
1
))ω(δ(q
3
, x
1
), x
2
) =
= y
2
y
3
λ(q
5
)ω(q
5
, x
2
) = y
2
y
3
y
3
λ(δ(q
5
, x
2
)) = y
2
y
3
y
3
λ(q
1
) = y
2
y
3
y
3
y
1
.
Таким образом, в автомате Мура выходной сигнал y
i1
=λ (q
m
) в момент време-
ни i
1
не зависит от входного сигнала х
i1
, а определяется только состоянием q
m
. Этот
сигнал y
i1
никак не связан с входным словом, поступающим на вход автомата, начи-
ная с момента i
1
. В связи с этим под реакцией автомата Мура в состоянии q
m
на
входное слово ξ =
1
i
х
2
i
х
...
k
i
х
понимается выходное слово той же длины ω(q
m
, ξ) =
=
2
i
y
3
i
y
...
1k
i
y
+
, но сдвинутое на один такт автоматного времени.
3.4.3. Получение неполностью определенных (частичных) автоматов
Автомат называется полностью определенным, если D
δ
= D
λ
= Q x X, опреде-
лена для всех пар (q
m
, x
j
) ∈ Q x X,
где D
δ
– отображение функции переходов δ;
D
λ
– отображение функции выходов λ.
У полностью определенного автомата области определения функций δ и λ сов-
падают с множеством Q x X – множеством всевозможных пар вида (q
m
, x
f
).
У неполностью определенного, или частичного, автомата функции δ или λ
определены не для всех пар (q
m
, x
f
) ∈ Q x X.
При задании неполностью определенных автоматов табличным способом на
месте неопределенных состояний и выходных сигналов ставится прочерк. Для час-
тичного автомата Мили S
3
(табл. 3.9) реакция автомата
3233212112
yyyy)xxxxx,q( =
ω
.
Черточка на последнем месте означает, что в реакции последний выходной сигнал не
определен. Сама же реакция определена, так как
)xхxxx,q(
~
212112
δ
определена. Од-
нако, для этого же автомата реакция
)xxxxx,q(
222112
ω
будет не определена, так как
не определена функция
)xхxxx,q(
~
222112
δ
.
Можно определить реакцию автомата Мили в состоянии q
m
на входное слово ξ
и через заключительный выход:
)x...x,q(
~
)...xx,q(
~
)x,q(
~
),q(
ik1im2i1im1imm
λλλ=ξω .
3.5. Синтез автоматов по индуцируемым ими отображениям
Одной из наиболее важных задач теории абстрактных автоматов является зада-
ча синтеза конечных автоматов по индуцируемым ими алфавитным отображениям.
Такая задача может решаться так называемым общим методом решения задачи.
3.5.1. Общий метод решения задачи
Абстрактный автомат с входным и выходным алфавитами индуцирует одно-
значное отображение множества слов во входном алфавите (входном алфавитном

Страницы