ГЛАВА VIII. РАСПОЗНАВАНИЕ РЕАЛИЗУЕМОСТИ ЗАДАНИЯ И АБСТРАКТНЫЙ СИНТЕЗ КОНЕЧНЫХ АВТОМАТОВ И ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН

§ 8.1. Постановка задачи

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

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

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

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

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

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

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

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

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

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

Всякое «задание на проектируемое устройство» подразумевает установление соответствия между заданными входными и выходными последовательностями. Наиболее просто обстоит дело в том случае, если число заданных входных и выходных последовательностей конечно; при этом термин «задание на проектируемое устройство» приобретает точный смысл: под ним можно понимать перечисление всех заданных последовательностей и соответствий между ними. Этот случай задания рассмотрен в § 8.2.

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

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

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

Таким образом, возникает задача о сужении языка, на котором описывается задание на проектируемую Я-машину. Одному из предложенных языков такого рода — языку регулярных формул — посвящен § 8.4, где в общих чертах показано, как по заданной регулярной формуле синтезируется относительно экономная (в смысле числа состояний) Я-машина, реализующая соответствующее задание. Вопрос о принципиальной возможности синтеза такой машины не возникает, так как сам язык в этом случае позволяет описать только реализуемое задание.