4.14] ПРОСТЫЕ УСЛОВНЫЕ УСТАНОВОЧНЫЕ ЭКСПЕРИМЕНТЫ 167

..., УИ I О/ на 12 • • • г- Расчленяем каждую реакцию на г подпослгдовательностей так, чтобы они соответствовали расчленению входной последовательности. После каждой выходной подпоследовательности вносим в перечень соответствующее конечное состояние. Полагаем /г= 1. (2) Прилагаем g; к УИ. (3) (а) Если реакцию УИ на 12 • • • можно приписать только одному конечному состоянию в перечне, составленном в (1), то это состояние есть конечное состояние УИ. (б) Если реакцию М на 12 • • можно приписать двум или более различным конечным состояниям в перечне, составленном в (1), то увеличиваем /г на 1 и возвращаемся к (2).

Алгоритм 4.6 может быть продемонстрирован автоматом Л17 и множеством допустимых начальных состояний {1, 2, 3, 4, 5), для которых мы имеем gj = аа и 2 = "-Перечень реакций на ааа, расчлененных, как определено в шаге 1, и соответствующих конечных состояний дан в таблице 4.12. Если оказалось, что начальное состояние есть 1

Таблица 4.12 Расчлененные реакции Л17 на ааа

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

В заключение мы можем сделать следующее утверждение.

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

безусловным экспериментом длины I, может быть решена простым условным экспериментом длины I или меньшей и порядка т - 1 или меньше.

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

4,16. Регулярные безусловные установочные эксперименты

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

Рассмотрим дерево преемников для автомата Men состояниями и множеством допустимых начальных состояний А{М). Пусть b есть ветвь, связанная с Л-группой О, состоящей из а-множеств g, g.....g в которой, по крайней мере, одно а-множество, скажем g-, не является однородным. Если gf содержит г состояний, то оно должно содержать, по крайней мере, два состояния, скажем о и Оу, которые являются (га - г--1)-различимыми. Следовательно, подпуть, начинающийся z b к описывающийся последовательностью (О;, Oj), должен вести к Л-группе О, которая состоит, по меньшей мере, из (и--1)-го о-множества. Следовательно, если О является неоднородной, то всегда может быть найден подпуть длины п-r+l или меньшей, который ведет от О к Л-группе, решение которой превышает решение О. Описываемая таким подпутем подпоследовательность называется регулярной подпоследовательностью О. Таким образом, мы имеем способ, с помощью которого можем проследить установочный путь в любом заданном

дереве преемников и, следовательно, построить jCTanOBOMHyro последовательность для любого М и А(М).

Алгоритм 4.7. Заданы автомат М и его множество допустимых начальных состояний А(М); требуется найти установочную последовательность для М и А(М). (1) Пусть А(М) является Oq. Полагаем k = 0. (2) (а) Если О/, не является однородным, то определим регулярную подпоследовательность, скажем j,, для О;,. Пусть Г;-преемником О/, является O/i. Увеличиваем /г на 1 и возвращаемся к (2). (б) Если 0, однородно, то 01 . .. есть установочная последовательность для М и А(М).

Так как решение А (Ж) есть 1 и так как решение любой Л-группы не может превышать числа допустимых состояний т, то число подпоследовательностей, производимых алгоритмом 4.7, не превышает т- 1. Для автомата с п состояниями длина минимальной диагностической последовательности для любой пары состояний не может превосходить п-1; следовательно, длина каждой подпоследовательности в установочной последовательности, выданная алгоритмом 4.7, не может превосходить п - 1. Таким образом, мы имеем следующую теорему.

Теорема 4.12. Установочная задача для автомата с п состояниями и т допустимыми состояниями всегда может быть решена с помощью простого безусловного эксперимента длины I, где

/<(га -1)(7?г-1). (4.12)

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

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

lLim-l). (4.13)

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