Минимизация конечных автоматов

По данному конечному автомату А можно найти наименьший эквивалентный ему автомат (автомат с минимальным числом состояний). Для этого исключаются недостижимые состояния и склеиваются лишние состояния. Лишние состояния определяются с помощью разбиения множества всех достижимых состояний на классы эквивалентности так, что любой класс содержит неразличимые состояния. После этого их любого класса берется по одному представителю. Таким образом, можно сократить автомат, если он содержит недостижимые состояния или 2 или более неразличимых состояний.

Пусть А - конечный автомат, z₁, z₂ - два его состояния. Цепь a различает z₁ и z₂, если из состояния z₁ можно перейти в z₃ под действием конечного числа тактов:

(z₁, a) |––––* (z₃, e)

и из состояния z₂ можно перейти в z₄ под действием конечного числа тактов:

(z₂, a) |––––* (z₄, e)

причем или z₃, или z₄ принадлежит множеству заключительных состояний:

z₃/z₄ Î F.

Состояния z₁ и z₂ будем называть k-неразличимыми, если не существует такой цепочки a, различающей z₁ и z₂, длина которой меньше или равна k:

z₁ º^k z₂

Состояния z₁ и z₂ будем называть неразличимыми, если они k-неразличимы для всех k>= 0.

z₁ º z₂

Автомат А называется приведенным, если в его множестве состояний нет недостижимых состояний и нет 2-х неразличимых состояний.

Пример:

Недостижимые состояния - F и G (из А никогда не попадешь в F и G).

Теорема: Пусть А - конечный автомат с n-состояниями. Состояния z₁ и z₂ неразличимы тогда и только тогда, когда они (n-2)-неразличимы:

z₁ º^n-2 z₂

Вопросы и упражнения

Пусть A= (Z, X, t, z₀, F),

Z - множество состояний = {z₀, z₁, z₂, z_F}

X= {0, 1}

F= {z_F}

t:

Постройте граф данного автомата.

Является ли данный автомат детерминированным?

Можно ли минимизировать данный автомат?