Тема 14. Автомат Мура

План леции

1. Автомат Мура

2. Равносильность автоматов Мили и Мура

Автомат Мура - это «пятерка» вида U = (К1, X, Y, f1, h), где:

K₁ - множество состояний автомата;

X - входной алфавит;

Y - выходной алфавит;

f₁ - функция переходов (отображение K ⋅ X → K);

h - функция выходов (отображение K ⋅ X → Y).

При представлении автомата Мура графом дуги помечаются символами входного алфавита, а каждая вершина графа - состоянием и символом выходного алфавита.

При формальном сравнении определений автоматов Мили и Мура может показаться, что автомат Мура может быть задан как входонезависимый автомат Мили, т.е. такой автомат Мили, выходная функция которого удовлетворяет следующим условиям: " a ÎX, " b Î X, " z Î Z (g(z, a) = g(z, b)). Однако это не соответствует способу функционирования автоматов Мура в соответствии с введенным определением.

В автомате Мура реализована иная временная связь между переходами из одного состояния в другое и выходом, по сравнению с автоматом Мили, у которого выход, соответствующий некоторому входу и определенному состоянию, порождается во время перехода автомата в следующее состояние. У автомата Мура сначала порождается выход, а потом - переход в следующее состояние, причем выход определяется только состоянием автомата.

2. Равносильность автоматов Мили и Мура

Равносильность заключается в том, что множество реакций этих автоматов совпадает:

L(M) = {q_z | q_Z Î K};

L(U) = {h_t | h_t Î K₁};

L(M) = L(U).

Теорема. Для каждого автомата Мура можно построить равносильный автомат Мили.

Доказательство. Граф равносильного автомата Мили M можно получить в том случае, если каждому ребру автомата Мура U сопоставить ребро автомата M.

Пусть w = x₁ x₂ ... x_n - входная цепочка, тогда множества реакций для автоматов M и U будут соответственно представлены следующим образом:

q₀ / y₁, x₁ → q₁ / y₂, x₂ → ... → q_n-1 / y_n, x_n;

q₀, x₁ / y₁ → q₁, x₂ / y₂ → ... → q_n-1, x_n / y_n.

Теорема. Для любого автомата Мили можно построить эквивалентный автомат Мура.

Доказательство. В качестве множества K₁ автомата Мура возьмем K₁ = K ⋅ Y. Для обеспечения равносильности автоматов M = U функции переходов и выходов определим следующим образом:

f₁(p ⋅ y, a) = {qb | f(p, a) = q, b ∈ X};

h(p ⋅ y) = y.

Если реакция автомата M на входную цепочку вида w = x₁ x₂ ... x_n из состояния q0 имеет вид

q₀, x₁ / y₁ → q₁, x₂ / y₂ → ... → q_k-1, x_k / y_k (1),

то существует такое состояние q0⋅x1 недетерминированного автомата U, что, начиная работу из этого состояния, автомат U выполняет следующие действия:

q₀ ⋅ x₁ / y₁ → q₁ ⋅ x₂ / y₂ → ... → q_k-1 ⋅ x_k / y_k, x_k (2).

Аналогично можно доказать и обратную теорему о том, что из существования реакции (2) следует существование реакции (1), что подтверждает равносильность автоматов Мили и Мура.

Рекомендуемая литература

1. Крючкова Е.Н. Теория формальных языков и автоматов. - Барнаул; 1996.

2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988.

Контрольные задания для СРС [2, 8, 9]

1. Формальное определение автомата

2. Языки и автоматы

3. Автоматы с магазинной памятью

4. Автоматы Мили и Мура

Дата добавления: 2015-07-26; просмотров: 196; Нарушение авторских прав

Мы поможем в написании ваших работ!