- •Самарский государственный архитектурно-строительный университет
- •Оглавление
- •Введение
- •Задание на курсовое проектирование
- •Построение и преобразование грамматик
- •3. Построение детерминированного конечного автомата
- •4. Минимизация автомата
- •5. Работа с сетями Петри
- •6. Кодирование состояний автомата
- •7. Структурный синтез автомата
- •Библиографический справочник
4. Минимизация автомата
Теорема. Для любого автомата существует минимальный автомат единственный с точностью до изоморфизма.
Рассмотрим алгоритм минимизации автомата по методике Мура:
В таблице переходов автомата отыскиваются строки, у которых имеются рабочие состояния в одинаковых столбцах. Под рабочим состоянием будем понимать состояние, отличное от состояния ошибки. Состояние ошибки на таблице переходов обозначено пустой клеткой. Состояния, соответствующие таким строкам, заносятся в группы.
Рабочие состояния внутри группы проверяются на эквивалентность.
Два состояния qi и qj называются эквивалентными, если для любого
входного символа Xk функции выходов и функции переходов пар
( qi, Xk ) , ( qj, Xk ) будут равны.
Если среди рабочих состояний групп через ряд проверок устанавливается эквивалентность, то такие состояния также считаются эквивалентными.
Удаляем из таблицы строку состояния q9, так как на состояние q9 нет больше переходов. Cтроку состояния q7 заменяем на склеенную строку q7,9, так как на состояние q7 нет больше переходов. Состояния
q1, q2, q3 - эквивалентны, удаляем строки q2 и q3. Заменяем в таблице 5 все q2 и q3 на q1. Состояния q4 и q5 - эквивалентны, удаляем строку q5, соответственно q5 в таблице 4 заменяем на q4. В итоге, получаем таблицу 5:
Таблица 5
|
|
Состояние |
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
q0 |
S (нач. сост.) |
|
|
|
|
q15 |
q1 |
q7 ,9 |
q6 |
|
q1 |
A |
q4 |
|
|
|
q15 |
|
|
|
|
q4 |
D |
q15 |
|
|
|
q0 |
|
|
|
|
q6 |
F |
|
q11 |
|
|
q12 |
|
q14 |
|
|
q7,9 |
S1 |
|
|
|
|
q8 |
|
q10 |
|
|
q8 |
S2 |
|
|
|
|
q1 |
|
|
|
|
q 10 |
S4 |
|
|
q1 |
|
|
|
|
|
|
q 11 |
S5 |
|
|
q12 |
|
|
|
|
|
|
q 12 |
S6 |
|
|
|
|
|
q13 |
|
|
|
q 13 |
S7 |
|
q15 |
|
|
|
|
|
|
|
q 14 |
S8 |
|
|
|
|
|
|
|
q13 |
|
q 15 |
закл. сост. |
|
|
|
q0 |
|
|
|
|
Продолжим рассматривать решение в соответствии с обозначенным алгоритмом. Анализ делаем по табл. 4. Группы состояний, проверяемые на эквивалентность, следующие:
( q1;q2;q3), (q4; q5,).
Проведем анализ этих состояний по переходам. Устанавливаем, что состояния q1, q2 и q3, а также состояния q4 и q5 являются эквивалентными по определению. Обозначив эквивалентные состояния одним состоянием, введем новые нетерминальные символы r вместо q. Будем иметь:
r0 = q0; r1 = q1; r2 = q4; r3 = q6; r4 = q7,9;
r5 = q8; r6 = q10; r7 = q11; r8 = q12; r9 = q13, r10= q14,
r11=q15;
Введем полученные замены и подстановки в табл.5 переходов автомата. Будем иметь новую таблицу 6 эквивалентную с точностью до изоморфизма таблице переходов 5.
Таблица 6
|
Соответствие нетерминалов |
Терминалы | ||||||||||
|
Х0 |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Х7 | ||||
|
r0 -нач.сост. |
q0 |
|
|
|
|
r11 |
r1 |
r4 |
r3 | ||
|
r1 |
q1 |
r2 |
|
|
|
r11 |
|
|
| ||
|
r2 |
q4 |
r11 |
|
|
|
r0 |
|
|
| ||
|
r3 |
q6 |
|
r7 |
|
|
r8 |
|
r10 |
| ||
|
r4 |
q7,9 |
|
|
|
|
r5 |
|
r6 |
| ||
|
r5 |
q8 |
|
|
|
|
r1 |
|
|
| ||
|
r6 |
q10 |
|
|
r1 |
|
|
|
|
| ||
|
r7 |
q11 |
|
|
r8 |
|
|
|
|
| ||
|
r8 |
q12 |
|
|
|
|
|
r9 |
|
| ||
|
r9 |
q13 |
|
r11 |
|
|
|
|
|
| ||
|
r10 |
q14 |
|
|
|
|
|
|
|
r9 | ||
|
r11- закл. сост |
q15 |
|
|
|
ro |
|
|
|
| ||