Изоморфизм и эквивалентность конечных автоматов. (до 50 минут)

а) Гомоморфизм автоматов.

Пусть заданы два конечных автомата U₁=<A₁,Q₁,B₁,δ₁,λ₁> и U₂=<A₂,Q₂,B₂,δ₂,λ₂>, где АUВ – терминальный, а Q- нетерминальный алфавиты. Тройка отображений h₁: A_1→A₂, h₂: Q_1→Q₂, h₃: B_1→B₂, называется гомоморфизмом автомата U₁ в автомат U₂, если для любых aÎ A₁, qÎ Q₁, bÎ B₁ выполнены условия: δ₂ (h₂(q), h₁(a)) = h₂ (δ ₁(q, a));

λ ₂ (h₂(q), h₁(a)) = h₃ (λ ₁(q, a)).

В этом случае автомат U₂ называют гомоморфным автомату U₁. Если все три отображения h₁, h₂, h₃ сюрьективны, то эта тройка h₁, h₂, h₃ называется гомоморфизмом U₁ на U₂ (или эпиморфизмом). Если три отображения h₁, h₂, h₃ есть функциональная биекция, то говорят об изоморфизме U₁ на U₂ (В этом случае говорят, что автоматы U₁ и U₂ изоморфны). Очевидно, что для изоморфных автоматов мощности соответствующих алфавитов должны быть одинаковыми, т.е. │A₁ │=│ A₂│, │ Q₁ │ =│ Q₂│, │ B₁│ = │B₂│.

Понятие изоморфизма имеет для конечных автоматов тот же смысл, что и для алгебр: автоматы U₁ и U₂ изоморфны, если входы, выходы и внутренние состояния автомата U₁ можно переименовать так, что таблица переходов автомата U₁ превратится в таблицу переходов автомата U₂.

Замечание.

1) Изоморфизм графов переходов (без учета букв, записанных на дугах) является необходимым, но недостаточным условием изоморфизма соответствующих автоматов.

₂₎ При гомоморфизме, помимо переименования, происходит еще и склеивание

(например, нескольких состояний автомата U₁ в одно состояние автомата U₂).

Пример. Пусть автономный автомат U₁ задан графом

а автономный автомат U₂ представлен графом

Гомоморфизм – автомата U₁ в автомат U₂ представим так:

a_1→a₂ (a₁Î A₁, a₂Î A₂, h₁: A_1→A₂, │A₁ │=│ A₂│=1)

q_1→q₄, q_2→q₃, q_3→q₃, q_4→q₂, q_5→q₁, q_6→q₂, q_7→q₁, q_8→q₆, q_9→q₇

b₁→b₁, b₃→b₂, b₂→b_2.

Замечание

1) Если в автомате U₂ убрать состояние q₅, то будем иметь эпиморфизм.

2) При гомоморфизме число входных, внутренних и выходных букв может не сохраняться.

Пример. Изоморфизм графа автомата U₁

и графа автомата U₂

не означает изоморфизм самих автоматов U₁ и U₂ . В этом случае нет функционального отображения выходных букв и поэтому у U₁ (q₁, a a a)=b₁b₁b₁, а у U₂ (q₁, a a a)=b₁b₁b₂.

б) Эквивалентность автоматов.

Def. Состояние q_iÎQ₁ автомата U₁=<A,Q₁,B,δ₁,λ₁> и состояние q_jÎQ₂ автомата U₂=<A,Q₂,B,δ₂,λ₂> называются неотличимыми, если для любого входного слова αÎА*

U₁ (q_i, α)=U₂ (q_j, α). В частности, если U₁ =U₂ , то речь идет о неотличимых состояниях одного итого же автомата U. Это означает, что неотличимость состояний q_i, q_j инициальных автоматов <U, q_i> и <U,q_j> есть реализация ими одного и того же автоматного отображения Т: А*→В*.

Def. Автоматы U₁ и U₂ называются неотличимыми (эквивалентными), если для любого состояния q_iÎQ₁, автомата U₁=<A,Q₁,B,δ₁,λ₁> найдется неотличимое от него состояние q_jÎQ₂ автомата U₂=<A,Q₂,B,δ₂,λ₂> и, наоборот, для любого q_jÎQ₂ из U₂ найдется неотличимое от него q_iÎQ₁ из U₁. Неотличимость автоматов означает, что любое автоматное отображение, реализуемое одним из них, может быть реализовано другим, т.е. их возможности по реализации преобразований входной информации в выходную совпадают. Переход от автомата U_i к эквивалентному автомату U_j называется эквивалентным преобразованием автомата U_i.

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

В качестве примера построим автомат Мура <A,Q₂,B,δ₂,μ>, эквивалентный инициальному автомату Мили <A,Q₁,B,δ₁,λ>, заданного автоматной таблицей вида:

А\Q1	q0	q1	q2	q3
a1	q1,b3	q2,b2	q0,b1	q3,b1
a2	q3,b4	q2,b3	q0,b4	q0,b2
a3	q2,b1	q1,b2	q2,b4	q3,b3

Дата добавления: 2015-12-01