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

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

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

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

дереве преемников и, следовательно, построить установочную последовательность для любого .

Алгоритм 4.7. Заданы автомат М и его множество допустимых начальных состояний требуется найти установочную последовательность для М и Пусть А (М) является Полагаем Если не является однородным, то определим регулярную подпоследовательность, скажем Пусть -преемником является Увеличиваем k на 1 и возвращаемся к (2). (б) Если однородно, то есть установочная последовательность для М и А (М).

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

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

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

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

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

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

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

представляет собой множество для строится на основе т. е. на основе предварительно определенной подпоследовательности (подпоследовательности, приведенной в последнем столбце строки ) и таблицы или графа переходов для . Пара состояний есть любая пара состояний в любом однородном -множестве, содержащемся в есть минимальная диагностическая последовательность для , которая может быть получена по методу, описанному в § 4.4. Для того чтобы минимизировать длину индивидуальных подпоследовательностей, можно выбрать так, чтобы они давали в результате кратчайшее . Для автомата это может быть выполнено с помощью таблицы 4.6, в которой приводится перечень минимальных диагностических последовательностей для всех пар состояний в Следует отметить, что, вообще говоря, это правило выбора не гарантирует минимальности общей длины установочного эксперимента (хотя в нашем примере оказалось, что результирующая установочная последовательность является минимальной). Строка 3 в таблице — последняя, так как является однородной А-группой. Установочная последовательность строится

путем выписывания последовательностей в порядке, в котором они появляются в последнем столбце. Поэтому регулярный установочный эксперимент для и множества допустимых начальных состояний состоит в подаче и наблюдении реакции. Реакция состояний 1, 2, 3, 4 и 5 на и соответствующее конечное состояние показаны в таблице 4.11.

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

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