Контроль функции выходов неинициального автомата с использованием простого безусловного эксперимента

Рассмотрим следующую задачу. Пусть в распоряжении экспериментатора имеется один экземпляр автомата Мили $$A$$, у которого известны входной алфавит $$X=\{x_1, \dots, x_m\}$$, выходной алфавит $$Y=\{y_1, \dots, y_l\}$$, множество состояний $$S=\{s_1, \dots, s_n\}$$, функция переходов $$\delta$$. Требуется построить простой безусловный эксперимент, позволяющий распознать функцию выходов $$\lambda$$ автомата $$A$$ или эквивалентного ему автомата. Эта задача отличается от задачи, сформулированной в лекции 6, лишь тем, что рассматриваемый здесь автомат предполагается неинициальным. Вследствие тех же причин, которые были приведены в лекции 6, содержательный смысл рассматриваемой задачи, в частности, соответствует и контролю функции выходов неинициального автомата.

Следующая теорема описывает класс автоматов, для которого сформулированная задача разрешима.

Теорема 7.1. Для того чтобы задача распознавания функции выходов неинициального автомата (с точностью до эквивалентности) была разрешима, необходимо и достаточно, чтобы автомат был сильно связен.

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

Достаточность. Построим всевозможные таблицы размерности $$m \times n$$, состоящие из элементов множества $$Y$$. Число таких таблиц конечно и равно $$N=l^{mn}$$. Очевидно, что класс автоматов $$K=\{A_1, \dots, A_N$$, у которых функция переходов совпадает с $$\delta$$, содержит автомат $$A$$. Среди автоматов класса $$K$$ встречаются попарно эквивалентные. Из каждого множества всех эквивалентных автоматов произвольным образом выбираем по одному представителю и образуем из них новый класс автоматов $$K'=\{A_1', \dots, A_r'\}$$, где $$r<N$$. По построению в классе $$K'$$ отсутствуют попарно эквивалентные автоматы, а один из автоматов $$A_i' \in K'$$ совпадает с автоматом $$A$$ или ему эквивалентен.

По предположению каждый $$A_i \in K$$ является сильно связным, но тогда можно показать, что построенный нами класс автоматов $$K'$$ является исключительным. Известно [18], что исключительность класса является необходимым и достаточным условием распознаваемости автомата, принадлежащего этому классу, простым безусловным экспериментом. Таким образом, исходная задача сведена к задаче распознавания автомата, принадлежащего известному классу, которая в нашем случае оказывается разрешимой. Этим и заканчивается доказательство теоремы.

Из приведенного доказательства следует применимость метода (предложенного в [18]) распознавания автомата, принадлежащего известному классу, к решению рассматриваемой нами задачи. Однако в этом случае он обладает тем недостатком, что при больших $$l, m, n$$ число автоматов в классе $$K'$$ велико, что вызывает значительное увеличение длины соответствующего эксперимента.

В связи со сказанным мы рассмотрим иной способ проведения эксперимента, позволяющий сократить мощность рассматриваемого класса автоматов и упростить сам эксперимент. Предположим, что исследуемый неинициальный автомат $$A$$ находится в состоянии $$s_1$$. Построим для автомата $$A_1=(S,X, \delta, s_1)$$ характеристическое слово, которое обозначим через $$p_1$$, и подадим его на вход исследуемого автомата.

По наблюдаемой реакции $$q_1$$ решаем задачу распознавания функции выходов $$\lambda_1$$ автомата Мили, которому соответствует автомат без выходов $$A_1=(S, X, \delta, s_1)$$. Вообще говоря, эта задача может и не иметь решения из-за неоднозначности, возникающей в процессе построения $$\lambda_1$$. Неоднозначность этой функции означает, что $$s_1$$ заведомо не является истинным начальным состоянием исследуемого автомата $$A$$. Если же задача разрешима, то обозначим через $$T_1$$ таблицу, которая соответствует распознанной функции выходов $$\lambda_1$$.

Предположим далее, что начальным состоянием исследуемого автомата перед подачей слова $$p_1$$ было $$s_2$$. Рассмотрим автомат $$A_2=(S,X, \delta, s_2)$$ и найдем такое слово $$p_2$$, чтобы $$p_1p_2$$ являлось для $$A_2$$ характеристическим словом. В частности, в качестве $$p_2$$ можно взять характеристическое слово для автомата $$A_2'=(S,X, \delta, \delta (s_2,p_1))$$. Подаем $$p_2$$ на вход исследуемого автомата, и пусть наблюдаемая его реакция есть $$q_2$$. По реакции $$q_1q_2$$ решаем задачу распознавания функции выходов $$\lambda_2$$ автомата Мили, которому соответствует автомат без выходов $$A_2$$. Если эта задача разрешима, то обозначим через $$T_2$$ таблицу, которая соответствует распознанной функции выходов $$\lambda_2$$.

Продолжая этот процесс и далее аналогичным образом в предположении, что начальным состоянием исследуемого автомата перед подачей слова $$p_1$$ были состояния $$s_3, \dots, s_n$$ соответственно, строим, если задачи оказываются разрешимыми, таблицы $$T_3, \dots, T_n$$, представляющие собой распознанные функции выходов $$\lambda_3, \dots, \lambda_n$$.

Предположим, что в результате описанного процесса построены таблицы $$T_{i_1}, \dots, T_{i_a}$$, где $$a \le n$$. Рассмотрим класс автоматов $$L=\{A_{i_1}, \dots, A_{i_a}\}$$, функции переходов которых совпадают с функцией переходов $$\delta$$ исследуемого автомата, а функции выходов заданы упомянутыми таблицами. Легко видеть, что по крайней мере один из автоматов класса $$L$$ совпадает с исследуемым автоматом или ему эквивалентен. Может оказаться, что в классе $$L$$ есть попарно эквивалентные автоматы. В этом случае из каждого множества всех эквивалентных автоматов выберем по одному представителю с наибольшим номером и образуем из них новый класс $$L'=\{A_{j_1}, \dots, A_{j_b}\}, b \le a, j_1 \le j_2 \le \dots \le j_b$$.

Поскольку все автоматы из $$L'$$ являются сильно связными, а по построению - попарно эквивалентными, то из уже приводимого выше утверждения [18] следует, что класс $$L'=\{A_{j_1}, \dots, A_{j_b}\}$$ исключительный. Отметим, что при больших $$l, m, n$$ мощность $$L'$$ меньше мощности класса $$K'$$, рассматриваемого в методе из [18].

Предположим, что автомат $$A_{j_k} \in L'$$ был выбран из класса $$L$$ в качестве представителя множества эквивалентных автоматов $$\{A_{\mu_1^{k}}, \dots, A_{\mu_k^{(k)}}\}$$, где $$\mu_1^{(k)} \le \dots \le \mu_k^{(k)}$$ и $$\mu_k^{(k)}=j_k$$. Пусть $$s_{\mu_1^{(k)}}, \dots, s_{\mu_k^{(k)}}$$ - состояния исследуемого автомата $$A$$, в которых он находился по предположению при построении таблиц $$T_{\mu_1^{(k)}}, \dots, T_{\mu_k^{(k)}}$$ соответственно. Образуем множество состояний

$$S_{i_k}=\{s_{\mu_1^{(k)}}', \dots, s_{\mu_k{(k)}}'\}$$

где $$s_{\mu_1^{(k)}}'=s_{\mu_1^{(k)}}$$, а состояние $$s_{\mu_i^{(k)}}', i=1,2,\dots, k$$, есть состояние автомата $$A_{\mu_i^{(k)}}$$, эквивалентное $$s_{\mu_1^{(k)}}>$$. Если в $$A_{\mu_1^{(k)}}$$ существует несколько состояний, эквивалентных $$s_{\mu_1^{(k)}}$$, то в качестве $$s_{\mu_i^{(k)}'}$$ произвольным образом выбираем одно из них. Построим теперь множество состояний

$$\tilde S_{j_k}=\{\delta(s_{\mu_1^{(k)}, p), \dots, \delta (s_{\mu_k^{(k)}}',p)}'\}$$

где $$p=p_{1p2} \dots p_n$$ - слово, использованное на предыдущем этапе эксперимента для построения автоматов класса $$L$$. Образуем, наконец, множество состояний $$\tilde S=Y_{1 \le k \le b} \tilde S_{j_k}$$.

Рассмотрим теперь автомат $$\Delta (A_{j_k}, \dots, A_{j_b})$$, состоящий из изолированных подавтоматов $$A_{i_k}$$ и по терминологии [18] называемый расщепляемым. Из приведенных выше построений вытекает, что исследуемый автомат совпадает с одним из подавтоматов $$A_{j_k}$$, находящимся в данный момент в одном из состояний множества $$\tilde S_{j_k}, =1, \dots, b)$$, либо ему эквивалентен. Для завершения эксперимента по распознаванию исследуемого автомата достаточно для расщепляемого автомата $$\Delta (A_{j_1}, \dots, A_{j_b})$$ с множеством допустимых начальных состояний $$\tilde S$$ построить такое слово $$p'$$, реакция на которое позволяет определить, к какому из изолированных подавтоматов принадлежит конечное состояние. Очевидно, что этот подавтомат и является искомым.

Эта задача, как нетрудно видеть, является обобщенной задачей установки, рассмотренной в [63]. Напомним, что слово $$p' \in X*$$ называется "обобщенным" установочным словом для автомата $$A$$ и пары $$(S', \varepsilon)$$, если

$$\forall_{s_1, s_2 \in S'} \lambda (s_1, p')=\lambda (s_2, p') \to (\delta(s_1,p'), \delta (s_2,p')) \in \varepsilon$$

где $$S' \subset S$$ - некоторое выделенное подмножество состояний автомата $$A$$, интерпретируемое как множество допустимых начальных состояний $$A$$, а $$\varepsilon $$ - некоторое отношение эквивалентности на множестве $$S \times S$$, классы которого определяют "точность" решения задачи установки. Если $$\varepsilon $$ есть тождественное отношение, то "обобщенная" задача установки вырождается в обычную задачу установки.

Применительно к нашему случаю рассмотрим "обобщенную" установочную задачу, когда $$S'=\tilde S$$, а классами отношения $$\varepsilon $$ являются множества состояний изолированных подавтоматов $$A_{j_k} (k=1, \dots, b)$$.

В [63] показано, что условие

$$\nu \subset \varepsilon $$

является достаточным для существования "обобщенного" установочного слова для автомата $$A=(S, X, Y, \delta, \lambda)$$, где бинарное отношение $$\nu \subset S \times S$$ определяется следующим образом:

$$(s_1, s_2) \in \nu \leftrightarrow \forall_{p \in X*} \lambda (s_1,p)=\lambda (s_2,p)$$

Выше показано, что класс автоматов $$L'=\{A_{j_1}, \dots, A_{j_b}\}$$ является исключительным. Из этого следует, что в рассматриваемом нами случае условие (7.1) выполняется. Таким образом, знания реакции исследуемого автомата на "обобщенное" установочное слово $$p'$$ достаточно для определения того изолированного подавтомата $$A_{j_k}$$ расщепляемого автомата $$\Delta (A_{j_k}, \dots, A_{j_b}))$$, которому принадлежит конечное состояние.

Итак, нами построен и обоснован алгоритм распознавания функции выходов неинициального автомата, который является более эффективным с точки зрения уменьшения объема вычислений, чем алгоритм Гилла [18].

Перейдем теперь к установлению верхней оценки длины описанного эксперимента, включающего в себя подачу на вход исследуемого автомата слова $$p=p_{1p2} \dots p_n$$ и "обобщенного" установочного слова $$p'$$.

Поскольку слово $$p'$$ является по построению характеристическим для автомата $$A$$, то из (6.7) следует, что длина его не превосходит величины $$n+\frac12(m-1)n(n+1)$$, где $$n=|S|, m=|X|$$. Длина слов $$p_2, \dots, p_n$$ тем более не превосходит этой величины. Тогда длина слова $$p$$ не превосходит величины $$n[n+\frac12(m-1)n(n+1)]$$.

Слово $$p'$$ является "обобщенным" установочным словом для автомата $$\Delta (A_{j_1}, \dots, A_{j_b})$$, число состояний которого не больше $$n^2$$, а мощность множества допустимых начальных состояний не превышает $$n$$. Очевидно, что длина слова $$p'$$ не превышает длины установочного слова для того же автомата, понимаемого в обычном смысле. Тогда в силу результатов, полученных в [67], верхняя оценка длины $$p'$$ есть $$\frac12n(2n-1)(n-1)$$. Как следствие, из наших рассуждений вытекает следующее утверждение.

Теорема 7.2. Длина кратчайшего простого безусловного эксперимента, позволяющего распознавать функцию выходов сильно связного неинициального автомата $$A=(S, X, Y, \delta, \lambda)$$, где $$|S|=n, |X|=m$$, не превышает величины

$$n^2+ \frac12 (m-1)n^2(n+1)+ \frac12 n(2n-1)(n-1)$$

Проиллюстрируем построение эксперимента на примере. Рассмотрим автомат $$A$$, функция переходов которого задана в табл. 7.1. Пусть его истинное начальное состояние (неизвестное экспериментатору) есть $$s_2$$. В предположении, что начальным состоянием автомата $$A$$ является $$s_1$$, строим характеристическое слово $$p_1=1010100$$.

Пусть реакция автомата $$A$$ на $$p_1$$ есть слово 1001100. Предполагаемые переходы и наблюдаемая реакция $$(s_1 \xrightarrow {1/1}s_1 \xrightarrow {0/0}s_2 \xrightarrow {1/0} s_3 \xrightarrow {0/1} s_3 \xrightarrow {1/1}s_1 \xrightarrow {0/0} s_2 \xrightarrow {0/0}s_1)$$ ) позволяют построить таблицу выходов $$T_1$$. Истинные переходы автомата $$A$$ при подаче слова $$p_1$$ таковы:

$$s_2\xrightarrow {1} s_3 \xrightarrow {0} s_3 \xrightarrow {1} s_1 \xrightarrow {0} s_2 \xrightarrow {1} s_3 \xrightarrow {0} s_3 \xrightarrow {0} s_3$$

Далее, в предположении, что начальным состоянием $$A$$ было $$s_2$$, строим слово $$p_2=1100$$, позволяющее обойти дуги графа автомата $$A$$, не пройденные при подаче слова $$p_1$$. При этом предполагаемые и истинные переходы такие:

$$s_3 \xrightarrow {1/0} s_1 \xrightarrow {1/0} s_1 \xrightarrow {0/1} s_2 \xrightarrow {0/0} s_1$$

Наблюдаемая реакция $$A$$ на слово $$p_2$$ дает возможность завершить заполнение таблицы $$T_2$$. Предположим теперь, что начальным состоянием $$A$$ было $$s_3$$. Тогда переходы $$A$$ при подаче на вход слова $$p_1p_2$$ должны иметь вид

$$s_3 \xrightarrow {1/1} s_1 \xrightarrow {0/0} s_2 \xrightarrow {1/0}s_3 \xrightarrow {0/1} s_3 \xrightarrow {1/1} s_1 \xrightarrow {0/0} s_2 \xrightarrow {0/0} s_3 \xrightarrow {1/0} s_1 \xrightarrow {1/0} s_1 \xrightarrow {0/1} s_2 \xrightarrow {0/0} s_1$$

Из приведенной цепочки видно, что записи в таблице $$T_3$$, соответствующие состояниям $$s_1$$ при входе 0 и $$s_3$$ при входе 1, будут противоречивыми. Это означает, что $$s_3$$ не может являться начальным состоянием $$A$$. Таким образом, рассматриваемый автомат $$A$$ совпадает (или эквивалентен) с автоматом $$A_1$$, функция выходов которого задана табл. 7.2, либо с автоматом $$A_2$$, функция выходов которого задана табл.7.3.

s\x	0	1
$$s_1$$	$$s_2$$	$$s_1$$
$$s_2$$	$$s_1$$	$$s_3$$
$$s_3$$	$$s_3$$	$$s_1$$

s\x	0	1
$$s_1$$	0	1
$$s_2$$	0	0
$$s_3$$	1	1

s\x	0	1
$$s_1$$	1	0
$$s_2$$	0	1
$$s_3$$	0	0

Множество $$\tilde S$$ в рассматриваемом случае есть $$\{s_1^{A_1}, s_2^{A_2}\}$$. Установочной последовательностью для расщепляемого автомата $$\Delta (A_1, A_2)$$ является, например, 0. При подаче на вход автомата $$A$$ символа 0 пусть его реакция есть 1, т. е. конечным состоянием автомата $$\Delta (A_1, A_2)$$ является $$s_2^{A_2}$$. Отсюда следует, что рассматриваемый автомат $$A$$ совпадает с $$A_2$$ или эквивалентен ему.

Приведем теперь некоторые соображения, сокращающие длину эксперимента. Такое сокращение возможно, например, когда у рассматриваемого автомата $$A=(S,X,Y, \delta, \lambda)$$ существует слово $$p \in X*$$, такое, что $$|\delta (S,p)|<|S|$$, где $$\delta (S,p)=Y_{s \in S} \delta (s,p)$$. В этом случае после подачи слова $$p$$ на вход автомата число его допустимых начальных состояний уменьшается и, соответственно, уменьшается число таблиц $$T_j$$, которые необходимо строить в процессе проведения эксперимента. Отсюда возникает задача отыскания для заданного автомата $$A$$ такого слова $$p$$, чтобы $$|\delta (S,p)|$$ была минимальной.

Эта задача может быть решена с использованием конструкции синхронизирующего дерева для алфавита $$A$$, описанной в лекции 1. Каждый лист этого дерева связан с некоторой $$A$$ -группой. При этом ее мощность может равняться либо 1, что говорит о наличии у автомата $$A$$ синхронизирующей последовательности, либо некоторому числу $$k>1$$.

В последнем случае путь, ведущий из вершины синхронизирующего дерева в эту $$A$$ -группу, не соответствует входной последовательности, являющейся синхронизирующей. Среди $$A$$ -групп упомянутого дерева, связанных с его конечными ветвями, т. е. листьями, найдем такую, число элементов которой минимально. Заметим, что, вообще говоря, таких $$A$$ -групп может быть несколько. Простые рассуждения показывают, что слово $$p$$, которое соответствует пути по дереву, ведущему из корня к ветви, связанной с минимальной по мощности $$A$$ -группой, дает решение поставленной задачи.

Вернемся к рассмотренному выше примеру. Выполнив для автомата $$A$$ построения синхронизирующего дерева, находим, что слово $$p=11$$ является для него синхронизирующей последовательностью. После подачи его на вход автомат устанавливается в состояние $$s_1$$, и завершающий этап эксперимента таким образом сводится к подаче на автомат слова $$p_1$$, являющегося характеристическим для $$A$$ в состоянии $$s_1$$. Общая длина эксперимента при этом равна 9, тогда как длина построенного ранее эксперимента была равна 12.

Вопросы и упражнения

Сформулируйте постановку задачи контроля функции выходов неинициального автомата.

Каков критерий разрешимости этой задачи?

К какой классической задаче сводится исследуемая здесь задача?

Опишите процедуру решения соответствующей классической задачи.

Сформулируйте "обобщенную" установочную задачу и приведите достаточное условие ее разрешимости.

Приведите верхнюю оценку длины эксперимента, контролирующего функцию выхода неинициального автомата. Является ли эта оценка достижимой?