Пусть некоторый конечный автомат имеет “лишние” внутренние состояния. Минимизация количества его состояний означает определение эквивалентного ему конечного автомата с минимальным количеством состояний.
Пусть в числе возможных состояний конечного автомата есть несколько состояний, обладающих таким свойством: произвольному входному слову соответствует некоторое выходное слово, не зависящее от того, в каком из указанных состояний находился конечный автомат в исходный момент. В этом случае можно считать, что все указанные состояния по существу одинаковы и лишь в разных случаях обозначены по-разному. Такие состояния можно объединить, обозначив одним символом.
Минимизация производится в несколько этапов. Первый этап минимизации количества состояний заключается в том, что просматриваются таблицы выходов и переходов и в верхней строке обеих таблиц (строка исходных состояний) выявляются такие состояния, которым соответствуют одинаковые столбцы как в таблице выходов, так и в таблице переходов. Эти состояния объединяются, т.е. в обеих таблицах вычеркиваются все одинаковые столбцы как в таблице выходов, так и в таблице переходов, кроме одного, соответствующего какому-либо из выявленных состояний, а в оставшейся части таблицы состояний всем объединяемым состояниям присваивается один и тот же символ. В результате такого преобразования могут снова появиться состояния, которым в обеих таблицах соответствуют одинаковые столбцы.
Если столбцы в таблицах переходов и выходов, соответствующие различным исходным состояниям, содержат прочерки и только поэтому не совпадают, то соответствующие таким столбцам исходные состояния тоже можно объединить.
На втором этапе объединения все состояния объединяются в группы таким образом, чтобы состояниям, входящим в каждую группу, соответствовали одинаковые столбцы в таблице выходов. Каждой такой группе присваивается некоторое обозначение. Запись производится следующим образом:
Состояния, входящие в разные группы, наверняка нельзя объединить. Возможность объединения состояний, входящих в одну и ту же группу, нужно исследовать дополнительно. Для этого под каждым состоянием выписывается соответствующий ему столбец из таблицы состояний, однако каждое состояние в этом столбце обозначается не собственным символом, а символом группы, в которую оно входит.
В результате такого переобозначения некоторые не совпадающие друг с другом столбцы таблицы состояний могут преобразоваться в совпадающие друг с другом столбцы групповых символов. Состояния, которым соответствуют такие совпадающие друг с другом столбцы, можно объединить. Далее проводим новую разбивку всех состояний на группы. Каждую старую группу нужно попытаться разбить на новые более мелкие группы. Все новые группы заново обозначаются какими-либо символами. С каждым состоянием, входящим в новые группы, выполняются такие же операции, какие выполнялись ранее с состояниями, входившими в старые группы: выписываются из таблицы переходов столбцы, соответствующие этим состояниям, и каждое состояние в этих столбцах обозначается новым групповым символом.
Пример. Пусть автомат Мили задан таблицами переходов и выходов, приведенными на рис. 36. Проведем минимизацию числа состояний этого автомата.
1 этап. Находим состояния, для которых совпадают столбцы в таблице выходов и в таблице переходов. Такими являются состояния а 3 и а 6. Заменяем а 3= а 6 (состоя-
Рис. 36. Таблицы переходов и выходов автомата Мили до минимизации
| ние а 6 исключаем), рис. 37. 2 этап. Группируем состояния в группы таким образом, чтобы в каждой группе были состояния, у которых совпадают столбцы в таблице выходов. а 1, а 4, а 5 - гр.1 (z1); а 0, а 3 - гр. 2 (z2). Могут объединятся лишь такие состояния, которые принадлежат одной и той же группе. Для выяснения возможности объединения таких |
состояний выписываем состояния одной группы, а под ним в столбик состояния из таблицы переходов, заменив обозначение состояния обозначением группы, в которую оно входит. Состояния с одинаковыми столбцами можно объеди-
Рис. 37. Таблицы переходов и выходов после первого этапа минимизации
| нять.
|
Таблицы переходов и выходов автомата после второго этапа минимизации приведены на рис. 38.
Рис. 38. Таблицы переходов и выходов после второго этапа минимизации
3 этап. Группируем состояния, у которых одинаковые столбцы в таблице выходов.
(a 0, a 3)=z1; (a 1, a 4)=z2. 
Больше ничего не объединяется, полученные таблицы соответствуют автомату с минимальным числом состояний.
