Минимизация числа состояний конечного автомата

Пусть некоторый конечный автомат имеет “лишние” внутренние состояния. Минимизация количества его состояний означает определение эквивалентного ему конечного автомата с минимальным количеством состояний.

Пусть в числе возможных состояний конечного автомата есть несколько состояний, обладающих таким свойством: произвольному входному слову соответствует некоторое выходное слово, не зависящее от того, в каком из указанных состояний находился конечный автомат в исходный момент. В этом случае можно считать, что все указанные состояния по существу одинаковы и лишь в разных случаях обозначены по-разному. Такие состояния можно объединить, обозначив одним символом.

Минимизация производится в несколько этапов. Первый этап минимизации количества состояний заключается в том, что просматриваются таблицы выходов и переходов и в верхней строке обеих таблиц (строка исходных состояний) выявляются такие состояния, которым соответствуют одинаковые столбцы как в таблице выходов, так и в таблице переходов. Эти состояния объединяются, т.е. в обеих таблицах вычеркиваются все одинаковые столбцы как в таблице выходов, так и в таблице переходов, кроме одного, соответствующего какому-либо из выявленных состояний, а в оставшейся части таблицы состояний всем объединяемым состояниям присваивается один и тот же символ. В результате такого преобразования могут снова появиться состояния, которым в обеих таблицах соответствуют одинаковые столбцы.

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

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

Состояния, входящие в разные группы, наверняка нельзя объединить. Возможность объединения состояний, входящих в одну и ту же группу, нужно исследовать дополнительно. Для этого под каждым состоянием выписывается соответствующий ему столбец из таблицы состояний, однако каждое состояние в этом столбце обозначается не собственным символом, а символом группы, в которую оно входит.

В результате такого переобозначения некоторые не совпадающие друг с другом столбцы таблицы состояний могут преобразоваться в совпадающие друг с другом столбцы групповых символов. Состояния, которым соответствуют такие совпадающие друг с другом столбцы, можно объединить. Далее проводим новую разбивку всех состояний на группы. Каждую старую группу нужно попытаться разбить на новые более мелкие группы. Все новые группы заново обозначаются какими-либо символами. С каждым состоянием, входящим в новые группы, выполняются такие же операции, какие выполнялись ранее с состояниями, входившими в старые группы: выписываются из таблицы переходов столбцы, соответствующие этим состояниям, и каждое состояние в этих столбцах обозначается новым групповым символом.

Пример. Пусть автомат Мили задан таблицами переходов и выходов, приведенными на рис. 36. Проведем минимизацию числа состояний этого автомата.

1 этап. Находим состояния, для которых совпадают столбцы в таблице выходов и в таблице переходов. Такими являются состояния а ₃ и а ₆. Заменяем а ₃= а ₆ (состоя-

Рис. 36. Таблицы переходов и выходов автомата Мили до минимизации

ние а 6 исключаем), рис. 37. 2 этап. Группируем состояния в группы таким образом, чтобы в каждой группе были состояния, у которых совпадают столбцы в таблице выходов. а 1, а 4, а 5 - гр.1 (z1); а 0, а 3 - гр. 2 (z2). Могут объединятся лишь такие состояния, которые принадлежат одной и той же группе. Для выяснения возможности объединения таких

состояний выписываем состояния одной группы, а под ним в столбик состояния из таблицы переходов, заменив обозначение состояния обозначением группы, в которую оно входит. Состояния с одинаковыми столбцами можно объеди-

Рис. 37. Таблицы переходов и выходов после первого этапа минимизации

нять.

Таблицы переходов и выходов автомата после второго этапа минимизации приведены на рис. 38.

Рис. 38. Таблицы переходов и выходов после второго этапа минимизации

3 этап. Группируем состояния, у которых одинаковые столбцы в таблице выходов.

(a ₀, a ₃)=z₁; (a ₁, a ₄)=z₂.

Больше ничего не объединяется, полученные таблицы соответствуют автомату с минимальным числом состояний.