ГЛАВА IV. АБСТРАКТНАЯ СТРУКТУРА И СЕТЬ

§ 4.1. Общие понятия о замещении последовательностных машин

Рассмотрим две последовательностные машины: машину (рис. 4.1,а), преобразующую символы из алфавита в символы из алфавита , и машину (рис. ), преобразующую символы из алфавита в символы из алфавита . Рассмотрим также два произвольных функциональных преобразователя , реализующих функции

Преобразователь мгновенно и однозначно ставит в соответствие паре символов и из алфавита символ из алфавита преобразователь той же паре символов ставит в соответствие символ из алфавита .

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

Рис. 4.1.

Рис. 4.2.

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

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

Условимся говорить, что машина замещает машину , если можно так подобрать функциональные преобразователи , что для каждого начального состояния машины найдется хотя бы одно начальное состояние машины такое, что при любых входных последовательностях из алфавита система, полученная путем соединения машины и преобразователей по схеме рис. 4.2, отправляющаяся из , и машина отправляющаяся из , выдадут одинаковые выходные последовательности из алфавита . Факт замещения машины машиной будем записывать так:

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

Из факта вообще говоря, не следует, что . В определении замещения существенно то, что выбор преобразователей и начальных состояний не зависит как-либо от того, какова входная последовательность символов . Можно было бы дать иное, более широкое определение понятия замещения, связав выбор преобразователей и начальных состояний с выбором входной последовательности.

Такое расширение понятия замещения нами не рассматривается, хотя и полезно для некоторых задач.

Можно также ввести понятие относительного замещения Я-машин, если множество L допустимых входных последовательностей машины ограничено.

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

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

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

Рис. 4.3.

Этот путь решения задачи будет далее продемонстрирован на примере.

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

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

Приведем теперь пример замещения конечных автоматов. Пусть автомат А имеет диаграмму состояний, показанную на рис. 4.5, а диаграмма состояний автомата В изображена на рис. 4.6. Может ли автомат В замещать автомат А по схеме рис. 4.4. Пусть к автомату В по схеме рис. 4.4 присоединены преобразователи . Преобразователь осуществляет перенумерацию состояний автомата В (т. е. перенумерацию кружков его диаграммы состояний), а преобразователь Ф, осуществляет перенумерацию входных воздействий (т. е. перенумерацию надписей над стрелками у диаграммы состояний).

Рис. 4.4.

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

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

Рис. 4.5.

Рис. 4.6.

Таблица 4.1

Для состояний автомата В работа преобразователя не определена, так как в процессе работы автомата В с преобразователями эти состояния никогда не будут проходиться.

Для них работу преобразователя можно доопределить произвольно, например так, как это показано в табл. 4.2.

Таблица 4.2

Теперь преобразователь построен полностью. Из табл. 4.2 видно, что он удовлетворяет условию однозначности, т. е. задание однозначно определяет .

Займемся преобразователем . Кружки диаграммы состояний автомата А (рис. 4.5) соединяет стрелка с надписью . Кружку согласно табл. 4.2, соответствует кружок диаграммы состояний автомата В (рис. 4.6), а кружку диаграммы рис. 4.5 — кружок диаграммы рис. 4.6. На диаграмме автомата В эти кружки соединяются стрелкой с надписью (т. е. автомат В переходит из второго состояния в пятое под воздействием входа ). Так как в автомате А переход от состояния к состоянию происходит под воздействием , то преобразователь должен ставить в соответствие символу символ .

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

Проверяя затем аналогично все остальные ветви диаграммы состояний рис. 4.5, устанавливаем, что всегда выполняются соотношения

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

Таблица 4.3

Если теперь на диаграмме состояний рис. 4.6 сменить надписи над ветвями в соответствии с табл. 4.3 и перенумеровать состояния согласно табл. 4.2, то диаграмма рис. 4.6 будет в точности частью диаграммы рис. 4.5.

Итак, в рассмотренном случае автомат А замещается автоматом В.

Возможен и иной вариант замещения. Для него вместо табл. 4.2 и 4.3 имеем соответственно табл. 4.4 и 4.5.

Таблица 4.4

Таблица 4.5

Если бы диаграмма состояний автомата В имела вид, показанный на рис. 4.7, а автомат А имел бы ту же диаграмму состояний, что и раньше (рис. 4.5), то замещение автомата А автоматом В было бы невозможно.

Рис. 4.7.

В самом деле, таблица преобразователя в этом случае может быть лишь одной из двух таблиц: табл. 4.6 или табл. 4.7.

Однако преобразователь в обоих случаях неоднозначен, так как в обоих случаях требуется, чтобы и в то же время . Поэтому замещение невозможно.

Таблица 4.6

Таблица 4.7

Разумеется, вывод о невозможности замещения автомата А автоматом В справедлив лишь для схемы замещения, показанной на рис. 4.4, в. Если же замещение производить по схеме рис. 4.2, то. в рассматриваемом случае оно уже оказывается возможным.

Таблица преобразователя при этом имеет вид табл. 4.6. Выход зависит лишь от одного входа , а выход преобразователя зависит уже от двух переменных — , т. е. . Таблица преобразователя имеет вид табл. 4.8.

Таблица 4.8

Говоря выше о «накладывании диаграмм состояний друг на друга», мы под совпадением подразумевали не только совпадение кружков, стрелок и надписей над ними, но и места расположения надписей над стрелками. Иначе говоря, речь шла о замещении автоматов и П-машин автоматами и П-машинами того же типа.

В гл. III было показано, что П-машина типа П — Н всегда может быть, как там говорилось, заменена П-машиной типа П — П. Употребляя термин «заменена», мы имели в виду интуитивное понимание читателем этого термина. Теперь, в свете введенных в этой главе определений, ясно, что в гл. III фактически речь шла о замещении П-машины типа П — Н машинами типа П — П.