✖

Przekształcenie NFA w DFA

Pokażemy, jak przekształcić automat niedeterministyczny (NFA) w automat deterministyczny (DFA) i w ten sposób udowodnimy, że moc obliczeniowa automatów niedeterministycznych i deterministycznych jest taka sama. Tę metodę nazywa się konstrukcją potęgową.

Główna idea

Weźmy automat niedeterministyczny ⟨QN, ΣN, δN, q0, FN⟩ bez epsilon-przejść. Zbudujemy automat deterministyczny ⟨QD, ΣD, δD, p0, FD⟩ tak, że

  • QD ⊆ 2QN
  • ΣD = ΣN
  • p0 = {q0}
  • FD = {Q ∈ QD | Q ∩ FN ≠ ∅}

Funkcję przejścia δD definiujemy następująco:

∀Q∈QD,a∈ΣD:δD(Q,a)=⋃q∈QδN(q,a)

Co to znaczy? Automat niedeterministyczny może być jednocześnie w kilku stanach, więc możemy na przykład trafić na sytuację, w której nasz automat niedeterministyczny jest w stanach {q0, q1}. Po przeczytaniu kolejnego symbolu, na przykład 1, możemy dostać się do zbioru stanów {q0, q2, q3}. W deterministycznej wersji tego samego automatu objawi się to tak, że utworzymy dwa stany, nazwiemy je {q0, q1} i {q0, q2, q3} i wprowadzimy między nimi przejście dla symbolu 1. Formalnie przechodzimy więc z jednego stanu do drugiego, ale dzięki nazwom będziemy wiedzieć, że w automacie niedeterministycznym znaleźlibyśmy się w dwóch, a potem w trzech stanach.

Przykład

Weźmy taki automat niedeterministyczny:

Żeby zbudować automat deterministyczny, musimy przede wszystkim zbudować nową funkcję przejścia. Pomoże nam w tym tabela, do której zapiszemy wszystkie przejścia. Na początku tabela wygląda tak:

stan/symbol01{q0}

Na końcu algorytmu w lewej kolumnie będą wszystkie stany automatu deterministycznego. Wypełniona tabela będzie wtedy wyznaczać funkcję przejścia. Teraz wpiszemy do tabeli, do jakich stanów dostaniemy się, jeśli jesteśmy w stanach {q0}, a na wejściu są symbole 0 i 1.

stan/symbol01{q0}{q1}{q1,q2}

Ze stanu q0 dla symbolu 0 prowadzi przejście tylko do stanu q1, natomiast dla symbolu 1 do stanów q1 i q2. Teraz dodamy do tabeli dwa nowe stany: {q1} i {q1, q2}. Dlaczego? Kiedy tylko wpiszemy do tabeli jakiś zbiór stanów, którego nie mamy jeszcze w lewej kolumnie, dopisujemy ten zbiór stanów właśnie tam.

stan/symbol01{q0}{q1}{q1,q2}{q1}{q1,q2}

i znowu wypełniamy. Przy stanie {q1, q2} nie możemy zapomnieć sprawdzić obu stanów, czyli wziąć sumę zbioru stanów, do których dostaniemy się z q1, i zbioru stanów, do których dostaniemy się z q2.

stan/symbol01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}

Dostaliśmy kilka nowych stanów, które musimy dodać do tabeli:

stan/symbol01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q3}

…i znowu uzupełniamy przejścia:

stan/symbol01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}

Stany {q0, q1, q3}, {q1} i {q1,q2} już mamy, więc dodamy tylko stan {q0,q1,q2,q3}.

stan/symbol01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}{q0,q1,q2,q3}{q0,q1,q3}{q0,q1,q2,q3}

Nie dodaliśmy już żadnego nowego stanu, więc tabela jest wypełniona. Teraz zostaje tylko narysować diagram. Stany automatu deterministycznego są w pierwszej kolumnie, przejścia dla symboli 0 i 1 w kolejnych. Każdy stan, który zawiera jakiś stan akceptujący pierwotnego automatu, będzie stanem akceptującym także w tym automacie. Czyli każdy stan zawierający q3 będzie stanem akceptującym. Automat będzie wyglądał tak:

Możemy pokazać, że automat naprawdę działa poprawnie. Spróbujmy zaakceptować słowo 11001. W automacie deterministycznym pójdziemy drogą

q0→1q1,q2→1q0,q3→0q1→0q0,q1,q3→1q0,q1,q2,q3

i automat zaakceptowałby słowo, bo ostatni stan {q0, q1, q2, q3} jest akceptujący. W automacie niedeterministycznym podczas symulacji dostalibyśmy się do tych samych stanów, czyli zaczęlibyśmy w stanie q0 i dla symbolu 1 dostalibyśmy się do stanów {q1, q2}. Kolejny symbol 1 przeniósłby nas do stanów {q0,q3} i tak dalej dla kolejnych symboli. Na koniec znaleźlibyśmy się we wszystkich stanach {q0, q1, q2, q3} i automat zaakceptowałby słowo.

Źródła

Rozdziały: Automat skończony, Automat zupełny, Niedeterministyczny automat skończony, Symulacja NFA, Przekształcenie NFA w DFA