Деление минимальной диагностической последовательлости на подпоследовательности выполняется следующим образом. Пусть есть /г-я подпоследовательность и пусть 0 представляет собой Л-группу, к которой ведет путь, описываемый 12 ••• ft- обозначим А{М) через Oq. Тогда есть подпоследовательность, описываемая подпутем, который ведет от Oj i к первой Л-группе, которая содержит, по крайней мере, одно более простое а-множество, чем 0 1. Так как рещение Oq равно 1 и так как число а-множеств в Л-группе не может превышать мощности т, соответствующей А{М), то число подпоследовательностей, полученных таким образом, не может превышать т - 1. Так, например, автомат Л17 на рис, 4.3 и множество допустимых начальных состояний {2,3,4,5) дают Оо= {2, 3, 4, 5), Oi={l), {2), {5,1), 02= {1), {1), {2), {1); следовательно, 1 = 00 и 2 = (см. рис. 4,7). После того как определены подпоследовательности, условный эксперимент может быть выполнен следующим образом.

Алгоритм 4,3. Даны автомат М, его множество допустимых начальных состояний Л(УИ) = {а;, а,......а

и разделенная на части диагностическая последовательность 12 • • • требуется распознать начальное состояние М с помощью простого условного эксперимента. (1) Составим

перечень реакций Ma, Ma,...... \im i2---r-

В соответствии с разделением входной последовательности разделим каждую реакцию на г подпоследовательностей. Пусть k=\. (2) Приложим j к М. (3) (а) Если реакция М на 12 • • • является свойственной только одному состоянию в перечне, составленном в (1), то это состояние есть начальное состояние М. (б) Если реакция М на 12 ••и является свойственной двум или более состояниям в перечне, составленном в (1), то увеличим /г на 1 и возвратимся к (2).

Алгоритм 4.3 может быть продемонстрирован на примере автомата Л17 и множества допустимых начальных состояний {2, 3, 4, 5), для которых мы имеем i = aa и 2- В таблице 4.8 дан перечень реакций на последовательность ааа, разделенную, как сказано в шаге 1. Если оказалось, что начальным состоянием Л17 является 2, то реакцией является 00, что может быть свойственно только состоянию 2; следовательно, в данном случае диагностический эксперимент требует

4.9]

ПРОСТЫЕ УСЛОВНЫЕ ДИАГНОСТИЧ, ЭКСПЕРИМЕНТЫ

Таблица 4,8

Расчлененные реакции А\1 на ааа

голько двух ВХОДНЫХ символов. Если оказалось, что начальным состоянием является 5, то реакция на ааесть 10, что не может быть свойственно одному только состоянию 5 (на основе этого ответа начальным состоянием может быть или 4, или 5), и, следовательно, для того чтобы завершить эксперимент, требуется вторая последовательность.

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

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

Хотя из решения диагностической задачи для т состояний путем проведения простого безусловного эксперимента следует решение путем проведения простого условного эксперимента, обратное неверно. Имеются случаи, когда начальное состояние не может быть распознано никаким простым безусловным экспериментом, но может быть распознано простым условным экспериментом. Примером служит автомат А2\ на рис, 4.10 и множество допустимых начальных состояний {1, 2, 3, 4). Ясно, что любая минимальная диагностическая последовательность для данной задачи должна начинаться с а. Любая последовательность, начинающаяся с аа, дает одинаковые реакции, если Л21 находится в состоянии 1 или 2; любая последовательность, начинающаяся с ар, дает одинаковые реакции, если Л21 находится в состоянии 3 или 4. Следовательно, не существует последовательности, реакции на которую всех четырех допустимых состояний являются различными. Однако если прикладывается а и затем наблю-

дается реакция, то имеется возможность определить, находится начальное состояние в {1, 2) (когда реакция равна 0) или в {3, 4) (когда реакция равна 1). Если найдено, что начальное состояние находится в (1, 2), то может быть приложен символ р, который дает О, если начальное состояние есть 1, и 1, если начальное состояние есть 2; если найдено, что начальное состояние находится в {3, 4), то может быть приложен символ а, который дает 1, если начальное состояние

(ar/ff) V (a/rj V (fi/Oj

Рис, 4.10. Автомат А2\.

есть 3, и О, если начальное состояние есть 4. Таким образом, начальное состояние может быть распознано с помощью простого условного эксперимента порядка 2 и длины 2. В заключение имеем следующую теорему.

Теорема 4.4. Каждая диагностическая задача для т состояний, которая может быть решена с помощью простого безусловного эксперимента длины I, может быть также решена с помощью простого условного эксперимента длины I или меньше и порядка т - 1 или меньше. Имеются диагностические задачи для т состояний, которые не могут быть решены с помощью простого безусловного эксперимента, но могут быть решены с помощью простого условного эксперимента.

Условный эксперимент, описанный алгоритмом 4,3, по существу, является безусловным экспериментом со спо-