Преобразования автоматов в автоматы без потери информации

Разбить на страницы

Показывать лекцию целиком

Отсутствие потери информации в автомате является полезным свойством при решении ряда задач. В качестве примера рассмотрим задачу контроля правильности функционирования сети автоматов, изображенной на рис.5.1. В этой сети $$A_i (i=1, \dots, 7)$$ - автоматы Мили. Задачу контроля сети автоматов можно свести к задаче контроля одного автомата $$A$$, являющегося математической моделью этой сети, и решить ее известными методами. Однако при этом исследуемый автомат $$A$$ может иметь столь значительную размерность, что известные методы окажутся практически неприемлемыми из-за большого объема вычислений. Другой возможный способ состоит в сведении контроля сети к последовательному контролю каждого из автоматов-компонентов.

(рис 5.1)

Второй подход более перспективен с точки зрения практической реализации, но применим он не ко всякой сети. При контроле сети, изображенной на рис.5.1, доступным для наблюдения выходом является только выход автомата $$A_7$$. Поскольку выходы автоматов $$A_5$$ и $$A_6$$ являются входами автомата $$A_7$$, для контроля каждого из них в отдельности необходимо распознавать входные слова $$A_7$$ по наблюдаемой реакции сети. Аналогичным образом обстоит дело и с входными словами автоматов $$A_5, A_6$$. Таким образом, одно из условий, упрощающих решение задачи контроля рассматриваемой сети, состоит в том, чтобы ее компоненты $$A_5, A_6, A_7$$ были БПИ-автоматами. Поскольку в конечных автоматах представлены регулярные события и только они, на входы указанных компонентов сети могут поступать только слова, принадлежащие регулярным событиям. С этой точки зрения нам достаточно потребовать, чтобы компоненты $$A_5, A_6, A_7$$ были БПИ-автоматами лишь на регулярных множествах входных слов (ниже мы уточним это понятие).

В связи с изложенным возникает задача преобразования заданного автомата в БПИ-автомат на регулярном множестве входных слов, которая и будет исследована ниже.

Заметим, что эта задача представляет и самостоятельный интерес, один из возможных ее вариантов рассмотрен в [80].

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

Перейдем к подробному рассмотрению упомянутой задачи. Пусть $$P$$ - регулярное множество непустых слов в алфавите $$X$$ автомата $$A=(S, X, Y, \delta, \lambda)$$. Обозначим через $$Q$$ следующее множество непустых выходных слов автомата $$A$$:

$$Q=\bigcup_{s \in S} \lambda_s (P)$$

где

$$\lambda_s (P)=\bigcup_{p \in X*} \lambda (s,p)$$

Автомат $$A$$ назовем $$P$$ -БПИ-автоматом, если и только если

$$\forall_{s \in S} \forall_{p,q \in P} \lambda (s,q)= \lambda (s,q) \delta (s,q) \to p=q$$

Рассмотрим следующую задачу. Пусть задан автомат $$A$$ и некоторое регулярное множество $$P$$ непустых слов в алфавите $$X$$. Требуется вывести контрольные точки в автомате $$A$$ таким образом, чтобы полученный в результате автомат был $$Р$$ -БПИ-автоматом.

По аналогии с [23] задачу нахождения минимального числа контрольных точек можно сформулировать следующим образом. Для автомата $$A$$ и заданного $$P$$ найти такое разбиение $$\Pi = \{K_1, \dots, K_r\}$$ множества $$Z=S \times X$$, чтобы выполнялись следующие условия:

для любого состояния $$s$$ автомата $$B=(S, X, Y, \times \Pi, \delta, \Lambda)$$ и любой пары слов $$p$$ и $$q$$ из $$P$$ имеет место соотношение

$$\Lambda (s,p)= \Lambda (s,p) \delta (s,p)=\delta (s,p) \to p=q$$

где $$\Lambda (s,x)=(\lambda (s,x), K(s,x)), K(s,x)$$, - код класса разбиения $$\Pi$$, содержащего пару $$(s,x)$$, в некотором стандартном алфавите;

у всех разбиений $$\Pi'$$, удовлетворяющих пункте 1 и не равных $$\Pi$$, число классов $$k$$ таково, что верно неравенство

$$E(\log_t k) \ge E(\log_t r)$$

где $$E(x)=n$$ при $$n-1<x \le n; n$$ - целое положительное число; $$t$$ - мощность стандартного алфавита; $$E(\log_t r)$$ - число дополнительных выходных каналов (контрольных точек).

Сформулированная задача относится к числу $$NP$$ -полных проблем, т. е. методы ее решения содержат перебор. Ниже описан способ вывода контрольных точек в автомате, не содержащий перебора, но в общем случае не минимизирующий их количество.

Пусть $$R$$ - регулярное выражение события $$Q$$. Используя известную технику, описанную, например, в работе [77], преобразуем $$R$$ таким образом, чтобы оно представляло собой объединение событий, не содержащих итерации. При этом воспользуемся следующими известными соотношениями:

$$R_1*(R_2YR_3)=R_1*R_2YR_1*R_3,$$ $$(R_1YR_2)*R_3=R_1*R_3YR_2*R_3,$$

операции объединения и произведения событий, а вхождение итерации события $$R$$, обозначаемой через $$R*$$, заменяется выражением $$eYRYR^2Y \dots YR^m$$. Здесь $$m$$ - целое положительное число, $$R^i=R*R*\dots * R - i$$ раз, $$e$$ - пустое слово.

Вопрос о выборе $$m$$ должен решаться особо в каждом конкретном случае. На этом мы остановимся ниже. Далее будет использоваться преобразованное указанным способом регулярное выражение $$R$$, обозначаемое $$R'$$.

Предположим, что $$R'=r_{1Yr2Y} \dots Yr_i$$, где $$r_i=y_1^{(i)}*y_2^{(i)}* \dots y_{m_i}^{(i)} (1 \le I \le t)$$ и $$y_j^{(i)} \in Y$$. Для каждого $$r_i$$ и каждого $$s \in S$$ построим ориентированный граф $$G_s^A(r_i)$$.

Множество вершин этого графа обозначим через $$T$$, а построение $$G_s^A(r_i)$$ будем выполнять следующим образом:

Полагаем множество $$T$$ равным паре $$\{s,s\}$$, а значение индекса $$j$$ равным 1. Переходим к пункту 2.

По выходному сигналу $$y_j^{(i)}$$ для каждого элемента $$\{s_1,s_2\}$$ множества $$T$$ строим множество $$M_{\{s_1, s_2\}}$$ всех различных неупорядоченных пар $$\{s_1', s_2'\}$$, где $$s_1', s_2 \in S$$, удовлетворяющих следующему условию: в алфавите $$X$$ существует два таких символа $$x$$ и $$x'$$ (необязательно различных), что

$$\delta (s_1, x)=s_1', \delta (s_2, x')=s_2', \lambda (s_1.x)=\lambda (s_2,x')=y_j^{(i)}$$

Если (5.3) не выполняется ни для каких пар символов из $$X$$, то построение заканчивается. В этом случае полагаем, что граф $$G_s^A(r_i)$$ имеет пустое множество дуг и вершин.

К множеству $$T$$ добавляем все множества $$M_{\{s_1, s_2\}}$$, построенные на предыдущем этапе. Соединим вершины $$\{s_1, s_2\}$$ и $$\{s_1', s_2'\}$$, удовлетворяющие условию (5.3), дугой, началом которой служит вершина $$\{s_1, s_2\}$$, а концом $$\{s_1', s_2'\}$$. Этой дуге присваивается отметка $$(x, x', y_j^{(i)})$$. Переходим к пункту 4.

Если $$j<i$$, то $$i:=i+1$$ и переходим к пункту 2, в противном случае построение графа $$G_s^A(r_i)$$ заканчивается.

Если в графе $$G_s^A(r_i)$$ есть дуга с отметкой $$(x,x', y_j^{(i)})$$, где $$x \ne x'$$, то такую дугу назовем выделенной.

Используя графы $$G_s^A(r_i)$$, $$1 \le i \le r$$, построим теперь граф $$G_s^A(R')$$ по следующим правилам:

Множество вершин графа $$G_s^A(R')$$ является объединением множеств вершин графов $$G_s^A(r_i)$$ для всех $$i=1, \dots , l$$.

Из вершины $$g_1$$ в вершину $$g_2$$ графа $$G_s^A(R')$$ ведет дуга, если существует такое $$i_0, 1 \le i_0 \le l$$, что в графе $$G_s^A(r_{i_0})$$ вершины $$g_1$$ и $$g_2$$ также соединены дугой. Полагаем, что отметка названной дуги в графе $$G_s^A(R')$$ совпадает с отметкой той же дуги в графе $$G_s^A(r_{i_0})$$.

Проверочный граф $$G^A(R')$$, который является конечной целью построений, определим следующим образом:

Множество вершин $$G^A(R')$$ является объединением множеств вершин графов $$G_s^A(R')$$ для всех $$s \in S$$.

Из вершины $$g_1$$ в вершину $$g_2$$ графа $$G^A(R')$$ ведет дуга, если существует такое $$s_0$$, принадлежащее $$S$$, что в графе $$G_{s_0}^A(R')$$ вершины $$g_1$$ и $$g_2$$ также соединены дугой. Полагаем, что отметка названной дуги в графе $$G^A(R')$$ совпадает с отметкой той же дуги в графе $$G_{s_0}^A(R')$$.

Начальными вершинами графа $$G^A(R')$$ считаются все его вершины типа $$\{s,s\}$$.

Дугу графа $$G^A(R')$$, исходящую из вершины $$\{s,t\}$$ с отметкой $$(x,x',y)$$, обозначим $$(s,t,(x,x',y))$$.

Преобразование исходного регулярного выражения $$R$$ в выражение $$R'$$ описанным выше способом не является эквивалентным. Покажем, что, несмотря на это, проверочные графы $$G^A(R)$$ и $$G^A(R')$$ совпадают.

Рассмотрим событие $$Q*$$ и предположим, что $$Q$$ не содержит итераций. Пусть $$Q_j=eYQYQ^2Y \dots YQ^j$$. Покажем при этих предположениях, что если событие $$Q*$$ в алфавите $$Y$$ представимо в автомате $$A=(S,X,Y, \delta, \lambda), |S|=n$$, то проверочные графы $$G^A(Q*)$$ и $$G^A(Q_m)$$ совпадают, где $$m=n(n+1)/2$$.

Пусть $$S_1=\{s_1, \dots, s_k\}, k \le n$$, есть множество всех состояний автомата $$A$$, из которых представимо событие $$Q*$$. Выберем произвольным образом состояние $$s$$ из $$S_1$$ и обозначим $$\bar {F_s^i}$$ множество неупорядоченных пар состояний из $$S$$, появляющихся на последнем этапе построения $$C_s^A(Q^i)$$. Элементы $$\bar {F_s^i}$$ будем называть финальными.

Графу $$G_s^A(Q_i)$$, $$i=1,2, \dots, m$$, естественным образом поставим в соответствие автомат Рабина - Скотта $$A_i'=(\sum_i, Y, \delta_i, (s,s), f_s^i)$$, где $$\sum_i \subseteq S \times S, (s,s)$$ - начальное состояние, $$F_s^i=Y_{\nu = 1}^I \bar {F_s^{\nu}}$$ - множество финальных состояний, а функция переходов определена следующим образом: $$\delta_i'(\{s,t\}, y)=\{\bar s, \bar t\}$$, если в графе $$G_s^A(Q^i)$$ из вершины $$\{s,t\}$$ в вершину $$\{\bar s, \bar t\}$$ ведет дуга с отметкой $$(x,x',y)$$. Легко видеть, что автомат $$A_i'$$, вообще говоря, представляет событие $$P$$, такое, что $$Y_{j=1}^I Q^j \subseteq P$$ и имеет место следующее соотношение:

$$F_s^1 \subseteq F_s^2 \subseteq \dots \subseteq F_s^I \subseteq \dots$$

Поскольку автомат $$A$$ имеет $$n$$ состояний, то число различных неупорядоченных пар $$\{s,t\},s,t, \in S$$, являющихся состояниями автомата $$A_i'$$, не превышает величины $$n(n+1)/2$$. Тогда из (5.4) вытекает

$$|F_s^1| \le |F_s^2| \le \dots \le |F_s^i| \le \dots \le n(n-1)/2$$

и, следовательно, существует такое $$i_0 \le n(n+1)/2$$, что $$|F_s^{i_0}|=|F_s^{i_0+k}|$$ при любом целом положительном $$k$$. Но тогда на основании (5.4) можно сделать вывод, что $$F_s^{i_0}=F_s^{i_0+1}=F_s^{i_0+k}= \dots$$ Последнее соотношение означает, что автоматы $$A_{i_0}', A_{i_0+1}, \dots$$ представляют одно и то же событие, следовательно, графы $$G_s^A(Q^m), m=n(n+1)/2$$, и $$G_s^A(Q*)$$ совпадают. Вследствие произвольности выбора $$s$$ из $$S$$ и способа построения проверочного графа это же утверждение справедливо для графов $$G^A(Q^m)$$ и $$G^A(Q*)$$.

Рассуждения, аналогичные приведенным, показывают, что если $$Q$$ содержит итерации некоторых событий, то эти итерации также можно заменить объединением конечного числа степеней событий и при этом такая замена не приводит к изменению проверочного графа автомата.

Таким образом, нами доказана справедливость следующего утверждения.

Теорема 5.1. Если событие $$Q$$ в алфавите $$Y$$, регулярное выражение которого есть $$R$$, представимо в автомате $$A=(S, X, Y, \delta, \lambda), |S|=n$$, то проверочные графы $$G^A(R)$$ и $$G^A(R')$$, где $$R'$$ получено из $$R$$ путем замены каждого вхождения итерации события $$T$$ на $$Y_{i=1}^{n(n+1)/2} T^i$$, совпадают.

Из доказательства этой теоремы следует, что если $$R'$$ является объединением всех возможных слов, принадлежащих $$R$$, длина которых не превосходит величины $$n(n+1)/2$$, то графы $$G^A(R')$$ и $$G^A(R)$$ для автомата $$A$$ совпадают. Это замечание позволяет упростить практическое построение графа $$G^A(R)$$.

Сформулированная ниже теорема будет служить критерием, используемым при преобразовании произвольного автомата в $$P$$ -БПИ-автомат. Ее доказательство аналогично доказательству теоремы 2 из [74].

Пусть $$R$$ - регулярное выражение события $$Q=Y_{s \in S} \lambda_s (P)$$.

Теорема 5.2. Для того чтобы автомат $$A$$ был $$P$$ -БПИ-автоматом, необходимо и достаточно, чтобы в его проверочном графе $$G^A(R)$$ для любого слова $$p \in P$$ каждый соответствующий ему путь не содержал выделенной дуги, исходящей из вершины $$\{s,s\}$$, а также дуги, заходящей в вершину такого же типа.

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

Задача 1. В проверочном графе $$G^A(R)$$ найти такое множество $$L$$ его дуг, чтобы полученный в результате их удаления новый граф удовлетворял условиям теоремы 5.2.

Задача 2. По заданному множеству $$L$$ дуг построить такое максимальное разбиение $$\Pi$$ множества $$Z=S \times Y$$, чтобы выполнялись условия:

если дуга $$(s,t,(x_i, x_j, y))$$ графа $$G^A(R)$$ принадлежит множеству $$L$$, то $$(s, x_i)$$ и $$(t, x_j)$$ находятся в разных классах разбиения;

для всех $$\Pi'$$, удовлетворяющих условию (a), выполняется условие (5.2).

Обе сформулированные задачи принадлежат к числу сложных комбинаторных задач, методы решения которых, отличные от перебора, пока не известны. В работе [23] предложены методы решения задач, подобных задачам 1 и 2, не гарантирующие минимальности, но не содержащие перебора.

Решение задачи 2 можно получить по алгоритму $$A1$$ из [23], если положить в нем $$Z=N$$, а симметричное бинарное отношение $$\varphi \subset Z \times Z$$ определить следующим образом: $$((s,x_i), (t, x_j)) \in \varphi$$, если и только если существует такое $$y \in Y$$, что $$\lambda (s, x_i)= \lambda (t, x_j)= y, (s,t,(x_i, x_j, y)) \ne L$$.

Перейдем к рассмотрению первой задачи. По графу $$G^A(R')$$ построим множество $$C$$ всех простых путей длины большей 1, удовлетворяющих следующим условиям:

путь начинается выделенной дугой, исходящей из вершины типа $$\{s,s\}$$, и заканчивается дугой, заходящей в вершину такого же типа;

ни один путь из $$C$$ не должен являться отрезком никакого другого пути из $$C$$ ;

каждый путь в $$C$$ должен соответствовать некоторому отрезку выходного слова, принадлежащего событию $$Q$$ ;

каждый путь в $$C$$ не содержит выделенной дуги, соединяющей вершины типа $$\{s,s\}$$.

Каждой дуге графа $$G^A(R')$$, входящей в состав путей из $$C$$, присвоим вес, равный числу путей в $$C$$, содержащих эту дугу.

Пусть $$F$$ - множество выделенных дуг графа $$G^A(R')$$, каждая из которых соединяет вершины типа $$\{s,s\}$$.

Рассмотрим проверочный граф $$G^A(R')$$ автомата $$A=(S,X,Y, \delta, \lambda )$$, где $$R$$ - регулярное выражение события $$Q=y_{s \in S} \lambda_s(P)$$. Выделим все слова $$p$$ из $$P$$, такие, что соответствующие им пути в графе $$G^A(R')$$ содержат выделенные дуги, исходящие из вершины типа $$\{s,s\}$$, а также дуги, заходящие в вершину такого же типа. Множество всех таких путей обозначим через $$M$$. Легко видеть, что множество всех путей $$C$$ и множество выделенных дуг $$F$$ принадлежат $$M$$: все пути из $$M$$, не совпадающие с путями из $$C$$ и $$F$$, содержат их в качестве отрезков.

Отсюда следует, что если в графе $$G^A(R')$$ отсутствуют пути из множеств $$C$$ и $$F$$, то и пути из множества $$M$$ в нем также отсутствуют. Таким образом, из теоремы 5.2 вытекает, что для преобразования автомата $$A$$ в $$P$$ -БПИ-автомат достаточно из графа $$G^A(R')$$ удалить все пути множества $$C$$ и все выделенные дуги множества $$F$$.

Перейдем к рассмотрению алгоритма, позволяющего по множествам $$C$$ и $$F$$ строить такое множество $$L$$ дуг графа $$G^A(R')$$, чтобы после их удаления из этого графа в нем отсутствовали все пути из $$C$$ и все дуги из $$F$$.

Алгоритм выбора множества дуг $$L$$ можно сформулировать следующим образом.

Полагаем $$L=F$$, где $$F$$ - множество выделенных дуг графа $$G^A(R')$$, каждая из которых соединяет вершины типа $$\{s,s\}$$. Если $$F= \varnothing$$, то перейти к пункту 2, иначе к пункту 4.

Из множества $$C$$ выделяем множество $$F_1$$ всех дуг, имеющих максимальный вес.

Добавляем в $$L$$ одну дугу из $$F_1$$, выбранную произвольно.

Из графа $$G^A(R')$$ удаляем дуги, входящие в множество $$F= \varnothing$$. Вновь полученный граф обозначаем также $$G^A(R')$$.

Из множества $$C$$ удаляем пути, содержащие дуги из множества $$C$$, построенного на предыдущем этапе. Если $$C= \varnothing$$, то построение $$L$$ окончено, иначе переходим к пункту 6.

Произво

Пусть $$L=\{(c_1, d_1, (x_{k_1}, x_{k_1}', y_{k_1})), \dots, (c_{\nu}, d_{\nu}, (x_{k_{\nu}}, x_{k_{\nu}}', y_{k_{\nu}}))\}$$ получено по описанному алгоритму, причем дуги в $$L$$ занумерованы в том порядке, в котором они присоединялись к $$L$$ в соответствии с алгоритмом. Пусть $$C-i$$ - подмножество всех путей из множества $$C$$, проходящих через дугу $$(c_i, d_i, (x_{k_i}, x_{k_i}', y_{k_i}))$$.

Лемма 5.1. Для любых $$a \ne b, 1 \le a,b \le \nu$$ справедливо соотношение $$c_a \not \subset c_b $$.

Доказательство. Для определенности положим, что $$alt;b$$. На основании пункта 4 алгоритма из $$G^A(R')$$ удаляется дуга $$(c_a, d_a, (x_{k_a}, x_{k_a}', y_{k_a}))$$, что влечет за собой удаление из этого же графа и всех путей из множества $$C_a$$. Это же множество путей удаляется из $$C$$ на основании пункта 5 алгоритма. Присоединение дуги $$(c_b, d_b, (x_{k_b, x_{k_b}', y_{k_b}}))$$ к множеству $$L$$ на основании пункта 2 алгоритма возможно лишь в том случае, если в множестве $$C$$, полученном на предыдущем этапе, есть по крайней мере один путь, проходящий через эту дугу. Поскольку $$C$$ после проведенной корректировки заведомо не содержит $$C_a$$, отсюда следует, что $$С_a \not \subset С_b $$. Обратное соотношение $$С_b \not \subset С_a $$ тоже справедливо, так как в противном случае после удаления дуги $$(c_a, d_a, (x_{k_a}, x_{k_a}', y_{k_a}))$$ из графа $$G^A(R)$$ все пути множества $$C_b$$ были также удалены, что противоречит предположению о наличии дуги $$>(c_b, d_b, (x_{k_b}, x_{k_b}', y_{k_b}))$$ во множестве $$L$$.

В качестве следствия леммы получаем, что для любого $$I, 1 \le I \le \nu$$, справедливы соотношения $$Y_{j=1}^{i-1}C_j \not \subset C_i$$ и $$C_i \not \subset Y_{j=1}^{i-1}C_j$$.

Отметим следующий очевидный факт: множество выделенных дуг $$F$$ заведомо принадлежит решению задачи 1 независимо от того, получено ли оно по описанному алгоритму или иным способом.

Из изложенного выше следует, что по предложенному алгоритму строится множество $$L$$, не являющееся избыточным в том смысле, что на каждом его шаге из графа $$G^A(R)$$ удаляется непустое множество путей, принадлежащих $$C$$. Если $$L=F$$, то мощность $$L$$ минимальна и $$L$$ строится за один шаг.

Рассмотренная нами задача построения множества $$L$$ дуг эквивалентна задаче о покрытии, или задаче построения минимальной формы булевой функции. Если проводить аналогию с последней задачей, то построенное с помощью предложенного алгоритма множество $$L$$ соответствует в силу леммы 5.1 приведенной системе простых импликант. Таким образом, вопрос о близости минимального по мощности решения задачи 1 и решения, построенного с помощью предложенного алгоритма, эквивалентен вопросу о близости приведенной системы простых импликант к минимальной приведенной системе импликант (минимальной форме булевой функции). Продолжая аналогию, заметим, что из построенного по предложенному алгоритму множества $$L$$ некоторые дуги можно удалять способом, подобным способу удаления импликант из приведенной системы [21].

Проиллюстрируем предложенный способ преобразования автомата в $$P$$ -БПИ-автомат на примере.

Рассмотрим автомат $$A$$, заданный табл. 5.1. Пусть $$R=a(ba*)*a$$.


s\x	0	1	2	3
1	2, a	3, a	2, a	1, c
2	4, a	1, b	2, c	3, c
3	2, b	4, a	3, d	2, f
4	3, a	2, b	4, f	3, d

Вследствие замечания к теореме 5.1 в рассматриваемом примере нам достаточно ограничиться при замене итерации по изложенному выше способу значением $$m$$, равным 8, так как в выражении $$R$$ до и после итерации $$(ba*)*$$ стоит символ $$a$$ и с учетом этого длина слов в $$R'$$ будет доведена до 10 (значение $$n(n+1)/2$$ при $$n=4$$ ) и при этом значении $$m$$. В результате преобразования $$R$$ получим следующее выражение:

$$R'=a^2\cup aba^2\cup aba^3\cup aba^4\cup aba^5\cup aba^6\cup aba^7\cup aba^8\cup \\ \cup a(ab)^2a\cup a(ba)^2a^2\cup a(ba)^2a^3\cup a(ba)^2a^4\cup a(ba)^2a^5\cup \\ \cup a(ba^2)^2\cup aba^2ba^3\cup aba^2ba^4\cup aba^2ba^5\cup aba^3ba^2\cup aba^3ba^3\cup \\ \cup aba^3ba^4\cup aba^4ba^2\cup aba^4ba^3\cup aba^5ba^2\cup a(ba)^3a\cup a(ba)^3a^2\cup \\ \cup a(ba)^3a^3\cup a(ba)^2aba^2\cup (ab)^2a^2ba^3\cup (ab)^2a^3ba^2\cup aba^2(ba)^2a\cup \\ \cup aba^2(ba)^2a^2\cup aba^2(ba^2)^2\cup aba^3(ba)^2a$$

Граф $$G^A(R')$$, или, что то же самое, $$G^A(R)$$, имеет вид, изображенный на рис. 5.2, где двойные стрелки соответствуют выделенным дугам.

(рис 5.2)

Множество путей $$C$$ в нашем случае таково:

$$1,1 \stackrel{0,1,a}{\Longrightarrow} 2,3 \stackrel{0,1,a}{\Longrightarrow} 4,4;$$ $$1,1 \stackrel{1,2,a}{\Longrightarrow} 2,3 \stackrel{0,1,a}{\Longrightarrow} 4,4;$$ $$1,1 \stackrel{0,1,a}{\Longrightarrow} 2,3 \stackrel{0,1,b}{\Longrightarrow} 1,2 \stackrel{1,0,a}{\Longrightarrow} 3,4 \stackrel{0,1,b}{\Longrightarrow} 2,2;$$ $$1,1 \stackrel{1,2,a}{\Longrightarrow} 2,3 \stackrel{1,0,b}{\Longrightarrow} 1,2 \stackrel{0,1,a}{\Longrightarrow} 3,4 \stackrel{0,1,b}{\Longrightarrow} 2,2$$ $$1,1 \stackrel{0,1,a}{\Longrightarrow} 2,3 \stackrel{0,1,b}{\Longrightarrow} 1,2 \xrightarrow {0,0,a} 2,4 \xrightarrow {0,0,a} 3,4 \stackrel{0,1,b}{\Longrightarrow} 2,2$$ $$1,1 \stackrel{1,2,a}{\Longrightarrow} 2,3 \stackrel{1,0,b}{\Longrightarrow} 1,2 \xrightarrow {0,0,a} 2,4 \xrightarrow {0,0,a} 3,4 \stackrel{0,1,b}{\Longrightarrow}2,2;$$ $$1,1 \stackrel{0,1,a}{\Longrightarrow} 2,3 \stackrel{1,0,b}{\Longrightarrow} 1,2 \stackrel{1,0,a}{\Longrightarrow} 3,4 \stackrel{0,1,a}{\Longrightarrow} 3,4 \stackrel{0,1,b}{\Longrightarrow}2,2;$$ $$1,1 \stackrel{1,2,a}{\Longrightarrow} 2,3 \stackrel{1,0,b}{\Longrightarrow} 1,2 \stackrel{1,0,a}{\Longrightarrow}3,4 \stackrel{0,1,a}{\Longrightarrow}3,4 \stackrel{0,1,b}{\Longrightarrow}2,2;$$ $$1,1 \stackrel{0,1,a}{\Longrightarrow} 2,3 \stackrel{0,1,b}{\Longrightarrow} 1,2 \stackrel{0,2,a}{\Longrightarrow}2,4 \xrightarrow {0,0,a} 3,4 \stackrel{0,1,b}{\Longrightarrow}2,2;$$ $$1,1 \stackrel{1,2,a}{\Longrightarrow} 2,3 \stackrel{1,0,b}{\Longrightarrow} 1,2 \stackrel{0,2,a}{\Longrightarrow}2,4 \xrightarrow {0,0,a} 3,4 \stackrel{0,1,b}{\Longrightarrow}2,2.$$

В соответствии с предложенным выше алгоритмом выбора $$L$$ на первом шаге получаем $$L=\{(1,1,(0,2,a))\}$$.

Далее, максимальный вес, равный 8, в множестве $$C$$ имеют дуги $$(3,4,(0,1,b))$$ и $$(2,3,(1,0,b))$$ ; тогда полагаем $$L=\{(1,1,(0,2,a)); (3,4,(0,1,b))\}$$, выбрав первую из названных дуг. После корректировки в множестве $$C$$ остается два первых пути из списка, приведенного выше. Поскольку вес дуги $$(2,3,(0,1,a))$$ максимален (он равен 2), то добавляем ее в $$L$$ и на этом процесс построения $$L$$ заканчивается, так как множество $$C$$ после повторной корректировки пустое. Таким образом, $$L=\{(3,4,(0,2,a)); (2,3,(0,1,a))\}$$

Используя алгоритм $$A1$$ из [23], получаем следующее разбиение множества $$Z=S \times X$$:

$$\Pi = \overline {(1,0), (1,1),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,2),(3,3),(4,0),(4,2),(4,3)};\\ \overline {(1,2),(3,1),(4,1)}$$

Это разбиение имеет два класса, следовательно, для кодирования символов классов достаточно, например, одной двоичной переменной. Пусть $$K_1=0$$ и $$K_2=1$$, тогда автомат с контрольными точками будет представлен в табл. 5.2.


s\x	0	1	2	3
1	2, a 0	3, a 0	2, a 1	1, c 0
2	4, a 0	1, b 0	2, c 0	3, c 0
3	2, b 0	4, a 1	3, d 0	2, f 0
4	3, a 0	2, b 1	4, f 0	3, d 0

Отметим, что идея изложенного метода преобразования автоматов очевидным образом может быть использована и для решения следующей задачи: для заданного регулярного множества $$P$$ непустых входных слов вывести выходные контрольные точки в автомате таким образом, чтобы каждое слово из $$P$$ стало диагностическим для автомата с контрольными точками.

Предложенный метод решения задачи 1 в качестве одного из этапов содержит построение путей множества $$C$$, выполняемого визуально по проверочному графу. Такое построение становится тем более затруднительным, чем большее число состояний имеет данный автомат. В связи с этим рассмотрим формализованный метод построения такого множества $$L'$$ дуг автомата $$A$$, что удаление их превращает автомат $$A$$ в $$P$$ -БПИ-автомат. В основу метода положим представление автомата в виде матрицы переходов и выполнение операций над этой матрицей, описанных, например, в работе [18].

Напомним, что для автомата $$A$$, имеющего $$n$$ состояний, матрица переходов состоит из $$n$$ строк и $$n$$ столбцов и обозначается $$[A]$$. Пусть $$S=\{s_1, \dots, s_n\}$$ - множество состояний автомата $$A$$ и пусть $$s_i \xrightarrow {x,y} s_j$$ обозначает дугу графа автомата $$A$$, направленную от $$s_i$$ к $$s_j$$ под воздействием входного сигнала $$x$$ с выдачей выходного сигнала $$y$$. Элемент $$(i,j)$$ матрицы $$[A]$$, т. е. содержимое клетки, расположенной на пересечении $$i$$ -й строки и $$j$$ -го столбца, содержит все дуги, ведущие из вершины $$s_i$$ в вершину $$s_j$$. Если такие дуги отсутствуют, то элемент $$(i,j)$$ полагается равным нулю.

Условимся считать, что обозначение $$k$$ -го состояния $$s_k$$ приписано $$k$$ -й строке и $$k$$ -му столбцу матрицы переходов.

В работе [18] введена операция возведения в степень матрицы переходов $$[A]$$ и доказано, что элемент $$(i,j)$$ матрицы $$[A]^k, k=1,2,\dots$$, является множеством всех путей длины $$k$$, ведущих из состояния $$s_i$$ в состояние $$s_j$$ автомата $$A$$. Этот факт и является основой для формализованного нахождения тех путей в графе автомата $$A$$, которые являются причиной потери информации.

Построение множества $$L'$$ дуг, упомянутого выше, будет проводиться в виде пошагового процесса. Одновременно с этим будет проводиться построение "каркаса" разбиения $$\Pi$$ множества $$Z$$.

Вначале произведем следующие преобразования над матрицей переходов автомата $$A$$:

удаляем из $$[A]$$ все дуги, имеющие в качестве выходных символы, не содержащиеся в выражении $$Q$$ ;

если элемент $$(i,j)$$ матрицы $$[A]$$ содержит две дуги с различными входными, но одинаковыми выходными символами, то одну из этих дуг, выбираемую произвольно, включаем в множество $$L'$$ и удаляем ее из матрицы $$[A]$$.

Отметим при этом, что удаленная и оставленная в матрице $$[A]$$ дуги должны находиться в разных классах разбиения $$\Pi$$ (это и есть информация о "каркасе" разбиения $$\Pi$$ ).

Описанный процесс продолжается далее до тех пор, пока элемент $$(i, j)$$ не будет содержать ни одной пары дуг с указанным выше свойством.

Легко видеть, что удаленные в соответствии с пунктом (a) дуги заведомо таковы, что путь в графе автомата $$A$$, соответствующий любому слову из заданного регулярного множества $$P$$, не может содержать их.

Удаление из матрицы $$[A]$$ дуг согласно пункту (b) соответствует удалению выделенных дуг множества $$F$$ из проверочного графа $$G^A(R)$$. Очевидно, что пара дуг графа автомата $$A$$ с различными входными, но одинаковыми выходными символами является выделенной дугой проверочного графа $$G^A(R)$$.

Преобразованную описанным способом матрицу переходов будем, как и ранее, обозначать $$[A]$$.

Описываемые ниже преобразования будут производиться над матрицами $$[A]^k$$ при $$k=1,2, \dots$$, получаемыми из $$[A]^{k-1}$$ путем умножения ее слева на преобразованную матрицу переходов $$[A]$$.

Итак, рассмотрим матрицу переходов $$[A}^k$$. Произведем над ней следующие преобразования:

Если элемент $$(i,j)$$ матрицы $$[A]^k$$ содержит два пути, которым соответствуют различные входные, но одинаковые выходные слова, то каждой дуге, входящей в состав этих путей, присваиваем вес, равный числу вхождений этой дуги во все пути матрицы переходов $$[A]^k$$. Дугу с максимальным весом включаем в множество $$L'$$ и удаляем из $$[A]^k$$ все пути, содержащие эту дугу. Из матрицы переходов $$[A]$$ дуга с максимальным весом также удаляется.

Этот процесс продолжается далее до тех пор, пока элемент $$(i, j)$$ не будет содержать ни одной пары путей с описанным выше свойством.

Среди всех путей матрицы $$[A]^k$$ находим пути, соответствующие входным (выходным) словам, которые не могут являться отрезками никаких слов из заданного множества $$P(Q)$$. Указанные пути удаляются из матрицы переходов $$[A]^k$$.

Как уже было отмечено, удаление дуг множества $$L'$$ из графа автомата $$A$$ соответствует удалению дуг некоторого множества $$\tilde L$$ из проверочного графа $$G^A(R)$$.

Пусть выполнены описанные выше преобразования над матрицей переходов $$[A]$$ и при этом получено множество $$L'$$ дуг графа автомата $$A$$. Удаляем из $$G^A(R)$$ множество $$\tilde L$$ дуг, соответствующее множеству $$L'$$, и проверяем выполнение условий теоремы 5.2. Если условия выполняются, то преобразования матриц переходов на этом завершаются. Для построения искомого разбиения $$\Pi$$ можно далее воспользоваться уже описанным методом. Если же условия теоремы 5.2 не выполняются, то вычисляем следующую степень матрицы переходов $$[A]$$ и выполняем над ней описанные преобразования. Затем вновь следует проверка условий теоремы 5.2 и процесс продолжается аналогичным образом.

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

Продемонстрируем предложенный метод на примере, который уже был рассмотрен выше. Итак, пусть автомат $$A$$ задан табл. 5.1, а множество $$Q$$ задается выражением $$R=a(ba*)*a$$.

Исходная матрица переходов имеет следующий вид:

$$[A]= \left [ \begin {matrix} 1 \xrightarrow {1,c}1 1\xrightarrow {2,c}2 1\xrightarrow {1,a}3 0\\ 1\xrightarrow {0,a}2\\ 2\xrightarrow {1,b}1 2\xrightarrow {2,c}2 2\xrightarrow {3,c}3 2\xrightarrow {0,a}4\\ 0 3\xrightarrow {0,b}2 3\xrightarrow {2,d}3 3\xrightarrow {1,a}4\\ 3\xrightarrow {0,f}2 \\ 0 4\xrightarrow {1,b}2 4\xrightarrow {0,a}3 4\xrightarrow {2,f}4\\ 4\xrightarrow {3,d}3 \end {matrix} \right ]$$

Преобразованная матрица после удаления дуг из элементов (1,1), (2,2), (2,3), (3,2), (3,3), (4,3), (4,4) на основании пункта (a) и дуги $$1 \xrightarrow {2,a}2$$ из элемента (1,2) на основании пункта (b) примет вид

$$[A]= \left [ \begin {matrix} 0 1\xrightarrow {0,a}2 1\xrightarrow {1,a}30\\ 2\xrightarrow {1,b}002\xrightarrow {0.a}\\ 0 3\xrightarrow {0,b}3 0 3\xrightarrow {1,a}4\\ 04\xrightarrow {1,b}24\xrightarrow {0,a}30 \end {matrix} \right ]$$

Дуга $$1\xrightarrow {2,a}2$$ включается в множество $$L'$$, причем она должна быть в разных классах разбиения $$\Pi$$ с дугой $$1\xrightarrow {0,a}2$$. Указанной паре дуг в проверочном графе $$G^A(R)$$ соответствует выделенная дуга $$\{1,1\}==\stackrel{0,2,a}{\Longrightarrow} \{2,2\}$$.

После удаления выделенной дуги из $$G^A(R)$$ этот граф не удовлетворяет условиям теоремы 5.2, поэтому вычислим матрицу переходов $$[A]^2$$:

$$[A]^2= \left [ \begin {matrix} 1\xrightarrow {0,a}2\xrightarrow {1,b}1 1\xrightarrow {1,a}3\xrightarrow {0,b}20 1\xrightarrow {0,a}2\xrightarrow {0,a}4\\ 1\xrightarrow {1,a}3\xrightarrow {1,c}4\\ 02\xrightarrow {1,b}1\xrightarrow {0,a}2 2\xrightarrow {1,b}1\xrightarrow {1,a}30\\ 2\xrightarrow {0,a}4\xrightarrow {1,b}2 2\xrightarrow {0,a}4\xrightarrow {0,a}3\\ 3\xrightarrow {0,b}2\xrightarrow {1,b}1 3\xrightarrow {1,a}4\xrightarrow {1,b}2 3\xrightarrow {1,a}4 \xrightarrow {0,a}3 3\xrightarrow {0,b}2\xrightarrow {0,a}4\\ 4\xrightarrow {1,b}2\xrightarrow {1,b}1 4\xrightarrow {0,a}3\xrightarrow {0,b}2 0 4\xrightarrow {1,b}2\xrightarrow {0,a}4\\ 4\xrightarrow {0,a}3\xrightarrow 1,a}4 \end {matrix} \right ]$$

Удалим дуги из элементов (3,1) и (4,1) на основании пункте 2, так как слово $$bb$$ не принадлежит событию $$a(ba*)*a$$. Пути элемента (1,4) удовлетворяют условию, сформулированному в пункте 1. Максимальный вес (равный 5) среди всех дуг, входящих в состав этих путей, имеет дуга $$2\xrightarrow {0,a}4$$. Включаем эту дугу в множество $$L'$$ и удаляем из $$[A]^2$$ все пути, содержащие ее. После этого преобразования матрица примет следующий вид:

$$[A]^2= \left [ \begin {matrix} 1\xrightarrow {0,a}2\xrightarrow {1,b}1 1\xrightarrow {1,a}3\xrightarrow {0,b}2 0 1\xrightarrow {1,a}3\xrightarrow {1,c}4\\ 0 2\xrightarrow {1,b}1\xrightarrow {0,a}2 2\xrightarrow {1,b}1\xrightarrow {1,a}3 0\\ 0 3\xrightarrow {1,a}4\xrightarrow {1,b}2 3\xrightarrow {1,a}4\xrightarrow {0,a}3 0\\ 0 4\xrightarrow {0,a}3\xrightarrow {0,b}2 0 4\xrightarrow {0,a}3\xrightarrow {1a}4 \end {matrix} \right ]$$

Удаление дуги $$2 \xrightarrow {0,a}4$$ из графа автомата $$A$$ соответствует удалению выделенных дуг $$\{2,3\} ==\stackrel{0,1,a}{\Longrightarrow} \{4,4\}; \{1,2\} ==\stackrel{0,2,a}{\Longrightarrow} \{2,4\}; \{1,2\} ==\stackrel{1,0,a}{\Longrightarrow} \{3,4\}$$ в проверочном графе $$G^A(R)$$, а также дуги $$\{1,2\} \xrightarrow {0,0,a} \{2,4\}$$.

Легко проверить, что после удаления названных дуг граф $$G^A(R)$$ удовлетворяет условиям теоремы 5.2.

Таким образом, изменив выходные сигналы при переходах $$1\xrightarrow {2,a} 2$$ и $$2 \xrightarrow {0,a} 4$$ в графе автомата $$A$$, например, следующим образом: $$1 \xrightarrow {2, a1} 2, 2\xrightarrow {0,a1} 4$$, мы удовлетворяем требованию, чтобы дуги $$1 \xrightarrow {2, a1} 2, 1 \xrightarrow {0,a} 2$$, принадлежали разным классам разбиения.

Поскольку число полученных классов разбиения равно 2, то для кодирования символов классов достаточно одной двоичной переменной. Это означает, что у автомата $$A$$ достаточно вывести одну дополнительную выходную контрольную точку. Таблицей автомата с контрольными точками в силу сказанного выше является табл. 5.3.


s\x	0	1	2	3
1	2, a 0	3, a 0	2, a 1	1, c 0
2	4, a 1	1, b 0	2, c 0	3, c 0
3	2, b 0	4, a 0	3, d 0	2, f 0
4	3, a 0	2, b 0	4, f 0	3, d 0

Итак, мы получим еще один вариант автомата с контрольными точками, являющегося $$P$$ -БПИ-автоматом, где событие $$Q$$ представлено выражением $$R=a(ba*)*a$$.

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

Дайте определение автомата БПИ на заданном регулярном множестве его входных слов.

Сформулируйте основную идею метода решения задачи преобразования автомата в автомат БПИ на регулярном множестве слов.

Сформулируйте две вспомогательных задачи, к решению которых сводится проблема исследуемого преобразования автомата в автомат БПИ.

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

Страницы: