Алгоритм перехода от автомата Мили к автомату Мура (до 40 минут)

Алгоритм перехода от автомата Мили <A={a₁,a₂,a₃},Q₁,B={b₁,b₂,b₃,b₄},δ₁,λ₁> к автомату Мура <A,Q₂,B,δ₂,λ₂> следующий:

- ставят в соответствие каждому картежу <q_i,a_j> автомата Мили состояние q_ij автомата Мура;

- начальное состояние q₀ÎQ₁ автомата Мили включается во множество состояний Q₂ автомата Мура.

Эти соответствия в нашем случае представим в таблице:

A\Q	q0→q00	q1	q2	q3
a1	q1→q01	q2→q11	q0→q21	q3→q31
a2	q3→q02	q2→q12	q0→q22	q0→q32
a3	q2→q03	q1→q13	q2→q23	q3→q33

Очевидно, т.к. наш инициальный автомат Мили <U₁, q₀> имеет m=3 и n=4 (входных букв и внутренних состояний), то эквивалентный ему автомат Мура имеет (n*m+1)=(4*3+1)=13 состояний, т.е. если │Q₁ │=4, то │ Q₂│=13. Перепишем таблично представленное соответствие состояний, эквивалентных автоматов Мили и Мура в виде фактор-множества:

q₀ q₁ q₂ q₃

↓ ↓ ↓ ↓

{q₀₀, q₂₁, q₂₂, q₃₂} {q₀₁, q₁₃} {q₀₃, q₁₂, q₁₁, q₂₃} {q₀₂, q₃₁, q₃₃}

Это означает, что переход автомата Мили из состояния q₀ в состояние q₁ должен соответствовать всем переходам автомата Мура из состояний {q₀₀, q₂₁, q₂₂, q₃₂} в состояния {q₀₁, q₁₃}; переход из q₁ в q₃ должен соответствовать переходам из {q₀₁, q₁₃} в {q₀₂, q₃₁, q₃₃}. Отсюда следует, что если состояние q_ij входит во множество состояний, совпадающих с состоянием q_к, то столбец таблицы переходов для состояний q_ij будет совпадать со столбцом таблицы переходов для состояний q_к.

Значение функции выходов для автомата Мура определяется соотношением:

λ(q_ij) = λ(q_i, a_j) при q_ij ≠q₀₀.

Для начального состояния q₀₀ значение выходной буквы выбирается произвольно.

Переходы, выходы эквивалентного автомату Мили автомата Мура в нашем примере представимы автоматной таблицей следующего вида:

A\B/Q	b3/q00	b3/q01	b4/q02	b1/q03	b2/q11	b3/q12	b2/q13	b1/q21	b4/q22
a1	q01	q11	q31	q21	q21	q21	q11	q01	q01
a2	q02	q12	q32	q22	q22	q22	q12	q02	q02
a3	q03	q13	q33	q23	q33	q22	q13	q03	q03

b4/q23	b1/q31	b2/q32	b3/q33
q21	q31	q01	q31
q22	q32	q02	q32
q23	q33	q03	q33

Обратная задача – задача перехода от автомата Мура к эквивалентному автомату Мили – решается просто. Если δ₂ и λ₂ – функции перехода и выхода автомата Мура, то функции перехода и выхода эквивалентного автомата Мили определяется выражениями: δ₁ (q, a) = δ₂ (q, a)

λ₁ (q, a) = λ₂ (δ₂ (q, a)).

Эти соотношения означают, что таблица переходов автомата Мили, эквивалентного автомату Мура, совпадает с таблицей переходов автомата Мура, а таблица выходов составляется так, что в каждую ее клетку записывается символ, которым отмечено состояние в данной клетке.

Примечание.

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

2) Задача минимизации автомата – задача поиска среди эквивалентных автоматов минимального автомата, т.е. такого автомата, который имеет минимальное число состояний.

3) В комбинационном автомате <A,Q,B,λ> все состояния эквивалентны, а минимальный комбинационный автомат (автомат без памяти) <A,B,λ> имеет одно состояние (т.е. │Q │=1).

4) С алгебраической точки зрения конечный автомат является трехосновной универсальной алгеброй с двумя операциями на нем δ и λ.

5) Переходную систему <A,Q, δ > обычно рассматривают как алгебру <Q; a₁,a₂,…,a_m> с унарными операциями (обозначаемыми буквами входного алфавита a_iÎ A), такими, что a_iq_j =δ(q_j,a_i).

Лекция №11.

КОМПОЗИЦИЯ АВТОМАТОВ.

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

- прямая сумма;

- прямое произведение;

- суперпозиция.

Текст лекции

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