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

UptoLike

ВУЗ: 

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

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

Рубрика: 

34
В момент времени t, отличный от начального, автомат способен воспринимать
входной сигнал x(t) – произвольную букву входного алфавита Х и выдавать соответ-
ствующий выходной сигнал y(t) – некоторую букву выходного алфавита Y.
Закон функционирования абстрактного автомата первого рода задается урав-
нением:
=−=
−=
..., 2, 1,t где x(t)),1),л(q(ty(t)
x(t)),1),д(q(tq(t)
а абстрактного автомата второго рода – уравнением:
==
−=
... ,2 ,1 )),(),(()(
)),(),1(()(
tгдеtxtqty
txtqtq
λ
δ
Вывод: Таким образом, в абстрактной теории автоматов входные и выходные
сигналы рассматриваются как буквы (символы) двух фиксированных для данного ав-
томата алфавитов. Абстрактная теория изучает те переходы, которые претерпевает
автомат под воздействием входных сигналов в дискретные моменты времени, и те
выходные сигналы, которые он при этом выдает.
3.1.2. Понятие об абстрактном автомате и индуцируемом
им отображении
Сущность индуцируемых абстрактным автоматом отображений заключается в
реализации некоторого отображения ϕ из множества слов входного алфавита в мно-
жество слов выходного алфавита.
Отображение ϕ реализуется следующим образом: каждое слово p = x
i1
, x
i2
, …,
x
ik
входного алфавита X = (x
1
, x
2
, …, x
n
) или, более кратко, каждое входное слово, по-
следовательно, буква за буквой, подается на вход данного абстрактного автомата А,
установленного предварительно в начальное состояние. Возникающая таким образом
конечная последовательность входных сигналов x(1) = x
i1
, x(2) = x
i2
, …, x(k) = x
ik
на
основании закона функционирования автомата вызывает появление однозначно
определенной конечной последовательности s = y(1), y(2), …, y(k) выходных сигна-
лов. Эту последовательность будем называть выходным словом, соответствующим
входному слову р.
Относя, таким образом, каждому входному слову р соответствующее ему вы-
ходное слово s, мы получаем искомое отображение ϕ, а именно, s = ϕ(p). Построенное
указанным способом отображение ϕ будем называть отображением, индуцирован-
ным абстрактным автоматом А.
Два абстрактных автомата с общим входным и выходным алфавитами называ-
ются эквивалентными между собой, если они индуцируют одно и то же отображе-
ние множества слов входного алфавита в множество слов выходного алфавита.
Наряду с эквивалентностью важнейшее значение имеет понятие изоморфизма
абстрактных автоматов.
Предположим, что заданы два абстрактных автомата:
А
1
(X
1
, Y
1
, Q
1
, q
1
, δ
1
(q,x), λ
1
(q,x)) и
А
2
(X
2
, Y
2
, Q
2
, q
2
, δ
2
(q,x), λ
2
(q,x))
одного и того же рода. Если для этих автоматов существуют взаимно однозначные
отображения: α – отображающее множество X
1
на множество X
2
;
β – отображающее

Страницы