Page 12 - 4625

Означення. Скінченний автомат М називається детер-
мінованим, якщо δ (q , a ) містить не більше одного стану для
k
i
будь-якого q ∈ Q та a ∈ Σ.
k
i
Твердження: для довільного недетермінованого скінчен-
ного автомата М можна побудувати еквівалентний йому
детермінований скінченний автомат M , такий що L(M) =
1
L(M ).
1
Доведення: Нехай М – не детермінований скінченний
автомат, такий що M = < Q, Σ, δ, q , F >.
0
Детермінований автомат M = < Q , Σ, δ , q , F > побу-
1
1
01
1
1
дуємо таким чином:
1. Q = P(Q), тобто імена станів автомата M - це
1
1
підмножини Q.
2. q 01 = {q }, {q } ∈ P(Q).
0
0
3. F складається з усіх таких підмножин S ∈ P(Q), S 
1
A ≠ Ø.
4. δ (S, a) = {q | q ∈ δ(q , a), q ∈ S}.
i
1
i
Доведемо індукцією по і, що (S, w) ⊨ (S , ε), тоді і тільки
i
1
i
тоді, коли S = {q | (q , w)) ⊨ (q, ε), для q ∈ S}.
i
i
1
∗
Зокрема, ({q }, w) ⊨ S , ε), для деякого S ∈ F , тоді і
0
1
1
1
∗
тільки тоді, коли (q , w) ⊨ (q, ε), q ∈ F. Таким чином, L(M) =
0
L(M ).
1
Побудований нами автомат М має дві властивості: він
детермінований та повністю визначений. До того ж кількість
n
станів цього автомата 2 – 1.

2.2 Мінімізація детермінованих скінченних автоматів
У подальшому програмуванні скінченних автоматів
важливо мати справу з так званими «мінімальними автома-
тами». Мінімальним для даного скінченого автомата візьмемо
еквівалентний йому автомат з мінімальною кількістю станів.
Те, що скінчені автомати можна мінімізувати, покажемо на
такому прикладі:

11