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

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

Алгоритм 4.6. Даны автомат М и его множество допустимых начальных состояний А (М) = {σ_i1, σ_i2,..., σ_im}; требуется найти конечное состояние М с помощью кратчайшего простого безусловного эксперимента. (1) Строим установочное дерево для М и А(М). (2) Выбираем любую установочную последовательность ε´(А), описываемую деревом[26]. (3) Составляем перечень реакций М|σ_i1, М|σ_i2,..., М|σ_im на ε´(А) и состояний σ´_i1, σ´_i2,..., σ´_im в которые ственно переходят σ_i1, σ_i2,..., σ_im при подаче ε´(А). (4) Прилагаем ε´(А) к M и фиксируем реакцию. Конечное состояние есть состояние σ´_ik, для которого реакция, внесенная в перечень в (3), совпадает с зафиксированной реакцией.

Алгоритм 4,5 может быть продемонстрирован на примере автомата A17 (рис. 4.3) и множества допустимых начальных состояний {1, 2, 3, 4, 5}. В этом случае установочное дерево на рис. 4.16 выявляет, что минимальная устацозочная последовательность есть аскх. Таблица 4.11 содержит перечень реакций и конечных состояний для начальных состояний {1, 2, 3, 4, 5}, когда применяется скха. Как и следовало ожидать, различные конечные состояния соответствуют различным реакциям и, следовательно, реакции могут служить в качестве критериев для распознавания конечного состояния A17 при условии, что определено множество допустимых начальных состояний.

Решение установочной задачи непосредственно может быть применено к следующей задаче. Известно, что заданный автомат М есть автомат М₁ в состоянии, принадлежащем множеству А(М₁), или автомат М₂ в состоянии, принадлежащем множеству А(М₂) или автомат M _N в состоянии, принадлежащем множеству A (M _N). Желательно распознать автомат и его конечное состояние. Если предположить, что M₁, M₂,..., M _N являются сравнимыми и что их таблицы переходов имеются, то указанная выше задача есть в точности установочная задача для т состояний для расщепляемого автомата ∆(M₁, M₂,..., M _N) и множества допустимых начальных состояний А (М₁)U A (M₂)U... UA(M _N). В этом случае в основном предположении, что заданный автомат М является минимальным, подразумевается, что каждый автомат M_i является минимальным и что ни одно состояние любого автомата M_i не является эквивалентным какому-нибудь состоянию автомата M_j (j ≠ i).