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

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

Задано конечное число лент (имеющих, быть может, разные, но конечные длины) с незаполненной строкой для . Так, например, могут быть заданы четыре ленты (табл. 8.1 — 8.4).

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

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

Таблица 8.1

Таблица 8.2

Таблица 8.3

Таблица 8.4

В приведенном примере, когда заданы четыре ленты, представленные в табл. 8.1 -8.4, такое доопределение означало бы, что синтезируемая П-машина должна иметь, например, ленты, указанные в табл. 8.5, 8.6 и 8.7.

Такты, начиная с которых появляется символ на этих таблицах отделены жирной линией.

Таблица 8.5

Таблица 8.6

Таблица 8.7

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

Рассмотрим, например, следующие две ленты (табл. 8.8 и 8.9). Ясно, что не существует П-машины, имеющей обе эти ленты, так как она должна была бы, исходя из одного и того же начального состояния , после появления входной последовательности выдать в третьем такте в соответствии с первой лентой (табл. 8.8) символ , а в соответствии со второй лентой (табл. 8.9) — символ , что противоречит самому определению последовательностной машины как машины детерминированной.

Задания такого рода назовем противоречивыми.

Таблица 8.8

Таблица 8.9

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

Так, в приведенном выше примере двух противоречащих лент (табл. 8.8 и 8.9) выделение отрезков таково:

Рисунок (см. оригинал)

Здесь противоречие выявляется для отрезков лент, начиная с 3-ого такта.

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

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

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

б) Построением автомата с выходным преобразователем, который представляет определенные события, «записанные» в заданных лентах. Для этого надо по заданным лентам выписать множество всех входных последовательностей, которые приводят к появлению на выходе символа множество входных последовательностей, приводящее к появлению символа , и т. д. После этого надо по методам гл. VII построить автомат I, представляющий определенное событие появлением на выходе символа 1 (из двоичного алфавита , автомат II, представляющий определенное событие появлением на выходе символа 1, и т. д., и выходы этих автоматов подвести к преобразователю, который выдает на своем выходе символ когда появилась 1 на первом входе в преобразователь, символ , когда появилась 1 на втором входе, и т. д.

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

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

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

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

Мы опишем один прием такого рода.

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

Подготовим для заполнения форму основной таблицы автомата и таблицы преобразователя.

Поскольку число состояний нам пока неизвестно, число строк в этих таблицах не определено и мы введем пока лишь одну строку — для хо (табл. 8.12 для автомата и табл. 8.13 для преобразователя).

Таблица 8.10

Таблица 8.11

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

Таблица 8.12. Автомат

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

Начнем с рассмотрения первой ленты (табл. 8.10). В строке первая клетка заполнена символом в соответствии с заданием. При заполнении второй клетки строки этой ленты ничто не препятствует вписать в нее тот же символ .

Этот же символ вписываем также в соответствующую клетку таблицы автомата. В соответствующие клетки и таблицы преобразователя вписываем символ (в соответствии с первым и вторым столбцами табл. 8.10).

Замечаем, что ничто не мешает нам этот же символ вписать теперь в третий столбец ленты (табл. 8.10) и в соответствующие клетки табл. 8.12 и 8.13. В результате получаем заполнение ленты и таблиц, показанное в табл. 8.14 - 8.16.

Таблица 8.14. Лента

Таблица 8.15. Основная таблица автомата

Таблица 8.16. Таблица преобразователя

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

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

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

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

Заполненные таким образом ленты рассматриваемого примера и соответствующие таблицы автомата и преобразователя имеют вид табл. 8.17 — 8.20.

Таблица 8.17. Первая лента

Таблица 8.18. Вторая лента

Таблица 8.19. Основная таблица автомата

Таблица 8.20. Таблица преобразователя

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

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

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

Таблица 8.21. Первая лента

Таблица 8.22. Вторая лента

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

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

Теперь обращаемся ко второй ленте. Сочетание уже встречалось в третьей клетке первой ленты, поэтому с точки зрения таблицы автомата мы можем вписать во вторую клетку второй ленты только и не что иное. Но вместе с тем вписать мы не можем, так как получаем противоречие в таблице преобразователя. У нас нет иного выхода, кроме как вернуться к третьей клетке первой ленты и заменить ранее вписанный символ на символ . Это позволит нам продолжать заполнение второй ленты, не меняя ничего в первой ленте. Далее можно продолжать заполнение второй ленты, ликвидируя возникающие противоречия так, как это делалось при заполнении первой ленты. В рассматриваемом примере новых состояний (помимо введенных ранее ) вводить не придется.

Заполненные для этого примера таблицы имеют вид табл. 8.23 — 8.26.

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

Таблица 8.23. Первая лента

Таблица 8.24. Вторая лента

Таблица 8.25. Основная таблица автомата

Таблица 8.26. Таблица преобразователя

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

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

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

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

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

2) Последним тактам заполненной части каждой из лент соответствуют такие пары символов (), которые определяют в таблице автомата незаполненную еще клетку.

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

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

Таблица 8.27. Первая лента

Таблица 8.28. Вторая лента

Таблица 8.29. Основная таблица автомата

Таблица 8.30. Таблица преобразователя

Заполнения в следующих трех примерах не являются правильными.

Пример 1 (табл. 8.31-8.34)

Таблица 8.31. Первая лента

Таблица 8.32. Вторая лента

Таблица 8.33. Основная таблица автомата

Таблица 8.34. Таблица преобразователя

Пример 2 (табл. 8.35-8.38)

Таблица 8.35. Первая лента

Таблица 8.36. Вторая лента

Таблица 8.37. Основная таблица автомата

Таблица 8.38. Таблица преобразователя

Пример 3 (табл. 8.39 — 8.41)

Таблица 8.39. Первая лента

Таблица 8.40. Вторая лента

Таблица 8.41. Третья лента

Неправильность заполнения в примерах 1—3 обусловлена соответственно нарушением условий 1), 2) и 3) приведенного определения термина «правильное заполнение».

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

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

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

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

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

2. Обращаясь к таблице автомата, дополненной теперь новой клеткой в соответствии с п. I, выясняем, нельзя ли продвинуть далее заполнение первой ленты (без того чтобы заполнять новые клетки таблицы автомата).

Если это возможно, продолжаем заполнять ленту, следя за тем, не вступаем при этом в противоречие с таблицей преобразователя. Далее: а) если таких противоречий нет, то продолжаем заполнение ленты до тех пор, пока не попадаем в Пустую клетку таблицы автомата или пока первая ленга не заполнится целиком, после чего переходим к п. 3 алгоритма; б) если противоречие с таблицей преобразователя получается, то возвращаемся к клетке первой ленты, в которую мы к концу п. 1 алгоритма вписали символ , отказываемся от символа , стираем его в таблицах автомата и преобразователя, стираем также записи, которые мы внесли согласно п. 1, и продолжаем поиск подходящего символа в соответствии с п. 1 алгоритма, начиная перебор символов с символа За конечное число шагов мы перейдем к п. 3 алгоритма, так как, если подходящий символ не будет найден среди символов , то будет вписан новый символ .

3. Допустим, что в результате применения п. 1 и 2 алгоритма мы остановились на символе .

Возвращаясь к правильному заполнению, от которого мы начали применение алгоритма, обратим внимание на пару символов в последнем заполненном столбце первой ленты и выясним, встречаются ли такие же пары в последних заполненных столбцах каждой из остальных лент. Если не встречаются, переходим к п. 4 алгоритма. Если же встречаются, то в каждой из лент, где последняя пара совпадает с последней парой первой ленты, надо продвинуть заполнение далее, пользуясь таблицей автомата так же, как в п. 2. При этом: а) может случиться, что заполнение всех таких лент будет доведено до конца (т. е. до попадания в незаполненную клетку таблицы автомата или до полного заполнения ленты) — тогда переходим к п. 4 алгоритма, и б) может случиться, что в процессе заполнения этих лент мы придем в противоречие с таблицей преобразоватнля.

Тогда возвращаемся к п. 1 алгоритма, отказываемся от символа , стираем все записи, вызванные этим символом, и продолжаем поиск подходящего символа в соответствии с п. 1, но начиная с символа . За конечное число шагов мы перейдем к п. 4 алгоритма, так как во всяком случае к нему приводит вписывание символа .

4. Проверяем, является ли полученное заполнение лент правильным с точки зрения третьего условия правильности заполнения.

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

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

Таблица 8.42. Первая лента

Таблица 8.43. Вторая лента

Таблица 8.44. Третья лента

В результате шестикратного применения алгоритма в этом примере получается заполнение лент, показанное в табл. 8.45-8.47, и синтезируется основная таблица автомата (табл. 8.48) и преобразователь (табл. 8.49).

Таблица 8.45. Первая лента

Таблица 8.46. Вторая лента

Таблица 8.47. Третья лента

Таблица 8.48. Основная таблица автомата

Таблица 8.49. Таблица преобразователя

Заметим, что этот же алгоритм решает задачу и в том случае, когда условия синтеза более легкие: задано конечное число лент конечной длины и требуется построить Я-машину, которая реализует эти ленты, но уже не обязательно исходя из одного и того же начального состояния. Более того, в этом случае не возникает необходимость проверять, противоречиво ли задание, и начальное правильное заполнение выписывается сразу соответствующим выбором подходящих начальных состояний для каждой ленты.

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

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