Эквивалентность конечных автоматов

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

Дадим несколько определений. Пусть Σ – алфавит (конечное множество символов) и Σ * – множество цепочек из элементов Σ. Цепочки будем обозначать малыми греческими буквами α, β, γ. Введём на множестве цепочек операцию конкатенации, отмечаемую как ⋅ (точка). Через ε будем обозначать пустую цепочку, вовсе не содержащую символов.

Определение 3. Пусть A=S, X, Y, s0, δ, λ – конечный автомат. Расширенными функциями перехода и выхода автомата A называются функции δ *: S× X*⟶ S и λ *: S× X*⟶ Y*, определённые как

δ *s, ε =s; δ *s, aβ =δ *δ (s, a), β;

λ *s, ε =ε; λ *s, aβ =λ (s, a)⋅ λ *δ s, a, β;

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

Рассмотрим пример построения расширенных функций для автомата из параграфа 1. Пусть имеется цепочка α =522. Тогда, следуя определению 3:

δ *s0, 522=δ *δ s0, 5, 22=δ *s3, 22=δ *δ s3, 2, 2=δ *s1, 2=s2.

λ *s0, 522=λ s0, 5⋅ λ *δ s0, 5, 22=y4⋅ λ *s3, 22=…=y4y2y1.

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

Определение 4. Пусть A=S, X, Y, s0, δ, λ – конечный автомат. Состояние s∈ S называется достижимым, если под воздействием какой-либо цепочки входных сигналов автомат попадает в это состояние. Состояние конечного автомата является недостижимым, если под воздействием любой входной цепочки автомат не переходит в это состояние.

s∈ S – достижимо ⇔ ∃ α ∈ X*: δ *s0, α =s.

s∈ S – недостижимо ⇔ ∀ α ∈ X* δ *s0, α ≠ s.

Вернёмся теперь к проблеме эквивалентности конечных автоматов.

Определение 5. Конечные автоматы A=SA, XA, YA, s0A, δ A, λ A
и B=SB, XB, YB, s0B, δ B, λ B называются эквивалентными, если совпадают их входные алфавиты и реализуемые ими отображения:

XA=XB=X;

∀ α ∈ X* λ A*s0A, α =λ B*(s0B, α).

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

Определение 6. Прямое произведение A× B автоматов
A=SA, X, YA, s0A, δ A, λ A и B=SB, X, YB, s0B, δ B, λ B с одинаковым входным алфавитом X – это автомат A× B=SA× SB, X, YA× YB, (s0A, s0B), δ A× B, λ A× B, где:

∀ sA∈ SA, ∀ sB∈ SB, ∀ x∈ X δ A× B(sA, sB), x=δ AsA, x, δ BsB, x;

∀ sA∈ SA, ∀ sB∈ SB, ∀ x∈ X λ A× B(sA, sB), x=λ AsA, x, λ BsB, x.

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

Теорема 1. (Теорема Мура) Два конечных автомата A=SA, X, YA, s0A, δ A, λ A и B=SB, X, YB, s0B, δ B, λ B с одинаковым входным алфавитом являются эквивалентными тогда и только тогда, когда для любого достижимого состояния (sA, sB) в их прямом произведении A× B справедливо

∀ x∈ X λ AsA, x=λ BsB, x.

Рассмотрим использование теоремы Мура на примере. Пусть имеются два конечных автомата A и B, графическое представление которых содержит рис. 2.

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

Действуя по определению 6, построим произведение A и B (рис. 3).

Рис. 3. Прямое произведение автоматов A и B.

Выбросим из полученного произведения недостижимые состояния (рис. 4).

Рис. 4. Произведение автоматов A и B без недостижимых состояний.

По графу переходов видно, что из всех достижимых состояний автомат A× B выдаёт пары одинаковых выходных сигналов. Следовательно, автоматы A и B эквиваленты.