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

4.3. Диагностические и установочные эксперименты

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

1. Диагностическая задача. Известно, что данный автомат М, таблица переходов которого имеется в нашем распоряжении, находится в одном из состояний Найти это состояние.

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

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

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

формой и, следовательно, без потери общности предполагать, что М минимален.

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

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

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