Приклад мінімізації автомата Мура

При мінімізації автоматів Мура вводиться поняття 0-еквівалентності станів і розбиття безлічі станів на 0- класи: 0- еквівалентними називаються будь-які однаково відмічені стани автоматів Мура. Якщо два 0-еквівалентні стани будь-яким вхідним сигналом переводиться в два 0-еквівалентні стани, то вони називаються 1-еквівалентними. Усі подальші класи еквівалентності станів для автоматів Мура визначаються аналогічно приведеному вище для автоматів Мілі.

Таблиця 1.32 - Відмічена таблиця переходів немінімального автомата Мура

В результаті застосування алгоритму мінімізації до автомата Мура, що має 12 станів, отримаємо автомат Мура, що має 4 стани. Відпускаючи проміжні таблиці, приведемо лише послідовність розбиття: p0 = {B1, B2, B3}.

Таблиця 1.33 - Відмічена таблиця переходів мінімального автомата Мура

B1={a1, a2, a8}; B2={a6, a9, a10, a11, a12}; B3={a3, a4, a5, a7} p1 ={C1, C2, C3, C4}. C1={ a1, a2, a8}; C2={ a6, a9, a11}; C3={ a10, a12}; C4={ a3, a4, a5, a7} p2 ={D1, D2, D3, D4}; p2 = p1; D1 = C1; D2 = C2; D3 = C3; D4 = C4.

Контрольні питання і завдання

1. Які існують способи завдання цифрових автоматів?

2. Дайте визначення графа автомата.

3. Напишіть функції переходів і виходів, що визначають закон функціонування автоматів Мілі і Мура.

4. Напишіть вирази, що визначають закон функціонування автомата Мура.

5. У чому полягає різниця між автоматами Мілі та Мура?

6. Чим відрізняється С-автомат від автоматів Мілі і Мура?

7. Які особливості має модель цифрового автомата Мілі?

8. Як перейти від автомата Мура до еквівалентного йому автомата Мілі?

9. Що означає еквівалентність двох автоматів?

10. Які головні етапи алгоритму переходу від автомата Мілі до автомата Мура?

11. У який спосіб задається автомат Мура? У чому різниця між автоматами І і II роду?

12. Що являє собою граф переходів цифрового автомата Мілі, Мура,
С-автомата?

13. У чому полягає суть таблиці переходів і виходів автомата Мілі? Наве­діть приклади?

14. У чому полягає ідея мінімізації числа станів абстрактного ЦА? Які методи мінімізації вам відомі?

13. Які особливості табличного завдання автомата Мура ви знаєте?

14. Складіть граф - схему автомата Мілі, еквівалентну сумісній таблиці переходів і виходів:

S(t)	X(t)
X1	X2
1	1, y1	4, y2
2	3, y3	2, y2
3	1, y4	4, y3
4	2, y2	3, y4

15. Наведіть граф - схему автомата Мура відповідно таблиці:

Y(t)	S(t)	X(t)
X1	X2
y1	1	2	4
y2	2	1	3
y2	3	4	2
y3	4	3	1

16. Що являє собою „матриця з'єднань" ЦА?

17. Задайте матрицю з'єднань для автомата Мілі, заданого таблицею

(див. таблицю приклада 14).

18. Задайте матрицю з'єднань автомата Мура (див. таблицю прикл.15).

19. Створіть сумісну таблицю переходів і виходів для автомата Мілі, зада­ного матрицею з'єднань.

20. Створіть позначену таблицю переходів для автомата Мура, заданого матрицею з'єднань.

; .

21. Які автомати називають „ еквівалентними"?

22. Наведіть алгоритм трансформації автомата Мура в еквівалентний ав­томат Мілі.

23. Створіть еквівалентну сумісну таблицю переходів і виходів автомата Мілі для автомата Мура, заданого позначеною таблицею переходів:

Y(t)	S(t)	X(t)
X1	X2
y1	1	4	3
y2	2	2	1
y2	3	3	4
y3	4	2	1

24. Сформулюйте алгоритм трансформації автомата Мілі в еквівалентний автомат Мура.

25. Для автомата Мілі, заданого сумісною таблицею, створіть позначену таблицю переходів еквівалентного автомата Мура:

S(t)	X(t)
X1	X2
1	2, y2	1, y1
2	4, y1	3, y3
3	2, y3	4, y3
4	1, y2	3, y3

26. Мінімізуйте кількість внутрішніх станів абстрактного автомата Мілі, заданого сумісною таблицею переходів і виходів:

Q(t)	X(t)
X1	X2
	5, y1	10, y2
	8, y1	12, y2
	6, y2	5, y1
	11, y2	7, y1
	9, y1	3, y2
	11, y2	7, y1
	6, y1	3, y2
	4, y1	10, y2
	6, y2	7, y1
	8, y2	1, y1
	9, y2	5, y1
	8, y2	2, y1

27. Поясніть суть поняття „еквівалентність" внутрішніх станів абстракт­ного автомата.

28. Сформулюйте поняття p - розподілувнутрішніх станів ЦА.

29. Сформулюйте поняття „0 - еквівалентність" для автоматів Мура.

30. Мінімізуйте кількість внутрішніх станів абстрактного автомата Мура, заданого позначеною таблицею переходів:

Y(t)	Q(t)	X(t)
X1	X2
y1
y1
y3
y3
y3
y2
y3
y1
y2
y2