4.5. Разновидности диагностической задачи с двумя состояниями

Следующая теорема суммирует рассуждения, приведенные в предыдущем параграфе.

Теорема 4.1. Диагностическая задача для автомата, содержащего n состояний, с двумя допустимыми состояниями всегда может быть решена простым безусловным экспериментом длины l, где

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

Рис. 4.4. Автомат

Очевидно, что в никакие два состояния не могут выдать различные выходные символы прежде, чем будет достигнуто состояние n из одного из этих состояний и приложен входной символ а; следовательно, Диагностический эксперимент для и допустимого

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

Диагностическая задача для двух состояний прямо связана со следующей задачей: известно, что данный автомат М является либо автоматом в состоянии либо автоматом в состоянии причем имеются таблицы переходов являются сравнимыми автоматами. Желательно распознать автомат и его начальное состояние. Простым искусственным приемом рассмотрения М как расщепляемого автомата а именно указанная задача может быть перефразирована в следующем виде: известно, что данный автомат таблица переходов которого доступна, находится в одном из состояний Найти это состояние. Эта задача в точности представляет собой диагностическую задачу для автомата и допустимого множества начальных состояний . При задача может быть решена методом, описанным в § 4.4. По теореме 4.1, мы имеем:

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

Как показано на примере автоматов (рис. 4.5), верхняя граница в соотношении (4.2) может быть достигнута в точности для любых В примере предполагается, что (когда , состояние имеет единственную исходящую дугу, отмеченную ) которая ведет к состоянию Прежде всего заметим, что никакие два состояния i в автомате и j в автомате не могут выдать различных выходных символов до тех пор, пока не будет достигнуто состояние 1 из i и j и не будет приложен входной символ . Далее, вычеркнем в пару

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

(см. скан)

Рис. 4.5. Автоматы

Как только это сделано, состояния становятся явно эквивалентными и могут быть заменены одним состоянием, скажем ; состояния

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

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