Второй этап минимизации

Лекция 14. Минимизация внутренних состояний автомата

На первом этапе минимизации внутренних состояний можно пользоваться следующим правилом:

• Если несколько предосновных мест отмечено одинаковой совокупностью индексов и справа от этих мест записаны одинаковые буквы, то основные места, расположенные справа от этих букв можно отметить одинаковыми индексами.

В полученном нами выражении основные места 2, 4 и 7 можно отметить общим индексом, так как слева от каждого из этих мест записана буква x ₁, а предосновные места, предшествующие этой букве, имеют одинаковую совокупность индексов (0, 1, 3, 6, 11). Теперь с учетом этого проведем новую разметку:

Проделанную процедуру можно повторить вновь, так как в полученном выражении есть два места (4 и 6), перед которыми стоит одинаковая буква x₁, имеющая предосновное место, отмеченное одинаковым индексом 2. После этого получим окончательную разметку:

Составление отмеченной таблицы переходов. Составим теперь отмеченную таблицу переходов автомата. Определим вначале внутренние состояния, в которые переходит автомат из состояния 0 при подаче на его вход сигнала x ₁. Для этого найдем все предосновные места, содержащие индекс 0, справа от которых записана буква x ₁. Таких мест в выражении три. Все основные места, расположенные за этой буквой x ₁, отмечены индексом 2. Следовательно, автомат из состояния 0 под действием сигнала x ₁ переходит в состояние 2. Аналогично сигнал x ₂ переводит автомат из состояния 0 в состояние 1, так как за предосновным местом, содержащим индекс 0, после буквы x ₂ расположено основное место с индексом 1. Таким же образом определяются переходы автомата их других внутренних состояний. Сигнал y ₁ выдается после поступления подряд трех букв x ₁, то есть в состоянии 6, а сигнал y ₂ – после x ₂, следующей за серией из трех и более букв, то есть в состоянии 8. В остальных случаях выдается пустая буква е. Отсюда получаем следующую отмеченную таблицу переходов.

yg	e	e	e	e	e	e	y1	e	y2
xj\ai
x1
x2

Из построенной таблицы видно, что из состояний 0, 1, 3 и 5 автомат сигналами x ₁ и x ₂ переводится в одинаковые состояния (2 и 1). Кроме того, все перечисленные состояния отмечены одинаковыми выходными сигналами. Поэтому состояния 0, 1, 3 и 5 можно объединить в одно состояние, обозначив его как a ₀. Введем также обозначения: 2 – a ₁; 4 – a ₂; 6 – a ₃; 7 – a ₄; 8 – a ₅. Тогда получим упрощенную таблицу переходов автомата. В этой таблице из состояний a ₃ и a ₄ под действием входных сигналов х ₁ и х ₂ автомат переходит в одинаковые состояния a ₄ и a ₅. Но объединять эти состояния нельзя, так как они отмечены разными выходными сигналами. По этой же причине нельзя объединять состояния a ₀ и а ₅. Объединение состояний и составляет второй этап минимизации, причем объединяются только такие состояния, которые отмечены одинаковыми выходными сигналами, и из которых под действием одинаковых входных сигналов происходит переход в одинаковые состояния. Очевидно, у таких состояний должны совпадать столбцы таблицы переходов.

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

Дата добавления: 2014-10-31