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

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

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

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

Расчленение минимальной установочной последовательности на подпоследовательности выполняется следующим образом. Пусть является подпоследовательностью и пусть является А-группой, к которой ведет путь, описывающийся последовательностью обозначим через

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

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

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

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

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

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

В заключение мы можем сделать следующее утверждение.

Теорема 4.11. Каждая установочная задача для m состояний, которая может быть решена простым

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

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

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