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

UptoLike

ВУЗ: 

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

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

Рубрика: 

67
(q
1
, ..., q
k
) состояний всех автоматов А
1
, ..., А
k
. Полученный отдельный набор обозна-
чается q и называется структурным состоянием автомата А. В дальнейшем бу-
дем предполагать, что в результате композиции автоматов, кроме указанных комби-
наций уже имевшихся состояний, других состояний не возникает. Тогда справедливо
следующее условие.
1.5. Число состояний автомата, полученных в результате композиций автома-
тов А
1
, ..., А
n
, равно произведению чисел состояний всех этих автоматов.
4.4. Канонический метод структурного синтеза автомата
4.4.1. Основная задача теории структурного синтеза автоматов
Основной задачей теории структурного синтеза автоматов является нахожде-
ние общих приемов построения структурных схем автоматов на основе композиции
автоматов, принадлежащих к заранее заданному конечному числу типов автоматов.
Более точно эта задача может быть сформулирована следующим образом.
2.1. Пусть задано некоторое конечное множество автоматов в одном и том же
структурном алфавите Z. Назовем эти автоматы элементарными автоматами и пред-
положим, что таких элементарных автоматов имеется неограниченное число экземп-
ляров. Пусть также задан произвольный конечный автомат А в том же самом струк-
турном алфавите Z. Необходимо найти алгоритм, позволяющий по заданному автома-
ту А строить некоторую композицию элементарных автоматов так, чтобы получен-
ный в результате композиции автомат индуцировал отображение, продолжающее
отображение, индуцируемое автоматом А.
Следует отметить, что далеко не при всяком выборе системы элементарных ав-
томатов эта задача имеет решение. Однако, если решение имеется (для произвольно-
го конечного автомата А), то считают, что заданная система элементарных автоматов
структурно полна или может иметь ослабленную структурную полноту.
Система элементарных автоматов ослабленно структурно полна, если для
любого отображения ϕ, индуцируемого конечным автоматом, можно найти такую
композицию элементарных автоматов, что получаемый в результате этой композиции
автомат индуцирует отображение, которое продолжает либо само отображение ϕ, ли-
бо отображение, полученное из отображения ϕ в результате применения к нему опе-
рации выравнивания длин слов. При этом предполагается, что автомат, индуцирую-
щий отображение ϕ, задан в том же структурном алфавите, что и все элементарные
автоматы. Заметим также, что операция выравнивания длин слов, применяемая к ото-
бражению ϕ, являющемуся автоматным отображением, заключается в дописывании
равного числа пустых букв справа к входным словам и слева к выходным словам ото-
бражения ϕ.
В настоящее время почти нет эффективных методов (существенно более про-
стых, чем метод перебора всех вариантов) решения основной задачи структурного
синтеза при любом выборе структурно полных систем элементарных автоматов. Наи-
более часто применяют так называемый канонический метод структурного синтеза
автоматов, пригодный для структурно полных систем элементарных автоматов неко-
торого специального вида.

Страницы