Cтраница 1
Автоматное отображение XS - S-Y задается, как правило, в виде графа переходов Gn S, ( U, ( X, У)), ( U S2), вершины которого взаимно однозначно соответствуют внутренним состояниям автомата, а дуги-переходам между ними, причем каждая дуга взвешена парой векторов ( X, У), при которой этот переход осуществляется. В целях упрощения задания автомата параллельные дуги графа переходов могут склеиваться. В этом случае некоторые компоненты входных и выходных векторов обозначаются символом -, указывающим на то, что при осуществлении данного перехода значение сигнала, приписанного данной компоненте вектора, несущественно для функционирования устройства. У асинхронного автомата каждая дуга графа переходов дублируется в концевой вершине петлей, взвешенной той же парой векторов ( X, Y), что и соответствующая дуга. Для графа переходов синхронного автомата это условие может не выполняться. [1]
Всякое автоматное отображение однозначно определяется соответствующим ему каноническим множеством событий в предположении, что события этого множества отмечены соответствующими буквами выходного алфавита заданного отображения. [2]
Будем называть автоматное отображение и соответствующее ему множество событий соответствующими друг другу. Предложение 2.7 показывает, что автоматные отображения могут задаваться конечными множествами событий. Условимся называть автоматными множества событий, соответствующие автоматным отображениям. [3]
Область определения автоматного отображения удовлетворяет условию полноты, то есть, иначе говоря, вместе с любым содержащимся в ней словом содержит также все начальные отрезки этого слова. Пустое слово всегда входит в область определения отображения. [4]
Теорема 5.1. Всякое частичное автоматное отображение f может быть индуцировано с помощью некоторого абстрактного автомата А. [5]
Однако часто рассмотрения автоматного отображения оказывается недостаточно, необходимо принимать во внимание преобразования автоматов, которые существенно меняют представленные в них отображения, используя определенную внешнюю информацию о природе входных и выходных сигналов. В этих случаях автомат рассматривается как абстрактная модель устройства, выполняющего вычисления по некоторому алгоритму. При этом выходные сигналы играют роль элементарных действий, а входные - условий, распознаваемых в процессе вычислений. Фиксируя для данного автомата указанную интерпретацию его входных и выходных сигналов, получаем объект, названный в этой работе дискретным преобразователем. [6]
Представляет интерес описание автоматных отображений Хц в УП, сохраняющих наряду со значением функции JJL и периоды последовательностей. [7]
Как правило, для автоматных отображений записывают такую таблицу, в которой никакое входное слово не является начальным отрезком какого-либо другого входного слова. Такая таблица называется сокращенной таблицей соответствия. Используя второе условие автомат-ности отображения, от сокращенной таблицы в случае необходимости легко перейти к полной таблице соответствия. Однако при синтезе автоматов наибольший интерес представляют произвольные автоматные отображения, в том числе и с бесконечной областью определения, задание которых невозможно с помощью таблиц соответствия. Удобной формой задания произвольных автоматных отображений является задание их с помощью событий, к рассмотрению которых мы и перейдем. [8]
Очень удобным способом задания произвольного автоматного отображения является задание его с помощью так называемого автоматного множества событий. [9]
Все слова входного алфавита разбиваются автоматным отображением на два класса: на класс допустимых и класс запрещенных слов, в зависимости от того, входят или не входят они в область определения этого отображения. [10]
Доказанное предложение позволяет нам применять термин автоматное отображение ко всякому алфавитному отображению, удовлетворяющему условиям автоматности. [11]
Через фд обозначим ( частичное) автоматное отображение, индуцируемое состоянием а автомата. Если А - инициальный автомат, то ФА - отображение, индуцируемое начальным состоянием. ФА отождествляется с подмножеством множества FX X FY - прямого произведения двух свободных полугрупп. [12]
В случае, когда область определения автоматного отображения ф конечна, его чаще всего принято задавать с помощью так называемой таблицы соответствия. В левой половине этой таблицы выписывают в том или ином порядке входные слова, на которых данное отображение ф задано, а в правой части таблицы - соответствующие им выходные слова. [13]
Заметим, что в отличие от автоматного отображения абстрактный автомат не определяется однозначно соответствующим ему каноническим множеством событий, поскольку одно и то же автоматное отображение может индуцироваться различными автоматами. [14]
Любое однозначное алфавитное отображение можно превратить в автоматное отображение, применяя к этому отображению операцию выравнивания длин слов а операцию пополнения. [15]