Главная > Методы обработки данных > Введение в теорию конечных автоматов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.9. Простые условные диагностические эксперименты

Рассмотрим в диагностическом дереве для М и путь, который ведет к А-группе О, содержащей простое -множество например (сама О не обязательно является простой, так как она может содержать другие непростые -множества). Если этот путь описывает входную последовательность то А(М) должно содержать состояние, например преемником которого по отношению к является состояние Так как множество в О является одноэлементным, то реакция на по лемме 4,2, не может быть приписана никакому состоянию из ), за исключением Следовательно, если случайно является истинным начальным состоянием М, то его можно распознать входной последовательностью, которая не обязательно описывается диагностическим путем. Используя этот факт, можно применять минимальные диагностические последовательности по частям, а не целиком, в надежде, что начальное состояние таково, что его можно распознать с использованием лишь части всей последовательности. Эта схема составляет решение диагностической задачи для т. состояний с помощью простого условного эксперимента.

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

Алгоритм 4,3. Даны автомат М, его множество допустимых начальных состояний и разделенная на части диагностическая последовательность требуется распознать начальное состояние М с помощью простого условного эксперимента. (1) Составим перечень реакций на . В соответствии с разделением входной последовательности разделим каждую реакцию на r подпоследовательностей. Пусть . Приложим к М. (3) (а) Если реакция М на является свойственной только одному состоянию в перечне, составленном в (1), то это состояние есть начальное состояние М. (б) Если реакция М на является свойственной двум или более состояниям в перечне, составленном в (1), то увеличим k на 1 и возвратимся к (2).

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

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

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

Таблица 4.8. Расчлененные реакции

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

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

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

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

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

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

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

Рис. 4.11. Диагностическое дерево для и множества допустимых начальных состояний {1, 2, 3, 4}.

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

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

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

Рис. 4,12. Пути для простого условного диагностического эксперимента.

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

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

Теорема 4.5. Если диагностические задачи для автомата с n состояниями и m допустимыми состояниями вообще могут быть решены путем проведения простого условного эксперимента, то они могут быть решены

с помощью простого условного эксперимента длины l, где

Для того чтобы определить, может ли быть реализован простой условный эксперимент для заданных и Л (М), определяют сначала, существует ли требуемое множество путей. Если это так, то составляют перечень всех возможных совокупностей правил для выбора входной последовательности. Если существует совокупность правил, которые выполняют оговоренные выше условия (1), (2) и (3), то такой эксперимент существует, и эта совокупность может быть использована для его выполнения. Если совокупность правил, удовлетворяющая этим условиям, не существует, то диагностическая задача для М и А (М) не может быть решена с помощью простого условного эксперимента. По теореме 4.4, из этого следует, что задача не может быть решена никаким простым экспериментом — безусловным или условным.

Чтобы убедиться в том, что имеются случаи, когда диагностическая задача не может быть решена никаким простым экспериментом — безусловным или условным, рассмотрим автомат на рис. 4.10 и множество допустимых начальных состояний Любая последовательность или подпоследовательность, начинающаяся с а, заставляет состояния 5 и 6 перейти в состояние 9 с одинаковыми реакциями; любая последовательность или подпоследовательность, начинающаяся с p, заставляет состояния 7 и 8 перейти в состояние 10 с одинаковыми реакциями. Следовательно, уже после приложения первого входного символа (для того чтобы начать безусловный или условный эксперимент) нет возможности когда-либо различить состояние 5 и 6 или состояние 7 и 8. Таким образом, мы имеем следующую теорему.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление