Cтраница 3
Таковы алгебры неоднородных конечнозначных функций ( их аргументы принимают конечное число значений из своих областей), рекурсивных и частично-рекурсивных функций, алгебры автоматных отображений и ряд других. [31]
Абстрактный автомат А применяется для реализации некоторого отображения р множества слов входного алфавита в множество слов выходного алфавита, при этом Ф называется автоматным отображением, индуцированным абстрактным автоматом А. [32]
Назовем сформулированные условия условиями автоматности отображения р, а всякое соответствие между словами в алфавитах Ж и, удовлетворяющее этим условиям, - автоматным отображением, или автоматным оператором. [33]
Таким образом, частичное отображение /, построенное из произвольного алфавитного отображения f, по самому способу построения удовлетворяет условиям ав-томатности и является частичным автоматным отображением. [34]
Заметим, что в отличие от автоматного отображения абстрактный автомат не определяется однозначно соответствующим ему каноническим множеством событий, поскольку одно и то же автоматное отображение может индуцироваться различными автоматами. [35]
Несмотря на то, что класс регулярных событий охватывает далеко не все бесконечные события, он тем не менее оказывается достаточным для описания всех автоматных отображений, индуцируемых конечными автоматами. [36]
Как известно, класс взаимно однозначных отображений замкнут относительно суперпозиции, класс конечно автоматных отображений тоже замкнут относительно этой операции, алфавитное кодирование - конечно автоматное отображение веса 1 и алфавитные отображения образуют замкнутый подкласс. [37]
В случае, когда отображение у получено из некоторого однозначного алфавитного отображения в результате стандартной операции выравнивания длин слов, пополнение ф этого отображения однозначно и является автоматным отображением. [38]
Построенное нами частичное отображение фх между словами в алфавитах 3.i и по самому способу построения удовлетворяет обоим условиям автоматности для частичных отображений и представляет собой, следовательно, искомое частичное автоматное отображение. [39]
Из предложения 2.1 вытекает, что классы отображений, индуцируемых произвольными ( не обязательно конечными) автоматами Мили и Мура, совпадают между собой: как един, так и другой класс состоят из всех автоматных отображений. Оказывается, что имеет место также совпадение классов отображений, индуцируемых конечными автоматами Мили и Мура. Поскольку в § 1 уже была установлена возможность интерпретации каждого автомата Мура как автомата Мили с тем же самым числом состояний, то для обоснования справедливости высказанного утверждения достаточно доказать следующую теорему. [40]
При совместной работе автомата А с инициальным автоматом В порождается пара последовательностей ( р, q) в алфавитах X и У, где р ф ( q), q ер А ( р) При этом, если автоматы А и В работают бесконечно долго, следует рассматривать естественное распространение автоматных отображений на бесконечные последовательности. [41]
Разумеется, можно задавать автоматное отображение индуцирующим его автоматом. Однако на практике при постановке той или иной задачи, относящейся к синтезу автомата, такой способ задания является конечной целью, а не исходным пунктом. [42]
Будем называть автоматное отображение и соответствующее ему множество событий соответствующими друг другу. Предложение 2.7 показывает, что автоматные отображения могут задаваться конечными множествами событий. Условимся называть автоматными множества событий, соответствующие автоматным отображениям. [43]
В самом деле, построив автомат Мура б, представляющий заданное множество регулярных событий М, мы можем интерпретировать его как автомат Мили А способом, описанным в § 1 настоящей главы. В индуцируют одно и то же автоматное отображение, и следовательно, представляют все события исходного множества М одинаковыми множествами своих выходных сигналов. [44]
Основной задачей абстрактной теории автоматов является установление связей, существующих между автоматами и индуцируемыми ими отображениями. Как было показано в § 2 настоящей главы, произвольное автоматное отображение можно задавать представляемыми этим отображением событиями. В связи с этим возникает задача установления связей между событиями и автоматами. [45]