Второй пример абстрактного синтеза

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

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

Из построенной таблицы видно, что из состояний 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 ₀ и а ₅. Объединение состояний и составляет второй этап минимизации, причем объединяются только такие состояния, которые отмечены одинаковыми выходными сигналами, и из которых под действием одинаковых входных сигналов происходит переход в одинаковые состояния. Очевидно, у таких состояний должны совпадать столбцы таблицы переходов.

Рассмотрим еще один пример абстрактного синтеза автомата. Найдем таблицу переходов автомата сравнения чисел, условия работы которого заданы регулярными выражениями:

Регулярные выражения

Регулярные выражения событий S ₁ и S ₂ содержат одинаковые сомножители в итерационных скобках, перед которыми расположено место с индексом 0. Поэтому в обоих выражениях основные места внутри итерационных скобок отмечены одинаковыми индексами (3, 4 и 5). Индекс конечного места каждого выражения распространяется на начальные места всех регулярных выражений, так как в автоматах многократного действия за словом любого события, например S ₁, может быть подано слово любого другого события, то есть S ₁ v S ₂ v S ₃. В размеченных выражениях можно объединить места с индексами 4, 6 и 5, 9:

По размеченному выражению составим отмеченную таблицу переходов.

При составлении таблицы следует учитывать, что для разных регулярных выражений автомат под действием одних и тех же входных сигналов переходит в разные состояния. Эти внутренние состояния будем отмечать множеством индексов основных мест. Например. В событии S ₃ переход из состояния 0 в состояние 1 происходит под действием сигнала x _r а в S ₁ под действием этого же сигнала из состояния 0 автомат переходит в состояние 3. Поэтому, внутреннее состояние, в которое автомат переходит под действием x_r из состояния 0, будем обозначать множеством из двух индексов 1 v 3. Аналогично получается переход из состояний 2, 7 и 9 под действием x _r, а также переход из состояния 4 и 5 в состояния 3 v 6 и 3 v 8 соответственно под действием x _r. При заполнении таблицы получается свободные клетки там, где переходы в автомате не определенны. Такие клетки будем отмечать звездочкой *, которую следует рассматривать как индекс некоторого внутреннего состояния. Таблица переходов составляется не только для состояний, отмеченных индексами основных мест регулярного выражения, но и для состояний, отмеченных множеством индексов. Для заполнения колонок для таких состояний достаточно образовать дизъюнкцию таких индексов, которые расположены в колонках, отмеченных индексами, входящими в множества. Например. Для заполнения колонки 1 v 3 образуем дизъюнкцию индексов расположенных в колонках 1 и 3. Поскольку состояния 1, 3, 6 и 8 отмечены пустой буквой e, то и состояния 1 v 3, 3 v 6, 3 v 8 также отмечаются буквой е.

После построения таблицы проведем второй этап минимизации числа внутренних состояний автомата. Можно объединить состояния, отмеченные индексами: 0 и 1v3, 4 и 3v6, 5 и 3v8. При этом состояния отмеченные звездочкой обозначим через 10, а состояния 1v3 – 0, 3v6 – 4, 3v8 – 5.

По построенной таблице проведем третий этап минимизации, исключив такие состояния, в которые автомат из нулевого состояния никогда перейти не может. В нашем случае такими состояниями являются 1, 3, 6, 8 и 10.

Обозначив оставшиеся состояния 0 – b ₀, 2 – b ₁, 4 – b ₂, 5 – b ₃, 7 – b ₄, 9 – b ₅, получим окончательную таблицу переходов заданного автомата.