[Список тем]

Эквивалентность КА: теорема Мура

Две булевы функции Ф и F эквивалентны, если на всех возможных интерпретациях они принимают одинаковые значения. Поскольку число интерпретаций у булевыx функций конечно, то, перебрав их все, можно проверить, эквивалентны ли Ф и F. Если число интерпретаций велико, можно привести Ф и F к нормальной формe и сравнить их представления. Для проверки эквивалентности Ф и F можно также проверить аналитически, будет ли общезначима функция Ф = F.

Иная ситуация с конечными автоматами. Два конечных автомата эквивалентны, если реализуемые ими отображения вход-выход эквивалентны. Конечный автомат реализует отображение бесконечного множества входных последовательностей сигналов в бесконечное множество выходных последовательностей сигналов. Поэтому автоматные отображения нельзя сравнить простым перечислением их значений на всех возможных аргументах. Дадим несколько определений. Расширим функции перехода и выхода автомата так, чтобы они были определены на множествах последовательностей (цепочках) сигналов входного алфавита. Пусть - алфавит (конечное множество символов) и ^* множество цепочек из элементов . Будем о бозначать ε пустую цепочку, вовсе не содержащую символов, а ^ - операцию конкатенации (склеивания) цепочек. Так, аав^ва = аавва. Знак операции конкатенации часто опускают. Цепочки будем обозначать малыми греческими буквами , . Очевидно, ε является как левой, так и правой единицей для операции конкатенации: аε = εа = а.

Определение 3
Пусть А = <S, X, Y, s0,, > - конечный автомат. Расширенными функциями перехода и выхода автомата А называются функции

Расширенные функции переходов и выходов определены на множестве входных последовательностей (входных цепочках) в отличие от обычных функций переходов и выходов, которые определены на множестве входных сигналов.

Пусть в некоторое состояние автомата не существует пути из начального состояния. Иными словами, в эти состояния автомат не может попасть. Такие состояния автомата называются недостижимыми, остальные - достижимыми. Очевидно, что недостижимые состояния и переходы из них можно отбросить: они не влияют на поведение конечного автомата. Дадим формальное определение.

Определение 4

Пусть А = <S, X, Y, s0,, > конечный автомат. Состояние s S называется достижимым тогда и только тогда, когда ( X*) * (s0, ) = s (то есть под воздействием какой-либо цепочки входных сигналов автомат попадает в это состояние). Состояние конечного автомата является недостижимым тогда и только тогда, когда под воздействием любой входной цепочки автомат не переходит в это состояние: Недостижимо (s)( X*)*(s0,a)s.

Рис. 5. Два конечных автомата

Достижимое множество состояний конечного автомата А = < S, X, Y, s₀,, > строится с помощью алгоритма, основанного на индукции. Алгоритм разобьем на последовательные шаги. На i-м шаге будем строить множество Qi состояний, достижимых из начального состояния автомата некоторой входной цепочкой длины не более чем i. Очевидно, что Q₀ = {S₀}. Для любого i очевидно определение . Очевидно также, что не более чем за |S| шагов Q_k+i = Q_k. Это множество состояний Q_k будет включать в себя все достижимые состояния автомата А = <S, X, Y, s₀,, > Вернемся теперь к проблеме эквивалентности конечных автоматов.

Определение 5
Конечные автоматы А = <SA, ХA, YA, S0A, А, .А> и В = <Sв, Хв, Yв, S0в,,> называются эквивалентными, если выполнены два условия: а) их входные алфавиты совпадают: ХА = Хв = X; б) реализуемые ими отображения совпадают: ( X *)А * (SOA, а) = в *(S0B , а).

Два конечных автомата (см. рис. 5) имеют разное число состояний и эти состояния по-разному называются. Но внешнее поведение у них похожее: реакция первого автомата на входную цепочку aabbabb равна _A*(q₀, aabbabb) = _B*(S_O, abbabb) = 0001001.

Однако ответить на вопрос, эквивалентны ли эти автоматы, перебором их реакций ia всех входные цепочки невозможно: входных цепочек бесконечно много. Поэтомy проблема эквивалентности конечных автоматов является нетривиальной.
Оказывается, существует простой метод решения этой проблемы. Этот метод основан на понятии прямого произведения конечных автоматов.

Определение 6
Прямым произведением конечных автоматов А = <SA, X, YA, S0A, A, A.А> и В = <SB, X, YB, S0B, B, B> с одинаковым входным алфавитом X (обозначается А х В) называется автомат А х В = <SAx SB, X, YA x YB, (S0A, S0B),A x B, А x В> , где: a)  (sASA) (sBSB) (xX) AxB((SA,sB),x) = (A(sA,x),B(sB,x)); б)  (sASA) (sBSB) (xX) AxB((sA,sB),x) = (A(sA,x),B(sB,x));

Иными словами, конечный автомат, являющийся прямым произведением двух конечных автоматов, в качестве своих состояний имеет пары состояний исходных автоматов, его начальное состояние есть пара их начальных состояний, выходной алфавит - множество пар выходных символов автоматов-множителей, функции переходов и выходов определены покомпонентно. Таким образом, прямое произведение конечных автоматов - это просто два стоящих рядом невзаимодействующих конечных автомата, синхронно работающих на одном общем ходе (рис. 6).

Теорема 1. (Теорема Мура)
Два конечных автомата А = <SA, X, YA, S0A, A, A.А> и В = <SB, X, YB, S0B, B, B> с одинаковым входным алфавитом являются эквивалентами тогда и только тогда, когда для любого достижимого состояния (SA, SB) в их прямом произведении А х В справедливо: ( x Х) А (SA, х) = В (SB, x).

Доказательство.(Необходимость.) Пусть А и В эквивалентны, то есть
( X*) _А *(S_0A, ) = _В *(S_0B, ).

Рис. 6. Прямое произведение конечных автоматов А и В

Докажем при этом предположении:
((S_A, S_B) S_A x S_B) Достижимо (S_A, S_B)(x X)_A (S_A,X) = _B(S_B, x).
В соответствии с определением 4, свойство достижимости состояния (S_A, S_B) эквивалентно условию

( X*)*((s_0A, s_0B)) = (s_A,s_B). Таким образом, надо доказать, что если

( X*) _А *(S_0B, ) = _В *(S_0B, ), то

((s_A,s_B) S_A x S_B)[( X*) *((s_0A,s_0B), ) = (s_A,s_B) (x X)_A(s_A, x) = _B(s_B, x)].
Предположим противное, то есть что

((s_A,s_B) S_A x S_B) [( X*) *((s_0A,s_0B), ) = (s_A,s_B) (x X)_A(s_A, x) = _B(s_B, x)].
и покажем, что тогда

( X*) _А *(S_0A, ) = _В *(S_0B, )

Отрицание следствия можно преобразовать в

((s_A,s_B) S_A x S_B)[( X*) *((s_0A,s_0B), ) = (s_A,s_B) & (x X)_A(s_A, x) _B(s_B, x)].
Положим а = х. Очевидно, что:

_A*(S_0A, ) = _A*(S_0A, x) = _A*(S_0A, ) ^_A(*(S_0A, ), X) = _A*(S_0A, ) ^_A( (S_A, X)

_B*(S_0B, ) ^ _B(S_B, x) = _B*(S_0B, ) ^_B(*(S_0B, ), X) = _B*(S_0B, X) = _B* (S_B, )

Отсюда:

( X*) _A*(S_0A, ) или ( X*)_A*(S_0A, ) = _B*(S_0B, ),
что и требовалось доказать.

(Достаточность.) Докажем обратное, то есть в предположении

((S_A, s_B) S_AxS_B)

Достижимо

(S_A, S_B) (x Х) _А (S_A, x) = _B (S_B, x)

докажем, что А и В эквивалентны, то есть

(x Х*) _А* (S_0A, ) = _B (S_0B, )

Это доказывается индукцией по длине входных цепочек. Иными словами, будем доказывать

(k Х) ( Х^k) _A*(S_0A, ) = _B*(S_0B, ) для k = 0, 1, ...

Базой индукции является доказательство этого утверждения при k = 0. Оно доказывается непосредственно подстановкой k = 0, поскольку

_A*(S_0A, ε) = _B*(S_0B, ε) = ε при входной цепочке е длиной 0.

Шаг индукции. Пусть для некоторого i выполняется

( Xⁱ) _A*(s_0A, ) = _B*(s_0B, ).
Докажем, что это выполнится и для i+1. Пусть - произвольная цепочка длиной i. Поскольку состояние _A*(S_0A, ) в автомате А и состояние _B*(S_0B, ) в автомате В являются достижимыми, из предположения

((S_A, S_B) S_A x S_B) Достижимо (S_A, S_B)(x X)_A (S_A,X) = _B(S_B, x).

следует: ( x X) _A(_A* (s_0A, ) x ) = _B(_B *(s_0B, ) x ).

Отсюда: ( x X) ( Xⁱ) _A *(s_0A, x) = _B*(s_0B, x).

Но при произвольном Xⁱ и произвольном x X очевидно, что x - произвольная цепочка из Xⁱ⁺¹.

Теорема доказана.

Пример 2 (продолжение)

Прямое произведение конечных автоматов А и В, изображенных на рис. 5, представлено на рис. 7, а. На рис. 7, б показан этот же автомат с выброшенными недостижимыми состояниями. По графу переходов видно, что из всех достижимых состояний под воздействием входных сигналов автомат А х В выдает пары одинаковых выходных сигналов. Следовательно, автоматы А и В эквивалентны.

Рис. 7. Прямое произведение конечных автоматов примера 2

[Список тем]