Алгоритм построения детерминированного автомата из недетерминированного

Пусть A= (Z, X, t, z₀, F) - недетерминированный автомат.

Построим А'= (Z', X', t', z₀', F') следующим образом:

1) X'= X

2) Z'= P(Z), где P(Z) - множество некоторых подмножеств множества Z.

3) z₀'= z₀

4) F'= {"S Z| F S 0}

5) t'(S, a)= S', при этом, для "S Z, S' - это некоторое подмножество состояний P, таких, что S'={P| t(P,a)}, t(Z,a) содержит p для некоторого z S.

Построим детерминированный автомат для примера из предыдущего пункта. Множество всех подмножеств множества Z:

z₀ z₁ z₂ z_F

z₀z₁ z₀z₂ z₀z_F z₁z₂ z₁z_F z₂z_F

z₀z₁z₂ z₀z₁z_F z₀z₂z_F z₁z₂z_F

z₀z₁z₂z_F

Построим функцию перехода для новых состояний автомата:

Множество заключительных состояний F'= {D, E}