ГЛАВА VI. АВТОНОМНЫЙ КОНЕЧНЫЙ АВТОМАТ И АВТОНОМНАЯ ПОСЛЕДОВАТЕЛЬНОСТНАЯ МАШИНА

§ 6.1. Что «могуть делать» автономный конечный автомат и автономная последовательностная машина

Цель этой и последующей седьмой главы состоит в том, чтобы определить возможности конечных автоматов и последовательностных машин, выяснить, «что могут они делать», отделить это от того, что принципиально «не может быть сделано» ни в каком конечном автомате или последовательностной машине. В настоящей главе задача такого рода рассматривается применительно к автономному конетаому автомату. Аналогичной задаче для неавтономного автомата (и П-машины) посвящена следующая глава.

Напомним, что автономным называется конечный автомат, у которого значение переменной под знаком функции F фиксировано, и что из автомата, уравнение которого (см. уравнение )

можно организовать различных автономных автоматов (см. 3.7)

так как символ может совпадать с любым из символов алфавита .

Постоянный символ можно рассматривать как символ-параметр.

Если задать начальный символ , то в силу (6.1) найдем , подставляя в (6.1), определим и т. д. Запущенный при некотором начальном символе автономный конечный автомат может выдавать неограниченную последовательность символов :

Число символов в алфавите конечно и равно . Поэтому в разворачивающейся последовательности символов , выдаваемых автоматом, через конечное число q тактов впервые встретится символ, который ранее уже встречался в этой же последовательности, например символ в последовательности

Тогда, начиная с такта, автомат будет лишь периодически повторять последовательность символов, выданных ранее. В нашем примере эта повторяющаяся далее последовательность подчеркнута:

Из изложенного следует, что автономный автомат, запущенный из любого начального состояния, не позже чем через k тактов начинает периодически повторять одну и ту же последовательность символов длиной не более к.

Если этот же автомат запустить из иного начального состояния, то он также, начиная с некоторого такта, начнет периодически повторять некоторую последовательность символов , причем эта последовательность может не совпадать с последовательностью, которая генерировалась раньше.

Особо выделим случай, когда последовательность состоит лишь из одного символа. Этот случай возникнет, если первый встретившийся в последовательности повторяющийся символ расположен непосредственно следом за таким же символом. Например,

или

Символ, появляющийся в последовательности два раза подряд, назовем равновесным и будем говорить, что автомат достиг равновесия в тот такт, когда впервые появился равновесный символ.

Условие того, что символ равновесный, состоит в выполнении равенства

т. е. в том, что при символ переводится уравнением (6.1) в себя.

Все изложенное очень удобно иллюстрируется на графе автономного автомата.

Рис. 6.1.

Граф содержит к кружков, соответствующих всем возможным символам . К каждому кружку может подходить несколько стрелок, но отходить может только одна. Поэтому, двигаясь вдоль направления стрелок, мы обязательно не более чем за к шагов попадем в один из кружков, пройденных ранее (стрелки образуют цикл — рис. 6.1), либо попадем в кружок, в который отходящая стрелка вновь возвращается (равновесие — рис. 6.2).

Рис. 6.2.

На рис. 6.3 показаны различные примеры графов для .

В случае рис. 6.3, а цикл проходит через все кружки.

В этом случае автономный автомат генерирует периодическую последовательность, состоящую из всех k символов, и начинает выдавать эту периодическую последовательность с первого же такта, если допускать в ней циклическую перестановку символов. От выбора начального состояния зависит лишь порядок символов.

Рис. 6.3.

На рис. 6.3, б показан граф, у которого цикл охватывает лишь 5 кружков, а от всех остальных стрелки ведут к одному из кружков цикла. В этом случае автономный автомат генерирует последовательность длины 5 и, будучи запущен из любого начального состояния, начинает генерировать ее (с точностью до циклической перестановки символов) не более чем через один такт.

В случае графа, показанного на рис. 6.3, в, число тактов, необходимых для начала генерирования периодической последовательности (для выхода на цикл), не более четырех.

На рис. 6.3, г показан пример графа автономного автомата, который в зависимости от выбора начального состояния генерирует одну из трех последовательностей длины соответственно 2, 3 и 5.

Автомат, имеющий граф, показанный на рис. 6.3, д, в зависимости от начального состояния не более чем за три такта достигает равновесия, либо не более чем за один такт переходит на генерирование периодической последовательности длины 4.

Наконец, на рис. 6.3, е показан пример графа автог номного автомата, имеющего три равновесия; в зависимости от начального состояния то или иное равновесие достигается не более чем за два такта.

Если требуется построить автономный автомат, генерирующий периодическую последовательность заданной длины q и удовлетворяющую каким-либо дополнительным условиям в отношении числа тактов, после которых начинается ее генерирование, то задача сводится к построению графа, удовлетворяющего этим условиям. Граф однозначно задает автономный автомат, так как по графу, как это отмечалось уже в гл. III, немедленно восстанавливается его основная таблица.

Пусть, например, требуется генерировать периодические последовательности длины 2, 4 и 6. Выбор генерируемой последовательности должен определяться выбором начального состояния, и в любом случае генерирование последовательности должно начаться не позже чем через один такт после запуска автомата.

В этом случае необходимо иметь .

Если (рис. 6.4), то граф восстанавливается немедленно соединением в циклы любых его двух, четырёх и шести кружков. Если же , например (рис. 6.5), то стрелки, отходящие от узлов, не вошедших в циклы, подводятся к любым узлам циклов.

Рис. 6.4.

Аналогично могут быть поставлены задачи и с учетом возможности менять параметр . Каждому значению соответствует свой автономный автомат, т. е. свой граф. Но все эти автоматы работают в одном и том же алфавите . Поэтому графы всех автономных автоматов, получающихся при изменении параметра , имеют одно и то же число к кружков.

Рис. 6.5.

Пусть, например, как и ранее, требуется, чтобы автомат генерировал периодические последовательности длины 2, 4 и 6. Выбор генерируемой последовательности должен определяться выбором уже не начального символа, а параметра или . Но по-прежнему при любом генерирование последовательности должно начаться не позже чем через один такт после запуска.

Рис. 6.6.

Число k не может быть выбрано меньше, чем длина самой длинной из заданных последовательностей, так как в противном случае ни при каком нельзя было бы получить автономный автомат, генерирующий эту последовательность. Положив, например, , строим граф для (рис. 6.6), замыкая все шесть кружков в цикл. Граф при также содержит тогда шесть кружков, но в цикл надо замкнуть лишь любые четыре из них. Поэтому стрелки от остальных двух кружков подводятся к кружкам цикла (рис. 6.7).

Рис. 6.7.

Наконец, для лишь два кружка замкнуты в цикл, а стрелки от остальных кружков подведены к ним (рис. 6.8).

Рис. 6.8.

Построенные три графа (рис. 6,6, 6.7 и 6.8) задают автомат. Его основная таблица может быть немедленно восстановлена по графам. В случае графов, показанных на рис. 6.6, 6.7 и 6.8, она имеет вид табл. 6.1.

Таблица 6.1

Из приведенного примера ясно, как сконструировать основную таблицу автомата, генерирующего любое конечное число последовательностей , выбираемых как начальным символом, так и параметром .

Переходя к последовательностной машине, надо дополнить автомат выходным преобразователем). Но если автомат периодически выдает последовательность из символов , то и преобразователь периодически выдает последовательность из символов А той же длины. Но в отличие от последовательности из , которая не может содержать двух одинаковых символов, последовательность из на выходе преобразователя может содержать и одинаковые символы. -например, если автомат выдает последовательность , которая потом периодически повторяется, а преобразователь реализует таблицу

то на выходе преобразователя периодически повторяется последовательность .

Если задана требуемая последовательность символов X, то, чтобы синтезировать П-машину, выдающую эту последовательность, сначала синтезируется автомат, выдающий любую последовательность символов , длина которой совпадает с длиной заданной последовательности символов . Затем, выписав эти две последовательности (из символов и из символов одну под другой, немедленно восстанавливаем и таблицу преобразователя. Все эти соображения имеют важные технические следствия.

Если какое-либо техническое устройство охватывается абстракцией «автономный конечный автомат» и если символы характеризуют возможные состояния устройства, то такое устройство может либо достигать равновесия за конечное число тактов, либо периодически повторять конечную последовательность состояний — и не более того. Из изложенного следует также, что, каково бы ни было конечное число наперед заданных последовательностей состояний любой конечной длины, всегда можно синтезировать автомат, генерирующий любую из этих последовательностей выбором начального состояния либо установкой в начальный момент значения параметра, который далее, во время работы автомата, не изменяется.

Чтобы несколько конкретизировать этот вывод, важный для технической реализации автоматов, рассмотрим, этот вопрос подробнее применительно к синтезу двоичной абстрактной структуры, замещающей автономную последовательностную машину. Распространение рассуждений на иные абстрактные структуры потребует после этого лишь кратких замечаний.