Трансформация автомата Мили в автомат Мура

1 задание

Трансформация автомата Мили в автомат Мура

Исходный автомат Мили представлен матрицами переходов и выходов.
1) Изобразить граф автомата Мили.
2) Построить граф эквивалентного автомата Мура.
3) Найти реакции автоматов Мура и Мили, если на вход автоматов подается последовательность

x1 ={z1,z2,z2,z1,z1,z1,z2,z1,z2,z1};

x2 = {z2,z2,z1,z1,z2,z2,z2,z1,z1,z1}.

Исходная таблица переходов A

	a1	a2	a3	a4	a5	a6
z1	а6	а4	a3	а6	a4	a5
z2	a2	a1	a2	a4	a2	a3

Исходная таблица выходов W

	a1	a2	a3	a4	a5	a6
z1	w1	w1	w2	w1	w2	w2
z2	w3	w2	w1	w3	w1	w1

1) Изобразить граф автомата Мили.

	a1	a2	a3	a4	a5	a6
a1	-	z2/w3	-	-	-	z1/w1
a2	z2/w2	-	-	z1/w1	-	-
a3	-	z2/w1	z1/w2	-	-	-
a4	-	-	-	z2/w3	-	z1/w1
a5	-	z2/w1	-	z1/w2	-	-
a6	-	-	z2/w1	-	z1/w2	-

w2 z2

z2 w3

z1

w1 w1

w1 z1

z2 z2

z2 w1

w1

z1

w1

w2 z2 w1

z1 z2

z1 w2

w1

Рис. 1 Граф автомата Мили

2. Построить граф эквивалентного автомата Мура.

А₁={(a₁;w₂)}={b₁}

A₂={(a₂;w₃)(a₂;w₁)}={b₂;b₃}

A₃={(a₃;w₃)}={b₄}

A₄={(a₄;w₁)(a₄;w₂)(a₄;w₃)}={b₅;b₆;b₇}

A₅={(a₅;w₂)}={b₈}

A₆={(a₆;w₁)}={b₉}

A1

z1

z2 z2

A2

A6

z2

z1

z2

z2

A5 z1

z1 z1 z1

A3

z2

z2

A4

Рис.2 Граф автомата Мура

3) Найти реакции автоматов Мура и Мили, если на вход автоматов подается последовательность

x1 ={z1,z2,z2,z1,z1,z1,z2,z1,z2,z1};

x2 = {z2,z2,z1,z1,z2,z2,z2,z1,z1,z1}.

Последовательность на входе:

x1 ={z1,z2,z2,z1,z1,z1,z2,z1,z2,z1}

Реакция автомата Мили:

w1, w1, w1, w1, w1, w2, w1, w1, w1, w1, w2

Реакция автомата Мура:

w1, w1, w1, w1, w2, w1, w1, w1, w1, w2

Последовательность на входе:

x2 = {z2,z2,z1,z1,z2,z2,z2,z1,z1,z1}.

Реакция автомата Мили:

w3, w2, w1, w2, w1, w2, w3, w1, w1, w2

Реакция автомата Мура:

w3, w2, w1, w2, w1, w2, w3, w1, w1, w2

2 задание

Построение автомата Мура по ГСА

1) По заданной ЛСА построить ГСА.

2) Построить граф автомата Мура по ГСА.

Y₀↓¹Y₁Y₂X₁↑¹↓² Y₃↓⁶Y₆X₂↑³Y₅↓⁷Y₄X₄↑²ω↑⁵↓³X₃↑⁶ ω ↑⁷↓⁵Y_к

0

1

0

0

1

1

0

1

Рис.3 Графическая схема алгоритма

x₄

x3 x4

x₂ x₁

Рис. 4 Граф автомата Мура

1. из а₁ в а₂ (безусловный переход);

2. из а₂ в а₃ через х₁(путь 2-го типа);

3. из а₃ в а₄ (безусловный переход);

4. из а₄ в а₅ через х₂;

5. из а₄ в а₆ через х₂ и х₃;

6. из а₅ в а₆ (безусловный переход);

7. из а₆ в а₁ через х₄;

8. из а₆ в а₃ через х₄;

9. из а4 в а4 через ;

10. из а₂ в а₂ через

3 задание

Построение автомата Мили по ГСА

1) По матричной схеме алгоритма построить ГСА.

2) По ГСА записать ЛСА.

3) По ГСА построить автомат Мили.

	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8	Y9	Yк
Y0	1	Р1
Y1			2	Р2
Y2
Y3
Y4
Y5					3	Р3
Y6
Y7
Y8				4					Р4
Y9

Y₀→ Y1˅ p1Y2 Y₅→ Y5˅ p3Y6

Y₁→ Y3˅ p2Y4 Y₆→Y₇

Y₂→Y₅ Y₇→Y₈

Y₃→Y₅ Y₈→ Y4˅ p4Y9

Y₄→Y₆ Y₉→Y_k

а₁

а₂

а₄ а₃

а₅

0 а₆

1 а₇

а₈

а₉

а₁

Рис. 5 Графическая схема алгоритма

2) По ГСА записать ЛСА.

Y₀P₁↑¹Y₂↓³ω↓⁴Y₅P₃↑⁴Y₆ω↑⁷↓⁷Y₇ω↑⁸↓⁸Y₈P₄↑⁵Y₉↑⁶↓²Y₃ω↑³↓¹Y₁P₂↑²↓⁵Y₄↓⁶Y_k

3) По ГСА построить автомат Мили.

Y₉

Y₁

P₄

Y₈ P₁

P₂

Y₃

Y₇ 1

Y₂

Y₆ Y₄

Y₅

Y₄

1 P₃

Рис. 6 Автомат Мили

Дата добавления: 2015-09-29