Обобщенные автоматы без потери информации конечного порядка

Автоматы без потери информации конечного порядка (ОБПИК-автоматы) являются в некотором смысле аналогами БПИК-автоматов, введенных С. Ивеном [74].

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

Для однозначности определения числа $$N(A)$$ будем считать, что оно является минимальным из всех возможных для заданного автомата $$A$$ чисел такого рода, и назовем его порядком автомата $$A$$.

Отметим, что определенные нами ОБПИК-автоматы в качестве частного случая включают в себя ранее известные БПИК-автоматы, введенные $$C$$. Ивеном [74] , и автоматы существенно без потери информации конечного порядка (СБПИК-автоматы), введенные автором представленного курса лекций в [9], [46]. БПИК-автоматы получаются при $$|S_0|=0$$, $$\nu = n, \mu = m$$, а СБПИК-автоматы получаются при $$S_0=S, \nu = n, \mu = m$$, где $$n$$ - число входных каналов автомата.

Пусть $$\bar p = p_1 p_2 \dots p_a$$ и $$\bar q=q_{1q2} \dots q_b$$ - слова в структурированном алфавите $$X$$. Из определения ОБПИК-автомата порядка $$N(A)$$ следует, что он должен обладать следующим свойством:

$$\forall_{s, t \in S_)} \forall_{\bar p, \bar q \in X*} d(\bar p)=d(\bar q)=N(A) pr_{1, \dots, \mu} \lambda (s, \bar p)=pr_{1, \dots, \mu} \lambda (s, \bar q) \to pr_{1, \dots, \nu} \bar p=pr_{1, \dots, \nu} \bar q$$

Здесь, не теряя общности, предполагается, что наблюдение реакции ведется по первым $$\mu$$ выходным каналам с номерами $$1,2, \dots, \mu$$, а неизвестное слово будет восстанавливаться по первым $$\nu$$ входным каналам с номерами $$1,2,\dots, \nu$$.

Теорема 4.1. Автомат $$A$$ является ОБПИК-автоматом тогда и только тогда, когда в его проверочном графе $$T(A)$$ все контуры и все пути, ведущие в эти контуры, не содержат выделенных дуг.

Необходимость. Пусть $$A$$ есть ОБПИК-автомат порядка $$N(A)$$. Покажем, что он одновременно является и ОБПИ-автоматом. Пусть на вход $$A$$ подано неизвестное входное слово $$\bar {\nu}$$, такое, что $$pr_{1, \dots, \nu} \bar {\nu}=\nu_1 \nu_2 \dots \nu_{d(\nu)}$$, а реакция $$\bar w$$ автомата $$A$$ на это слово такова, что $$pr_{1, \dots, \mu} \bar w= w_1 w_2 \dots w_{d(\nu)}$$. Подадим на вход $$A$$ произвольное слово $$\bar {\nu*}$$ длины $$N(A)$$ (пусть $$pr_{1, \dots, \nu} \bar {\nu*}=\nu_1* \dots \nu_{N(A)}*$$ ), реакция на которое есть слово $$\bar w*$$ (пусть $$pr_{1, \dots, \mu} \bar w*=w_1* \dots w_{N(A)}*$$ ). Поскольку $$A$$ есть ОБПИК-автомат порядка $$N(A)$$, то по начальному отрезку проекции выходного слова $$w_{1w2} \dots w_{d(\nu)}w_1* \dots w_{N(A)}*$$ длины $$N(A)$$ можно определить 1-й символ $$\nu_1$$ неизвестного входного слова, аналогично по начальному отрезку длины $$N(A)$$ слова $$w_{2w3} \dots w_{d(\nu)}w_1* \dots w_{N(A)}*$$ - символ $$\nu_2$$ и, наконец, по начальному отрезку длины $$N(A)$$ слова $$w_{d(\nu)}w_1* \dots w_{N(A)-1}*$$ - символ $$\nu_{d(\nu)}$$. Таким образом, подача на вход автомата $$A$$ произвольного слова длины $$N(A)$$ является тем экспериментом, который всегда позволяет определить искомую проекцию неизвестного входного слова. Следовательно, $$A$$ является ОБПИ-автоматом.

Предположим, что в $$T(A)$$ имеется контур $$\{s_1, s_j\}\to \{s_{i_1}, s_{j_1}\} \to \dots \to \{s_{i_{t-1}}, s_{j_{t-1}}\} \to \{s_i, s_j\}$$ длины $$t$$, первая дуга которого - выделенная. В силу теоремы 3.2 предшествующей лекции все вершины $$\{s_a, s_b\}$$ этого контура таковы, что $$s_a \ne s_b$$. Обозначим через $$\bar p$$ и $$\bar q$$ входные слова, соответствующие проходу автомата $$A$$ по состояниям контуров $$s_i, s_{i_1}, \dots, s_{i_{t-1}}$$ и $$s_j, s_{j_1}, \dots, s_{j_{t-1}}$$. Поскольку 1-я дуга контура в $$T(A)$$ является выделенной, то $$\bar p=p_1 \bar {\nu}$$ и $$\bar q=q_1 \bar {\nu}$$, где $$p_1 \ne q_1$$. Если к автомату $$A$$, находящемуся в состоянии $$s_j$$ или $$s_j$$, приложить входные слова вида $$p_1 \bar {\nu^{\gamma}} \bar {\nu*}$$ и $$q_1 \bar {\nu^{\gamma}} \bar {\nu*}$$, где $$r$$ - целое положительное число, $$\bar {\nu*}$$ - некоторый начальный отрезок слова $$\bar {\nu}, \bar {\nu^{\gamma}} - r$$ -кратное повторение слова $$\bar {\nu}$$, то понятно, что наблюдаемые проекции автомата в обоих случаях будут одинаковыми. Следовательно, по наблюдаемой реакции восстановить однозначно 1-й символ неизвестного входного слова невозможно. Поскольку сказанное справедливо для любого $$r$$ и начального отрезка $$\bar {\nu*}$$ любой длины, то упомянутая потеря информации будет иметь место для слов произвольной длины. Последний факт противоречит исходному предположению о том, что $$A$$ является ОБПИК-автоматом.

Нетрудно убедиться, что аналогичная ситуация имеет место и в случае, когда в графе $$T(A)$$ существует путь, ведущий в контур и начинающийся с выделенной дуги.

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

Достаточность. Пусть $$T(A)$$ не содержит контуров и, следовательно, в нем имеются только пути конечной длины. Рассмотрим вначале случай, когда эти пути не содержат выделенных дуг. Покажем, что в этих предположениях однозначное восстановление проекции первого символа неизвестного входного слова длины $$N(A)$$ возможно. Предположим противное: пусть в $$T(A)$$ существует два пути

$$\{s_{i_1}, s_{j_1}\} \xrightarrow {x_1/y_1} \{s_{i_2}, s_{j_2}\} \to \dots \xrightarrow {x_{N(A)}/y{N(A)}} \{S_{i_{N(A)}}, S_{j_{N(A)}}\}$$

и

$$\{s_{k_1}, s_{l_1}\} \xrightarrow {\tilde {x_1}/y_1} \{s_{k_2}, s_{l_2}\} \to \dots \xrightarrow {x_{N(A)}/y_{N(A)}} \{S_{i_{N(A)+1}}, S_{j_{N(Q)+!}}\}$$

где $$x_1 \ne \tilde {x_1}$$. Очевидно, что если проекция реакции автомата $$A$$ есть $$y_{1y2} \dots y_{N(A)}$$, то проекцию 1-го искомого символа восстановить однозначно невозможно. Однако в этом случае в $$T(A)$$ должны существовать выделенные дуги $$\{s_{i_1}, s_{k_1}\}\xrightarrow {y_1} \{s_{i_2}, s_{k_2}\}, \{s_{i_1}, s_{l_1}\} \xrightarrow {y_1}\{s_{i_2}, s_{l_2}\}$$ и т. д., что противоречит исходному предположению.

Теперь рассмотрим случай, когда в графе $$T(A)$$ содержится путь $$\{s_{i_1}, s_{j_1}\} \to \{s_{i_2}, s_{j_2}\} \to \dots \{s_{i_a}, s_{j_a}\}$$, у которого 1-я дуга является выделенной. Отсутствие в вершине $$\{s_{i_a}, s_{i_b}\}$$ исходящей дуги означает, что при любом входном сигнале реакции автомата $$A$$ из состояний $$s_{i_a}$$ и $$s_{j_a}$$ различны. Но тогда по этой реакции идентифицируется истинное состояние автомата ( $$s_{i_a}$$ или $$s_{j_a}$$ ). Поскольку по теореме 3.2 предшествующей лекции для вершины $$\{s_{i_k}, s_{j_k}\}$$ упомянутого выше пути $$s_{i_k} \ne s_{j_k}$$ при $$k=2, \dots, a$$, то обратным ходом можно идентифицировать истинную последовательность сменяющихся состояний автомата $$A$$ из двух возможных: $$s_{i_1}, \dots, s_{i_a}$$ либо $$s_{j_1}, \dots, s_{j_a}$$. Отсюда вытекает, что проекция первого символа неизвестного входного слова восстанавливается однозначно.

Перейдем к рассмотрению случая, когда в графе $$T(A)$$ имеются контуры. Доказательство для него проведем от противного. Пусть $$A$$ не является ОБПИК-автоматом. В частности, в нем могут существовать два контура:

$$s_1 \xrightarrow {x_1/y_1} s_2 \xrightarrow {x_2/y_2} \dots \to s_k \xrightarrow {x_b/y_b} s_1$$

и

$$s_1* \xrightarrow {\hat {x_1}/y_1} s_2* \xrightarrow {x_2/y_2} \dots \to s_b* \xrightarrow {x_b/y_b} s_1*$$

где происходит потеря информации о первом входном символе, если $$x_1 \ne \hat {x_1}$$. Но тогда в графе $$T(A)$$ существует контур $$\{s_1, s_1*\} \to \{s_2, s_2*\} \to \dots \to \{s_b, s_b*\} \to \{s_1, s_1*\}$$, у которого 1-я дуга является выделенной. Отсюда вытекает справедливость достаточности условий теоремы для контуров с выделенными дугами. По аналогии устанавливается справедливость условий теоремы и для случая путей с выделенными дугами, ведущими в контур. На этом завершается доказательство достаточности условий теоремы.

Следующее утверждение позволяет определить порядок ОБПИК-автомата .

Теорема 4.2. Если в проверочном графе $$T(A)$$ ОБПИК-автомата $$A$$ длина максимального пути, начальная дуга которого является выделенной, равна $$t$$, то порядок ОБПИК-автомата $$N(A)=t+1$$.

Доказательство. Пусть в $$T(A)$$ существует путь, начинающийся в вершине $$\{s_i, s_j\}$$ и заканчивающийся в $$\{s_k, s_l\}$$, 1-я дуга которого является выделенной. Наличие его означает существование у автомата $$A$$ двух входных слов $$\bar {\nu_1}$$ и $$\bar {\nu_2}$$, различающихся проекциями первых символов и обладающих следующим свойством:

$$\delta (s_i, \bar {\nu_1})=s_k \delta (s_j, \bar {\nu_2})=s_l \to pr_{1, \dots, \mu} \lambda (s_i, \bar {\nu_1})=pr_{1, \dots, \mu} \lambda (s_i, \bar {\nu_1})=pr_{1, \dots, \mu} \lambda (s_j, \bar {\nu_2})$$

При распознавании проекции неизвестного входного слова автомата $$A$$ мы не располагаем информацией об истинном его начальном состоянии. Если на вход автомата $$A$$ будет подано одно из слов $$\bar {\nu_1}$$ или $$\bar {\nu_2}$$, то мы не сможем определить и его истинное конечное состояние. В этой ситуации определение проекции 1-го символа входного слова по наблюдаемой реакции длины не более $$t$$ символов невозможно. Это означает, что порядок автомата $$A$$ заведомо больше $$t$$. Поскольку путь рассматриваемого вида максимален по длине, то из вершины $$\{s_k, s_l\}$$ графа $$T(A)$$ не может исходить ни одной дуги. Для автомата $$A$$ этот факт интерпретируется следующим образом: если автомат $$A$$ находится в одном из состояний $$s_k$$ или $$s_l$$, то подача любого входного символа и наблюдение соответствующей реакции автомата позволяет всегда однозначно определить истинное начальное состояние из двух допустимых. Отсюда можно сделать вывод, что знание проекции реакции автомата на неизвестное входное слово длины $$t+1$$ всегда позволяет однозначно определить проекцию 1-го символа этого входного символа.

Докажем это утверждение от противного. Пусть существуют два различных входных слова $$\bar {\nu_1} \bar x$$ и $$\bar {\nu_2} \bar x$$, где $$\bar {\nu_1}$$ и $$\bar {\nu_2}$$ - слова, упомянутые ранее, а $$\bar x$$ - произвольный символ из $$X$$. Пре дположим, что автомат находится в состоянии $$s_i$$ или $$s_j$$. Если на вход автомата $$A$$ будет подано одно из слов $$\bar {\nu_1} \bar x$$ или $$\bar {\nu_2} \bar x$$, то по проекции последнего выходного символа можно определить состояние, в котором автомат находился перед подачей символа $$\bar x$$. Неоднозначность определения проекции 1-го символа неизвестного входного слова в нашей ситуации означало бы, что $$\exists {\nu_1, \nu_2 \in X*} \delta (s_i, \bar {\nu_1})=\delta (s_j, \bar {\nu_2}) pr_{1, \dots, \mu} \lambda (s, \bar {\nu_1})= pr_{1, \dots, \mu} \lambda (s, \bar {\nu_2}) \to pr_{1, \dots, \nu} \bar {\nu_1} \ne pr_{1, \dots, \nu} \bar {\nu_2}$$.

Тогда в соответствии с определением 3.1 состояния $$s_i$$ и $$s_j$$ образуют пару СПИ-состояний. Отсюда следует, что автомат $$A$$ не может принадлежать классу ОБПИ-автоматов, а в силу теоремы 4.1 он не может принадлежать и классу СБПИК-автоматов. Последний факт противоречит нашему предположению.

Рассмотрим автомат, заданный графом на рис.4.1. Пусть его реакция наблюдается по 1-му и 2-му выходным каналам ( $$\mu =2$$ ), а проекция неизвестного входного слова должна восстанавливаться по 1-му каналу ( $$\nu =1$$ ). Пусть $$S_0=\{1,2,3\}$$, тогда проверочный граф для этого автомата изображен на рис.4.2. Легко проверить, что условия теоремы 4.1 для графа на рис.4.2 выполняются, следовательно, рассматриваемый автомат есть ОБПИК. Поскольку длины всех путей в графе $$T(A)$$, начальные дуги которых являются выделенными, равны $$1 (t=1)$$, то порядок автомата $$N(A)=2$$.

(рис 4.2) (рис 4.1)

В табл. 4.1 приведены все возможные реакции автомата на входные слова длины 2 и соответствующие им проекции 1-го символа неизвестного входного слова по 1-му входному каналу.

Реакция автомата по каналам 1 и 2	Проекция 1-го входного символа по каналу 1
$$y_1(t) y_2(t)y_1(t+1) y_2(t+1)$$
0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1	0 1 0 1 1 0

Рассмотрим вопрос о восстановлении проекции 1-го символа неизвестного входного слова. Из (4.1) следует, что каждой комбинации из $$N(A)$$ символов, являющихся проекциями реакций автомата $$A$$ по выходным каналам с номерами $$1, \dots, \mu$$, однозначно соответствует искомая проекция 1-го символа неизвестного входного слова. В частности, такое соответствие для автомата на рис.4.1 задано табл. 4.1. Подобную таблицу будем интерпретировать далее как совокупность $$\nu$$ таблиц истинности частичных булевых функций, где $$\nu$$ - число каналов, по которым производится восстановление неизвестного входного слова. Строки первого столбца таблицы типа табл. 4.1 содержат двоичные наборы длины $$\mu * N(A) $$, на которых упомянутые булевы функции считаются заданными, а значение на соответствующем наборе $$i$$ -й булевой функции полагается равным величине, стоящей в $$i$$ -й позиции второго столбца таблицы, где $$i=\overline {1, \nu}$$.

Исходя из предложенной интерпретации, общая схема восстановления некоторой проекции неизвестного входного слова для ОБПИК-автомата порядка $$N(A)$$ с использованием комбинационного устройства, реализующего совокупность $$\nu$$ частичных булевых функций, изображена на рис.4.3. На этом рисунке $$D$$ означает элемент единой задержки. На рис.4.4 изображена схема восстановления, которая построена на основе табл. 4.1 для автомата, представленного на рис.4.1.

(рис 4.4) (рис 4.3)

По аналогии с оптимальными ОБПИ-автоматами, введенными в предыдущей лекции, рассмотрим ОБПИК-автоматы. Для их отыскания по графу автомата $$A$$ построим проверочный граф $$T(A)$$, предполагая, что наблюдение реакции ведется по всем $$m$$ выходным, а восстановление - по всем $$n$$ входным каналам. Используя $$T(A)$$, найдем в нем все контуры и все пути, ведущие в эти контуры, образуем на этой основе множество $$\Gamma = \{\gamma_1, \gamma_2, \dots, \gamma_t\}$$ всех входящих в них выделенных дуг. Если $$\Gamma = \varnothing$$, то по теореме 4.1 автомат $$A$$ есть ОБПИК и при $$\mu = m$$ он будет таковым для любого $$\nu = \overline {1,n}$$. Если $$\Gamma \ne \varnothing$$, то для каждого $$i=\overline {1,t}$$ построим множество $$R_i*$$ целых чисел, являющихся номерами входных каналов, в которых на дуге $$\gamma_i$$ происходит потеря информации в смысле, определенном в предыдущем разделе. По аналогии с ОБПИ-автоматами можно утверждать, что $$A$$ является ОБПИК для любого подмножества каналов из множества $$R=\{1,2,\dots, n\}\{R_1^* \cup \dots \cup R_t^*\}$$ и $$R$$ есть максимальное по мощности множество каналов, сохраняющее свойство ОБПИК.

Пусть $$M=\{1,2, \dots, \mu\}$$. Для $$j=\overline {1, \mu}$$ строим проверочный граф $$T_{M\\{j\}}^R(A)$$. Если он удовлетворяет условиям теоремы 4.1, то $$j$$ -й канал является избыточным в смысле, определенном в предыдущей лекции. Пусть $$M*+\{j_1, j_2, \dots, j_s$$ - множество номеров всех избыточных выходных каналов автомата $$A$$. Если $$M* = \varnothing$$, то $$A_M^R$$ является искомым оптимальным автоматом. При $$M* \ne \varnothing$$ рассмотрим всевозможные сочетания пар, троек и т. д. номеров каналов из $$M*$$. Обозначим $$S_{\lambda}$$ множество, содержащее $$\lambda$$ номеров из $$M*$$, где $$\lambda = \overline{2, |M*|}$$. Для каждого из множеств $$S_{\lambda}$$ начиная с $$\lambda =2$$ строим проверочный граф $$T_{S_{\lambda}}^R(A)$$. Если для всевозможных множеств $$S_{\lambda}$$ при $$\lambda =2$$ соответствующие им проверочные графы удовлетворяют условиям теоремы 4.1, то увеличиваем $$\lambda$$ на 1 и продолжаем этот процесс. Если на очередном этапе каждый из построенных для всевозможных множеств $$S_{\lambda}$$ проверочных графов не удовлетворяет условиям теоремы 4.1, то процесс прекращается. При этом очевидно, что оптимальными будут все те автоматы $$A_{S_{\lambda}}^R$$, рассмотренные на предпоследнем этапе (для них $$\lambda$$ имеет значение на 1 меньше, чем на последнем этапе), для которых соответствующие графы удовлетворяют условиям теоремы 4.1.

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

Сформулируйте определение обобщенного автомата без потери информации конечного порядка.

Приведите критерий принадлежности автомата классу автоматов ОБПИК в терминах проверочного графа.

Опишите процедуру определения порядка ОБПИК-автомата.

Опишите процедуру построения комбинационной схемы, позволяющей восстанавливать проекцию неизвестного входного слова ОБПИК-автомата.

Автомат задан графом на рис.4.1. Пусть множество допустимых начальных состояний автомата есть $$\{1,2,3\}$$. Пусть для наблюдения реакции доступны оба выходных канала, а проекция неизвестного входного слова должна быть восстановлена по 2-му каналу. Требуется:

построить проверочный граф этого автомата;

проверить критерий принадлежности этого автомата классу ОБПИК-автоматов;

если этот критерий выполняется, то определить порядок автомата.