Развяжем все пары переходов по элементам памяти τi, вводя дополнительный элемент памяти только тогда, когда по уже введенным элементам памяти пару переходов развязать невозможно. В результате получаем таблицу кодирования автомата А (табл. 16).
Таблица 16. Таблица кодирования автомата А
|
τ1 |
τ2 |
τ3 |
τ4 |
|
|
q0 |
0 |
0 |
0 |
0 |
|
q1 |
1 |
1 |
0 |
1 |
|
q2 |
1 |
1 |
1 |
1 |
|
q3 |
1 |
0 |
1 |
1 |
|
q4 |
0 |
0 |
1 |
1 |
|
q5 |
1 |
1 |
1 |
0 |
Граф автомата А содержит всего 6 вершин, следовательно минимальное количество элементов памяти для его кодирования равно 3. Полученное кодирование требует использование четырех элементов памяти, следовательно, можно провести минимизацию состояний памяти автомата А. Минимизация проводится последовательным вычеркиванием элементов памяти и проверкой, развязаны ли все пары переходов (из табл.15). Данная процедура выполняется до получения неопределенного элемента памяти или до зацикливания.
Таблица 17. Минимизация состояний памяти автомата А
|
τ2 |
τ3 |
τ4 |
τ5 |
|
|
q0 |
0 |
0 |
0 |
0 |
|
q1 |
1 |
0 |
1 |
- |
|
q2 |
1 |
1 |
1 |
1 |
|
q3 |
0 |
1 |
1 |
1 |
|
q4 |
0 |
1 |
1 |
0 |
|
q5 |
1 |
1 |
0 |
1 |
Таблица 18. Минимизация состояний памяти автомата А
|
τ3 |
τ4 |
τ5 |
τ6 |
|
|
q0 |
0 |
0 |
0 |
0 |
|
q1 |
0 |
1 |
- |
1 |
|
q2 |
1 |
1 |
1 |
1 |
|
q3 |
1 |
1 |
1 |
0 |
|
q4 |
1 |
1 |
0 |
0 |
|
q5 |
1 |
0 |
1 |
1 |
Таблица 19. Минимизация состояний памяти автомата А
|
τ4 |
τ5 |
τ6 |
τ7 |
|
|
q0 |
0 |
0 |
0 |
0 |
|
q1 |
1 |
0 |
1 |
0 |
|
q2 |
1 |
1 |
1 |
- |
|
q3 |
1 |
1 |
0 |
- |
|
q4 |
1 |
0 |
0 |
1 |
|
q5 |
0 |
1 |
1 |
- |
Таблица 20. Минимизация состояний памяти автомата А
|
τ5 |
τ6 |
τ7 |
τ8 |
|
|
q0 |
0 |
0 |
0 |
0 |
|
q1 |
0 |
1 |
0 |
1 |
|
q2 |
1 |
1 |
- |
1 |
|
q3 |
1 |
0 |
1 |
- |
|
q4 |
0 |
0 |
1 |
- |
|
q5 |
1 |
1 |
0 |
0 |
Таблица 21. Минимизация состояний памяти автомата А
|
τ6 |
τ7 |
τ8 |
τ9 |
|
|
q0 |
0 |
0 |
0 |
0 |
|
q1 |
1 |
0 |
1 |
0 |
|
q2 |
1 |
1 |
1 |
- |
|
q3 |
0 |
1 |
1 |
1 |
|
q4 |
0 |
1 |
0 |
0 |
|
q5 |
1 |
0 |
0 |
1 |
Таблица 22. Минимизация состояний памяти автомата А
|
τ7 |
τ8 |
τ9 |
τ10 |
|
|
q0 |
0 |
0 |
0 |
0 |
|
q1 |
0 |
1 |
0 |
1 |
|
q2 |
1 |
1 |
- |
1 |
|
q3 |
1 |
1 |
1 |
0 |
|
q4 |
1 |
0 |
0 |
0 |
|
q5 |
0 |
0 |
1 |
1 |
Таблица 23. Минимизация состояний памяти автомата А
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.