Методы абстрактного синтеза
S = | {| x2| v | x1| x2| v | x1| x1| x2|} | x1| x1| x1| {| x1| }| x2|
0 1 2 3 2 4 5 2 6 7 8 9
0 0 2 0 2 4 0 2 6 7 7
1 1 1 1 8 8
3 3 3 3
5 5 5 5
9 9 9 9
На этом первый этап минимизации (минимизации по регулярному выражению) закончен.
Составим теперь отмеченную таблицу переходов автомата. Определим вначале внутренние состояния, в которые переходит автомат из состояния 0 при подаче на его вход сигнала x1. Для этого найдем все предосновные места, содержащие индекс 0, справа от которых записана буква x1. Таких мест в выражении три. Все основные места, расположенные за этой буквой x1, отмечены индексом 2. Следовательно, автомат из состояния 0 под действием сигнала x1 переходит в состояние 2. Аналогично, сигнал x2 переводит автомат из состояния 0 в состояние 1, т.к. за предосновным, содержащим индекс 0, после буквы x2 расположено основное место с индексом 1. Таким же образом определяются переходы автомата их других внутренних состояний. Сигнал y1 выдается после поступления подряд трех букв x1, т.е. в состоянии 6, а сигнал y2 – после x2, следующей за серией из трех и более букв, т.е. в состоянии 8. В остальных случаях выдается пустая буква е. Отсюда получаем следующую отмеченную таблицу переходов:
|
yg |
e |
e |
e |
e |
e |
e |
y1 |
e |
y2 |
|
xj\ai |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
x1 |
2 |
2 |
4 |
2 |
6 |
2 |
7 |
7 |
2 |
|
x2 |
1 |
1 |
3 |
1 |
5 |
1 |
8 |
8 |
1 |
|
yg |
E |
e |
e |
y1 |
e |
y2 |
|
xj\ai |
A0 |
a1 |
a2 |
a3 |
a4 |
a5 |
|
x1 |
A1 |
a2 |
a3 |
a4 |
a4 |
a1 |
|
x2 |
A0 |
a0 |
a0 |
a5 |
a5 |
a0 |
Из построенной таблицы видно, что из состояний 0, 1,3 и 5 автомат сигналами x1 и x2 переводится в одинаковые состояния (2 и 1). Кроме того, все перечисленные состояния отмечены одинаковыми выходными сигналами. Поэтому состояния 0, 1, 3 и 5 можно объединить в одно состояние, обозначив его как а0. Введем также обозначения: 2 – а1; 4 – а2; 6 – а3; 7 – а4; 8 – а5. Тогда получим упрощенную таблицу переходов автомата. В этой таблице из состояний а3 и а4 под действием входных сигналов х1 и х2 автомат переходит в одинаковые состояния а4 и а5. Но объединять эти состояния нельзя, т.к. отмечены разными выходными сигналами. По этой же причине нельзя объединять состояния а0 и а5. Объединение состояний и составляет второй этап минимизации, причем объединяются только такие состояния, которые отмечены одинаковыми выходными сигналами, и из которых под действием одинаковых входных сигналов происходит переход в одинаковые состояния. Очевидно, у таких состояний должны совпадать столбцы таблицы переходов.
предыдущаяследующая