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

Рассмотрим путь в установочном дереве для М и А(М), который ведет к A-группе G, содержащей однородное σ-множество, скажем {σ´_í, σ´_i,..., σ´_i}, где σ´_i встречается h раз (так как G может содержать другие σ-множества, которые не являются однородными, сама G не обязательно является однородной). Если этот путь описывает входную последовательность ε, то тогда А(М) должно содержать некоторое число h состояний, скажем σ_i1, σ_i2,..., σ_ih, все преемники которых по отношению к ε суть σ´_i. Так как (σ´_í, σ´_i,..., σ´_i) является однородным в G, то реакция σ_i1 или σ_i2 или σ_im на ε, по лемме 4.2, не может быть приписана никакому конечному состоянию, за исключением σ´_i Следовательно, если σ_i1 или σ_i2 или σ_im случайно является истинным начальным состоянием М, то конечное состояние М может быть распознано с помощью входной последовательности, которая не обязательно описывается установочным путем. Используя этот факт, можно применять минимальную установочную последовательность не целиком, а по частям, в надежде, что конечное состояние является таким, что оно может быть распознано с помощью только части всей последовательности. Эта схема составляет решение диагностической задачи для т состояний с помощью простого условного эксперимента.

Расчленение минимальной установочной последовательности на подпоследовательности выполняется следующим образом. Пусть ε_k является k-й подпоследовательностью и пусть G_k является Л-группой, к которой ведет путь, описывающийся последовательностью ε₁ε_2... ε_k обозначим А(М) через G₀. Тогда ε_k есть последовательность, описываемая подпутем, который ведет от G_k-l к первой A-группе, которая содержит, по крайней мере, на одно однородное σ-множество больше, чем G_k-l. Так как решение G₀ есть 1 и так как число σ-множеств в A-группе не может превышать мощность А(М), равную m, число подпоследовательностей, произведенных таким образом, не может превышать m— 1. Например, автомат A17, представленный на рис. 4.3, и множество допустимых начальных состояний {1, 2, 3, 4, 5} дают: G₀={1, 2, 3, 4, 5}; G₁={1,1}, {2}, {5, 1}; G₂={1, 1}, {1}, {2}, {1}, и, следовательно, ε₁ = aa, а ε₂ = a (см. рис. 4.16). Если определены подпоследовательности, условный эксперимент может быть выполнен следующим образом.

Алгоритм 4.6. Даны автомат М, его множество допустимых начальных состояний A(M) = { σ_i1, σ_i2,..., σ_im } и расчлененная установочная последовательность ε₁ε_2... ε_k распознать конечное состояние М с помощью условного эксперимента. (1) Составляем перечень реакций М|σ_i1, М|σ_i2,..., М|σ_im, на ε₁ε_2... ε_r. Расчленяем каждую реакцию на r подпослгдовательностей так, чтобы они соответствовали расчленению входной последовательности. После каждой выходной подпоследовательности вносим в перечень соответствующее конечное состояние. Полагаем k=l. (2) Прилагаем ε_k к М. (3) (а) Если реакцию М на ε₁ε_2... ε_k можно приписать только одному конечному состоянию в перечне, составленном в (1), то это состояние есть конечное состояние М. (б) Если реакцию М на ε₁ε_2... ε_k можно приписать двум или более различным конечным состояниям в перечне, составленном в (1), то увеличиваем k на 1 и возвращаемся к (2).

Алгоритм 4.6 может быть продемонстрирован автоматом А17 и множеством допустимых начальных состояний {1, 2, 3, 4, 5}, для которых мы имеем ε₁ = aa и ε₂ = a. Перечень реакций на aaa, расчлененных, как определено в шаге 1, и соответствующих конечных состояний дан в таблице 4.12. Если оказалось, что начальное состояние есть 1

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

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

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

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