§ 4.3. Сеть

Введем в рассмотрение простейший конечный автомат, для которого уравнение (4.1) имеет вид

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

Возвращаясь к автомату типа вводя новую переменную (алфавит совпадает с алфавитом ), заменяем (4.1) соотношениями

Такое соотношение уже было рассмотрено в § 3.3. Теперь будем считать, что первое соотношение в (4.11) определяет мгновенно действующий преобразователь символов в символы , а второе — определяет задержку. Поэтому соотношения (4.11) могут быть представлены схемой, показанной на рис. 4.8, где, как и далее на схемах, задержка обозначена кружком.

Рис. 4.8.

Рассмотрим теперь какую-либо абстрактную структуру автомата, например автомат типа , т. е. совокупность соотношений вида (4.2)

Каждое соотношение в этой системе, например

само может рассматриваться как совокупность задержки

и функционального преобразователя

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

Рис. 4.9.

Располагая несколькими абстрактными структурами, можно строить новые абстрактные структуры, «соединяя» их между собой.

Говоря о соединении автоматов друг с другом, мы имеем в виду отождествление выходных символов одного автомата с входными символами другого автомата.

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

Рис. 4.10.

Пусть даны, например, две абстрактные структуры: структура А

(4.14)

и структура Б

(4.15)

Дополним (4.14) и (4.15) уравнениями трех преобразователей

Здесь дополнительные нитки входа преобразователей. На рис. 4.10 показано схематически соединение структур А и Б с помощью этих трех преобразователей.

Уравнения (4.14), (4.15) и (4.16), рассмотренные совместно, вновь образуют некоторую абстрактную структуру. Действительно, подставляя (4.16) в (4.14) и (4.15), получаем систему из семи рекуррентных соотношений с координатами и нитками входа , из, того типа, который мы назвали выше «абстрактная структура».

Любую совокупность конечного числа рекуррентных соотношений типа (4.2), дополненных уравнениями преобразователей, выражающих некоторые из входов через координаты, назовем сетью.

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

Чтобы получить для сети систему соотношений типа (4.2), надо использовать уравнения преобразователей для исключения входных переменных, на которые воздействуют преобразователи.

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

Назовем сетью задержек сеть, содержащую только задержки, связанные через функциональные преобразователи. Из изложенного выше следует, что любая абстрактная структура и любая сеть представимы сетью задержек. Это было показано на рис. 4.9. Такое представление не единственно в том смысле, что всякая сеть задержек замещает автомат, а для каждого автомата, как было указано в предыдущем параграфе, может быть построено множество замещающих его абстрактных структур.

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

Среди сетей задержек выделим подкласс сетей без петель. Сеть задержек называется сетью без петель, если, перемещаясь по сети от любой из задержек вдоль направления воздействия (вдоль стрелок на схеме типа рис. 4.5), мы не можем достигнуть вновь исходной задержки. На рис. 4.11 показан пример сети без петель, а на рис. 4.12 — сети, содержащей петли.

Рис. 4.11.

Рис. 4.12.

Важным примером сети без петель служит сеть, составленная из q последовательно соединенных друг с другом задержек (рис. 4.13). Если входы и выходы задержек определены на разных алфавитах, то между задержками включаются преобразователи (рис. 4.14).

Построенную так сеть назовем линией задержки. Линия задержки, как и всякая сеть, есть конечный автомат. Но если обращать внимание лишь на символы на ее входе и на ее выходе, то символ будет определяться символом , но не в предыдущий такт, a q тактов назад:

В том же случае, когда входные и выходные символы всех задержек берутся из одного и того же алфавита, символ совпадает с символом , появляющимся q тактов назад:

Вернемся теперь к схеме, показанной на рис. 4.8, но заменим в этой схеме задержку на линию задержки (рис. 4.15). Вместо соотношений (4.11) получим тогда

Рис. 4.13.

Рис. 4.14.

Исключая , получаем

а исключая из (4.17) не , находим

Можно включить линию задержки и на входе преобразователя. Тогда вместо соотношений (4.17) получаем

или, исключая ,

Заметим теперь, что если бы мы символы приписывали состоянию всей системы, учитывая выходы всех задержек, то, разумеется, в момент зависело бы лишь от в момент . Поступая же так, как это было описано выше, то есть приписывая символ лишь выходу последней задержки, мы в этом же автомате реализуем соотношение (4.19). Именно это мы имели в виду, когда, вводя в гл. III понятие о конечном автомате, говорили, что запись автомата в форме соотношения (3.5)

охватывает и тот случай, когда символ зависит от символов конечное число q тактов назад.

Рис. 4.15.

Теперь, когда введены понятия «задержка» и «сеть», вернемся вновь к вопросу о соотношений между автоматами и последовательностными машинами типа П — П и П — Н. Для этого рассмотрим схему рис. 4.8, описываемую уравнением (4.11). Как уже говорилось в гл. III, уравнения (4.11) приводят к описанию автоматов типа П — П или П — Н в зависимости от того, исключается ли из уравнений (4.11) переменная или к. На схеме рис. 4.8 этому соответствует рассмотрение в качестве выхода переменной и (П — П автомат) или (П — Н автомат). На рис. 4.16,а, б показаны соответствующие схемы.

Рис. 4.16.

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

Рис. 4.17.

Напомним, что машина типа П — Н всегда может быть замещена машиной типа П — П. Для замещения следовало сменить лишь преобразователь . Однако неверно обратное утверждение, что одной лишь сменой выходного преобразователя машина типа П — П может быть замещена машиной типа П — Н. Теперь, когда мы владеем методами задания автоматов с помощью таблиц и ввели схемы, показанные на рис. 4.16 и 4.17, мы можем показать это на примере.

Пусть, например, задана последовательностная машина типа П —П (рис. 4.17, а) таблицами преобразователя F (табл. 4.13) и преобразователя Ф (табл. 4.14).

Таблица 4.13. Преобразователь F

Таблица 4.14. Преобразователь Ф

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

Рассмотрим, например, клетку табл. 4.14 для Ф, стоящую на пересечении первой строки и первого столбца. В нее вписан символ В табл. 4.13 преобразователя F в такой же клетке вписан символ . Поэтому символ впишем в таблицу нового преобразователя в клетку, стоящую на пересечении первого столбца и третьей строки (табл. 4.15).

Таким образом, могла бы быть построена и вся эта таблица.

Однако попробуем повторить процедуру, рассмотрев теперь в табл. 4.14 старого преобразователя Ф клетку, находящуюся в первом столбце и второй строке. В нее вписан символ , а в табл. 4.13 преобразователя F автомата в такой же клетке вписан, как и раньше, символ .

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

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

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

Таблица 4.15. Преобразователь Ф*

Доказательство. Докажем сначала первое утверждение теоремы. Пусть дана последовательностная машина, описываемая уравнениями

Построим сеть, состоящую из двух конечных автоматов и заданную уравнениями

и зададим выходной преобразователь сети

где алфавиты совпадают с алфавитами соответственно; алфавит отличается от добавлением одного символа функция Ф в (4.26) совпадает с соответствующей функцией в (4.23) на всех парах символов из и не определена (или задана как угодно) при функция в (4.24) совпадает с F в (4.22) при всех сочетаниях символов, не содержащих 20, а при сочетаниях, содержащих . Уравнения (4.24) и (4.25) описывают конечный автомат А, состояния которого кодируются парой символов , а уравнение (4.26) задает выходной преобразователь этого автомата. Каждому начальному состоянию последовательностной машины П сопоставим такое начальное состояние автомата А, при котором

При из (4.24) следует, что . При символ не может появиться, и для этих моментов в (4.24) можно заменить на F, откуда

Вводя новую переменную и учитывая (4.24), можно написать

причем . Уравнения (4.22), (4.29) и начальные условия совпадают, в силу чего для любого

Но , откуда

Подставляя (4.25) и (4.30) в (4.26) и сравнивая с (4.23), получаем

что и доказывает первое утверждеиие теоремы.

Докажем второе утверждение. Пусть задан конечный автомат А

с выходным преобразователем

Сопоставим этому автомату последовательностную машину П

где алфавиты совпадают. Каждому начальному состоянию автомата А поставим в соответствие начальное состояние машины П. Поскольку уравнения (4.31), (4.33) и соответствующие начальные состояния совпадают, то для всех

Подставляя (4.35) в (4.34) и учитывая (4.31) и (4.32), получим для всех

что и доказывает второе утверждение теоремы. Таким образом, теорема доказана полностью.

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