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

4.10. Кратные безусловные диагностические эксперименты

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

вообще говоря, нет способа сознательно восстановить начальное состояние для того, чтобы провести новый эксперимент, когда оказалось, что предыдущий эксперимент неудачен. Таким образом, при проведении простых экспериментов полезная информация, которую дает неудающийся эксперимент, никогда не может быть использована для проведения дальнейших экспериментов, так как в то время, когда информация становится доступной, начальное состояние больше нельзя распознать. Если имеется достаточное число экземпляров данной машины, то можно провести ряд экспериментов, каждый из которых сам по себе недостаточен для того, чтобы решить диагностическую задачу, но в совокупности они дают достаточную информацию для того, чтобы распознать начальное состояние. Например, мы пришли к заключению, что нет простого эксперимента, который решает диагностическую задачу для автомата представленного на рис. 4.10, и множества допустимых начальных состояний (5, 6, 7, 8). Однако если имеются два экземпляра то решение может быть достигнуто следующим образом. Приложим к первому экземпляру и p — ко второму экземпляру. Если реакция первого экземпляра есть , то начальное состояние есть 8; если реакция есть 10, то начальное состояние есть 7; если реакция есть 00, то начальное состояние есть либо 5, либо 6. В последнем случае реакция второго экземпляра есть 0, если начальное состояние есть 5, и 1, если начальное состояние — 6. Таким образом, диагностическая задача для и множества допустимых начальных состояний может быть решена кратным экспериментом кратности 2 и длины 3.

В данном месте полезно представить следующую теорему.

Теорема 4.7. В минимальном автомате с состояниями любое множество r состояний содержит, по меньшей мере, два состояния, которые являются -различимыми.

Доказательство. По лемме 3.9, число состояний в каждом классе минимального автомата с n состояниями не превышает n — k. Следовательно, число состояний в каждом классе не превышает . Следовательно, по меньшей мере, два состояния в множестве r состояний должны находиться в двух различных

классах и, следовательно, являются -различимыми.

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

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

путем построения уровня на основе построенного уровня. Так как множества представленные на уровне, являются -множество то отсюда следует, что высота дерева не может превышать . К тому же дерево должно давать в точности т. оконечных ветвей — по одному на каждое допустимое состояние.

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

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

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

В качестве примера на рис. 4.13 показано дерево кратного эксперимента для автомата (рис. 4.3) и множества допустимых начальных состояний . Начальная ветвь представляет , которое есть заданное множество допустимых начальных состояний. Парой

состояний использованной для разбиения является . В данном случае пара состояний выбрана таким образом, чтобы она дала кратчайшее возможное (однако это правило выбора в данном методе несущественно). Выбор можно произвести с помощью перечня последовательностей, записанного в таблице 4.6, где (1,4), очевидно, есть а. Когда а приложено к подмножество множества отвечает реакцией 0, а подмножество реакцией 1, что легко может быть выведено из таблицы переходов или диаграммы для Поэтому начальная ветвь расщепляется на две ветви: ветвь, обозначенную О, что является характеристической реакцией по отношению к и ветвь, обозначенную 1, что является характеристической реакцией по отношению к Теперь из выбирается пара состояний таким же образом, как была выбрана из . Когда к приложено подмножество отвечает реакцией 00, а подмножество из отвечает реакцией Поэтому ветвь, представляющая расщепляется на две ветви: ветвь, обозначенную 00, что является характеристической реакцией по отношению к и ветвь, обозначенную что является характеристической реакцией Последняя ветвь является оконечной, так как является одноэлементным множеством. Остаток дерева развертывается аналогичным образом.

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

Для и его множества допустимых начальных состояний {1, 2, 3, 4, 5} используются четыре экземпляра. Эти экземпляры, обозначенные подвергаются воздействию диагностических последовательностей а, и рааа соответственно, как предписывается деревом сложного эксперимента на рис. 4.13. Если теперь оказывается, что начальное состояние АП есть 2, то должен дать О, должен дать 00 и должен дать 1100. Так как эти реакции удовлетворяют реакциям, указанным вдоль пути по дереву, оканчивающегося в начальное состояние распознается как 2.

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

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

Граница в (4.7) существенно выше, чем величина i, встречавшаяся в большинстве задач (хотя она может быть достигнута для ), так как, по теореме 4.7, только часть примененных последовательностей должна быть длины . Однако граница в (4.8) может быть достигнута при каждом n и как показано на примере автомата с n состояниями (таблица 4.9).

Так как каждый входной символ переводит все состояния в состояние 1, все диагностические последовательности ограничиваются одним символом. Так как каждый входной

Таблица 4.9. Автомат

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

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

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

(см. скан)

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

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