Минимизация автоматов-распознавателей

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

Под минимизацией автомата-распознавателя подразумевается построение минимального автомата кого, что:

1) он обладает минимальным числом состояний;

2) является эквивалентным исходному автомату, т.е. распознает один и тот же язык.

Описание алгоритма минимизации конечного автомата:

1.Находим и удаляем в начальном КА все недостижимые и непродуктивные состояния.

Пример: В следующем КА состояние q₃ – недостижимое.

Пример: В следующем КА состояние q₃ – непродуктивное.

2.Затем необходимо найти такое разбиение множества всех оставшиехся состояний автомата, чтобы каждое подмножество содержало неразличимые состояния. То есть множества состояний автомата разделяются на классы эквивалентности:

a) В I-й класс относим все конечные/финальные состояния (то есть состояния из множества F);

b) Во II-й класс относим все остальные состояния (то есть Q\F).

Назовем эти состояния 0-эквивалентными.

3. Строим новое одно-эквивалентное разбиение, выделив те состояния, которые по одинаковым символам переходят в 0-эквивалентные состояния.

4. Повторяется шаг 3, последовательно создавая (n+1)-эквивалентные состояния по n-эквивалентным, увеличивая так число классов эквивалентности.

5. Алгоритм заканчивается, когда (n+1)-эквивалентные состояния совпадают с n-эквивалентными.

Каждый полученный класс эквивалентности будет новым состоянием в новом минимизированном автомате.

В множество F' автомата внесём те состояния, которые содержат хотя бы одно финальное состояние из начального.

Полученный, минимизированный КА должен быть эквивалентен начальному КА.

Если на некотором шаге при нахождении k-эквивалентных состояний, состояния и попадают в разные классы эквивалентности , то на шаге k+1 данные состояния не могут войти в один класс разбиения.

Пример.Пусть задан конечный автомат-распознаватель , где , , , а функция переходов задана графом переходов и расширенной таблицей переходов:

Рис. 1 Граф переходов

a
b

Первый шаг.

Исходное разбиение содержит два класса:

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

Поэтому:

a
b

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

Разбиение совпадает с разбиением . На основании теоремы искомое разбиение совпадает с . Таким образом, минимальный автомат с эквивалентным поведением имеет 4 состояния, представляющих блоки разбиения .

Введем следующие переобозначения: , , , .

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

a
b

Начальным состоянием здесь является состояние , заключительными - два состояния и .

Рис. 1 Граф переходов минимизированного автомата