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

UptoLike

ВУЗ: 

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

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

Рубрика: 

38
Пусть ϕ – произвольное (как правило, частичное) отображение множества слов
в (конечном) алфавите Х в множество слов в (конечном) алфавите Y. Обозначим че-
рез Р область определения этого отображения. Будем применять к отображению ϕ две
операции.
Первая операция – выравнивания длин слов (операция выравнивания).
Ее суть: во входной и выходной алфавиты отображения ϕ (т. е. Х и Y) добавляется
по одной новой букве, которые будем называть пустыми и обозначать через α и β.
Каждому слову р из Р приписывается справа m
p
экземпляров букв α, а к его об-
разу q = ϕ(p) приписывается слева n
q
экземпляров букв β так, чтобы длины полу-
ченных в результате приписывания новых букв словам р
1
и q
1
совпали.
Далее строится новое отображение ϕ
1
некоторого множества Р
1
, слов в алфави-
те Х U(α) в множества слов в алфавите Y U (β), которое переводит друг в друга слова
р
1
и q
1
, полученные в результате выравнивания длин слов р и q соответственно: ϕ
1
(р
1
)
= q
1
(р – пробегает при этом все множество P). Условимся считать, что отображение
ϕ
1
, получается из отображения ϕ с помощью операции выравнивания. Существует не-
которая стандартная операция выравнивания, при которой отображение ϕ
1
, однознач-
но определяется отображением ϕ и присоединенными пустыми буквами α и β. Суть
ее в том, что число m
p
пустых букв α, приписываемых справа к произвольному слову
р из области определения отображения ϕ, принимается равным длине слова q = ϕ(p), а
число n
q
пустых букв β, приписываемых слева к слову q, принимается равным длине
слова р.
Вторая операция применяется только к выравниванию алфавитных отображе-
ний ϕ, т. е. к таким отображениям у которых длины входных и соответствующих им
выходных слов равны между собой. Сущность этой операции – операции пополне-
ния отображения ϕ, заключается в распространении отображения ϕ на начальные от-
резки слов.
Если s – произвольный начальный отрезок любого слова р из области опреде-
ления отображения ϕ, то полагаем ϕ(s) равным начальному отрезку слова ϕ(p), т. е.
имеющему длину s.
В результате применения операции пополнения к произвольному выровнен-
ному алфавитному отображению ϕ возникает новое отображение ϕ
1
область опреде-
ления которого удовлетворяет условию полноты. Условимся называть это отображе-
ние пополнением отображения ϕ.
Если пополнение ϕ
1
отображения ϕ является однозначным, то очевидно, что
оно удовлетворяет всем четырем условиям автоматности.
3.2.2. Представление событий в автоматах
Основной задачей абстрактной теории автоматов является установление связей,
существующих между автоматами и индуцируемыми ими отображениями. Произ-
вольное автоматное отображение можно задавать событиями, которые соответствуют
этим отображениям.
Рассмотрим как устанавливаются связи между событиями и автоматами. Для
этого используем следующие определения:
1. Для произвольного автомата
А множество S
y
всех входных слов, вызываю-
щих появление выходных слов, которые оканчиваются одной и той же буквой (вы-

Страницы