Cтраница 1
Условия автоматности на первый взгляд очень суживают класс отображений, которые можно задавать с помощью абстрактных автоматов. Хорошо известно, в частности, что требование равенства длин входных и выходных слов не удовлетворяется для большей части алгоритмов, которые должны выполняться теми или иными конкретными автоматсми. Это затруднение, представляющееся на первый взгляд весьма серьезным, в действительности легко устраняется с помощью перекодирования входной и выходной информации на основе весьма простого приема. [1]
Условия автоматности накладывают весьма жесткие ограничения на класс отображений, которые могут быть индуцированы абстрактными автоматами. Большинство алфавитных отображений, с которыми приходится иметь дело на практике - в частности большинство алгоритмов - не удовлетворяют этим условиям. Существует, однако, стандартный прием, позволяющий превратить любое алфавитное отображение в автоматное. К описанию этого приема мы сейчас и переходим. [2]
Основное свойство автоматности [ 61 отображения X - Y состоит в следующем. Тогда, если брать любые конечномерные распределения процесса Y ( t), относящиеся к моментам более ранним, чем т, и вычисленные в предположении, что входной процесс есть X или X, то эти распределения будут совпадать. [3]
Используя четвертое условие автоматности, в таблицу соответствия обычно не включают входные слова, являющиеся начальными отрезками слов, уже включенных в таблицу. Таблицу соответствия, в которой никакое входное слово не является начальным отрезком какого-либо другого входного слова, мы будем называть сокращенной таблицей соответствия. При задании автоматного отображения сокращенной таблицей соответствия его Продолжение на начальные отрезки входных слов, вошедших в таблицу, осуществляется на основании четвертого условия автоматности. [4]
Назовем сформулированные условия условиями автоматности отображения р, а всякое соответствие между словами в алфавитах Ж и, удовлетворяющее этим условиям, - автоматным отображением, или автоматным оператором. [5]
Назовем перефразированные условия условиями автоматности частичного отображения ф, а всякое частичное отображение, удовлетворяющее этим условиям, - частичным автоматным ото-брожением. [6]
На первый взгляд кажется, что условия автоматности накладывают жесткие ограничения на алфавитные отображения, индуцируемые абстрактными автоматами. Например, равенство длин входных и выходных слов для произвольных ( разумеется, однозначных) алфавитных отображений, как правило, не выполняется. Тем не менее любое алфавитное отображение может быть превращено в автоматное отображение с помощью следующего стандартного приема. [7]
Нетрудно проверить, что отображение р, продолженное на начальные отрезки слов, удовлетворяет условию автоматности. [8]
Доказанное предложение позволяет нам применять термин автоматное отображение ко всякому алфавитному отображению, удовлетворяющему условиям автоматности. [9]
Если пополнение ф отображения ф является однозначным, то оно удовлетворяет, очевидно, всем четырем условиям автоматности. [10]
Построенное нами частичное отображение фх между словами в алфавитах 3.i и по самому способу построения удовлетворяет обоим условиям автоматности для частичных отображений и представляет собой, следовательно, искомое частичное автоматное отображение. [11]
Большой интерес представляет проблема нахождения экономного перекодирования отображения, заданного на том или ином алгоритмическом языке ( например, на языке нормальных алгоритмов), с целью превращения его в автоматное соответствие, а также задача построения теории алгоритмов, которые удовлетворяют условиям автоматности и поэтому сокращенно называются автоматными алгоритмами. Один из возможных подходов к теории автоматных алгоритмов развивается в следующем параграфе. [12]
Если отображение ф множества слов в алфавите Ж в множество слов в алфавите 3) задается частичным автоматом, то оно будет, разумеется, лишь частичным отображением, определенным не на всех словах. Однако для него по-прежнему будут выполняться оба условия автоматности при дополнительном предположении, что ф ( /) существует. [13]
В силу способа построения отображения q / слову рг относится в качестве образа некий начальный отрезок gz слова ф ( /), а слову /, - начальный отрезок дг того же слова, имеющий меньшую, чем отрезок д2, длину. Так как д, может рассматриваться в качестве начального отрезка слова 72, то выполнимость четвертого условия автоматности для отображения ф доказана. [14]
Описанный прием преобразования любого частичного отображения в автоматное является общим, однако, именно в силу своей общности, он не всегда приводит к самому экономному ( с точки зрения расходования дополнительных букв) решению. Это обстоятельство особенно легко уяснить на случае, когда само исходное частичное отображение ф удовлетворяло обоим условиям автоматности. Между тем описанный стандартный прием ( который применим, разумеется, и в этом случае) приведет к ненужному увеличению длин исходных слов, участвующих в соответствии. [15]