1.4. Свойства классов k - эквивалентности автоматов. Построение сокращенных автоматов
Для построения итоговых классов эквивалентности {Q} и сокращения автоматов могут быть использованы их классы k - эквивалентности {Q}k (k=1,2,...,).
Свойства классов k – эквивалентности.
1. При любых k справедливо: {Q}k+1 {Q}k.
Данное свойство очевидно, поскольку из совпадения реакций А(Qi, Хk+1) длины k+1 для состояний вытекает совпадение и более коротких реакций А(Qi, Хk) длины k.
Из свойства 1 вытекает, что при увеличении k классы k – эквивалентности могут распадаться на более мелкие (рас-щепляться) либо сохраняться (стабилизироваться).
2. Если для некоторого k выполняется условие {Q}k+1 = {Q}k (т.е. все классы k –эквивалентности стабилизирова-лись), то равенство {Q}l = {Q}k, будет выполняться и для всех значений глубины l>k+1. Это означает, что с ростом k стабильность классов k –эквивалентности сохранится.
Доказательство. Достаточно доказать, что из условия {Q}k+1 = {Q}k вытекает справедливость утверждения {Q}k+2 = {Q}k+1. Из определения k – эквивалентности для этого необ-ходимо доказать, что для любых двух (k+1)– эквивалентных
291
состояний Qi, Qj (входящих в некоторый класс (k+1)– эквивалентности Q(k+1),s и взятых качестве начальных) и лю-бого входного словаХ=(Х(t1), Х(t2), …Х(tk+2)) длины k+2 со-ответствующие выходные слова Z(Х, Qi) иZ(Х, Qj) бу-дут совпадать.
Рассмотрим работу автомата в момент времени t1. При начальных состояниях Qi, Qj функция выходов F даст некоторые одинаковые элементы Z1 :
F: ( Х(t1), Qi ) = Z(t1); F :( Х(t1), Qj) = Z(t1).
Функция переходов G выдаст, соответственно, некото-рые значения состояний:
G: ( Х(t1), Qi ) = Q(Х(t1), Qi ); G :( Х(t1), Qj) = Q(Х(t1), Qj ).
Новые состояния Q(Х(t1),Qi) и Q(Х(t1),Qj) будут k – эквивалентными, поскольку начальные состояния Qi, Qj являются (k+1) – эквивалентными. При этом возможно, со-стояния Q(Х(t1),Qi) и Q(Х(t1),Qj) будут совместно входить в некоторый класс k – эквивалентности Qk,r, отличный от Qk,s. Однако по условию все классы k – эквивалентности авто-мата совпадают со своими (k+1) – эквивалентными клас-сами. Отсюда следует, что класс Qk,r, в который входят состояния Q(Х(t1),Qi) и Q(Х(t1),Qj), будет (k+1) – эквива-лентным и при данных начальных состояниях автомат переведет остаток входного слова (Х(t2), …Х(tk+2)) длины k+1 в одинаковые выходные слова вида (Z(t2)… Z(tk+2)) .
Таким образом, получаем, что для любого входного словаХ длины k+2 при начальных состояниях Qi, Qj, входя-щих в некоторый класс (k+1) – эквивалентности Q(k+1),s, по-лучено одинаковое выходное словоZ =( Z(t1)Z(t2)…Z(tk+2)) .
В силу произвольности состояний Qi, Qj, получим: {Q}k+2 = {Q}k+1, что и требовалось доказать.
Следствие 1 из Свойства 2. Если для некоторого k классы эквивалентности стабилизировались ({Q}k+1 = {Q}k), то разбиение {Q}k является искомым итоговым разбиением
292
множества внутренних состояний автомата на классы экви-валентности: {Q} = {Q}k.
Следствие 2 из Свойства 2. Процесс расщепления классов k – эквивалентности ограничен по числу шагов, поскольку ограничено общее число внутренних состояний, а следовательно – и состояний в классах k – эквивалент-ности. Предельное число k определяет
Теорема Хаффмена-Мили.
Для эквивалентности двух состояний Qi, Qj автомата Мили А = (Х, Z, Q, F, G) с P>1 внутренними состояниями (Q=P) достаточно, чтобы совпадали реакции данных состояний на входных словах длины P-1 .
Доказательство. Максимальное число 1-эквивалентных со-стояний у автомата равно P-1. Если бы все P состояний автомата были бы 1-эквивалентными, то они будут и полно-стью эквивалентными. Следовательно, для проверки их эквивалентности достаточно совпадения реакции всех состояний на входных словах 1. При мощности класса {Q}1= P-1 максимальное число расщеплений равно P-2. При этом максимально достижимая величина k = P-1, что и требова-лось доказать.
Замечание. Как будет показано в Примере 1, длину реакций в общем случае уменьшить нельзя, т.е. предельная величина k = P-1 достигается.
Из рассмотренных свойств классов k – эквивалент-ности вытекает простейший алгоритм построения сокра-щенных автоматов, который заключается в последователь-ном определении классов эквивалентности {Q}k до тех пор, пока их структура не стабилизируется.
Пример 1. Произвести сокращение автономного авто-мата, граф переходов которого дан на Рис.5.3 в п 1.3.
Решение.
k=1. А(Q1, а)=А(Q2, а)= …= А(QP-1, а)=у, А(QP, а)= z, cледо-вательно, {Q}1 = {(Q1, Q2, …, QP-1 ), (QP )}.
293
k=2. А(Q1,а)=А(Q2,а)= …= А(QP-2,а) = уу, А(QP-1, а)= zу, А(QP, а)= уz, {Q}1 = {(Q1, Q2, …, QP-2), (QP-1 ), (QP )}.
k=3. А(Q1,а)=А(Q2,а)= …= А(QP-3,а) = ууу, А(QP-2,а) = zуу, А(QP-1, а)=уzу, А(QP, а)= ууz, {Q}3 = {(Q1, Q2, …,QP-3), (QP-2 ), (QP-1 ), (QP )}.
…
k=Р-1. А(Q1, а)= уP-1, А(Q2, а)= zуP-2, А(Q3, а)= уzуP-3, …, А(QP, а)= уP-2z, {Q} P-1 = {(Q1), (Q2), …, (QP-1 ), (QP )}.
Поскольку разбиение на классы (P-1)- эквивалентнос-ти содержит по одному состоянию в каждом классе, дальше его можно не производить. Отсюда следует, что автомат является сокращенным и не содержит ни одной пары экви-валентных состояний.
Пример 2. Произвести сокращение автомата, граф переходов которого дан в Примере 1 п.1.3.
Решение.
k=1. А(Q1,а)=А(Q1,b)=z; А(Q2,а)=x;А(Q2,b)=y; А(Q3,а)=x; А(Q3,b)=y. {Q}1 = {(Q1),(Q2,Q3 )}.
k=2. На этом шаге достаточно проверить класс эквивалент-ности (Q2,Q3). Из Таблицы, построенной в Примере 2 п.1.3, следует, что данный класс на рассматриваемом шаге стаби-лизируется. Отсюда получаем итоговое разбиение множест-ва состояний на классы эквивалентности: {Q} = {Q}2 = {(Q1),(Q2,Q3 )}.
Заменяя состояния Q2, Q3 одним состоянием Q2, полу-чим сокращенный автомат с двумя внутренними состояни-ями, эквивалентный исходному автомату. Граф переходов сокращенного автомата дан на Рис.5.5.
Разработан ряд более оптимальных методов алгорит-мов для определения эквивалентных состояний и построе-ния сокращенных автоматов. Данные алгоритмы приво-дятся в специальной литературе по теории автоматов.
294
Рис.5.5
Задачи.
I. Определить эквивалентные состояния и произвести со-кращение для следующих автоматов, заданных графами пе-реходов:
1)
Рис.5.6
2)
Рис.5.7
295
3)
Рис.5.8
4)
Рис.5.9
296
II. Строго доказать, что если в автомате Мили А = (Х, Z, Q, F, G) множество классов 1-эквивалентности {Q}1 = Q, то все внутренние состояния автомата эквивалентны.
III. Построить пример графа переходов для автомата со сле-дующими числовыми характеристиками (Х=2,Q=6, Z=3), имеющего классы эквивалентности {Q} = {(Q1, Q2), ( Q3 , Q4 , Q5 )}.
IV. Построить пример графа переходов для автомата с P внутренними состояниями, у которого для определения эквивалентных состояний необходимо исследование реак-ций состояний на входных словах длины P-2 .