Niedeterministyczny automat skończony

Automat skończony przedstawiony w poprzednich rozdziałach (w skrócie DFA, od ang. deterministic finite automaton) był zawsze deterministyczny, co objawiało się tym, że w każdej chwili było jasne, co automat zrobi. Teraz przyjrzymy się ogólniejszemu pojęciu niedeterministycznych automatów skończonych (w skrócie NFA, od ang. nondeterministic finite automaton), w których mogą istnieć przejścia wychodzące z tego samego stanu dla tego samego symbolu.

Przykład

Spójrz na następujący diagram automatu:

Co jest w nim dziwnego? To, że z węzła q₀ wychodzą dwie krawędzie dla symbolu 0. Jeśli więc spróbujemy zaakceptować słowo 001, mogłoby się wydawać, że automat nie będzie wiedział, czy ma zostać w stanie q₀, czy pójść przejściem do q₁. Taki automat byłby niedeterministyczny.

Determinizm w tym ujęciu oznacza, że w każdej sytuacji jest jasne, co automat zrobi – nie ma miejsca na niejednoznaczność. Automat deterministyczny ma dla każdego stanu i każdego symbolu tylko jedno przejście. Niedeterminizm oznacza niejednoznaczność – z jednego stanu dla tego samego symbolu mogą prowadzić na przykład trzy przejścia.

Jak więc automat zdecyduje? Automat niedeterministyczny zawsze wybierze (mówimy też, że „zgadnie”) to przejście, które doprowadzi do zaakceptowania słowa – o ile to możliwe.

Jeśli podamy automatowi słowo 001, automat ma następujące możliwości, co zrobić ze słowem:

\begin{eqnarray} q_0 \rightarrow q_0 \rightarrow q_0 \rightarrow q_0\\ q_0 \rightarrow q_0 \rightarrow q_1 \rightarrow q_2 \end{eqnarray}

plus możliwości, w których nie przeczyta całego słowa. W pierwszej gałęzi cały czas zostawał w stanie q₀, co na pewno może, reguły przejścia mu na to pozwalają. W drugiej gałęzi odważył się pójść do kolejnych stanów i w końcu doszedł do stanu q₂, który jest akceptujący. W tej gałęzi automat zaakceptowałby słowo. Automat niedeterministyczny zawsze automatycznie wybierze tę gałąź, w której słowo akceptuje, jeśli taka gałąź istnieje.

Jak to robi, że automatycznie wybiera tę „korzystną” gałąź? Możemy to sobie wyobrazić tak, że automat niedeterministyczny przechodzi wszystkie możliwe gałęzie i jeśli znajdzie gałąź, w której słowo akceptuje, to słowo akceptuje. Jak mógłby przejść wszystkie gałęzie? Po prostu w chwili, gdy jest w stanie, z którego dla aktualnego symbolu wychodzi n krawędzi, automat kopiuje sam siebie n razy i każda kopia idzie inną drogą. W ten sposób stopniowo przejdziemy wszystkie możliwości.

Drzewo obliczeń automatu

Lekko zmodyfikujemy poprzedni automat:

Niedeterminizm zostaje w pierwszym stanie. Poprzedni automat akceptował wszystkie słowa kończące się na 01. Ten zmodyfikowany automat akceptuje wszystkie słowa, które zawierają podsłowo 01. Akceptuje więc na przykład słowo 101 albo 0101. Wszystkie gałęzie obliczenia łatwo zobrazujemy za pomocą drzewa, np. dla słowa 01010 drzewo mogłoby wyglądać tak:

Na początku jesteśmy w stanie początkowym q₀. Na wejściu mamy słowo 01010, pierwszy nieprzeczytany znak to 0. Ze stanu q₀ wychodzą dwa przejścia dla symbolu 0, do stanów q₀ i q₁. Drzewo będzie więc miało w tym węźle dwóch potomków: q₀ i q₁. Dalej czytamy symbol 1. Tu żadnej niejednoznaczności nie ma, przechodzimy do stanów q₀ i q₂. Następnie czytamy znak 0 – w lewej gałęzi znowu pojawia się niejednoznaczność, więc dzielimy obliczenie na dwie kolejne gałęzie. W jednej znowu zostajemy w q₀, a w drugiej idziemy do q₁. I tak dalej.

Zauważ, że w sumie dwie gałęzie kończą się w stanie q₂, czyli w stanie akceptującym. Istnieją dwie gałęzie obliczenia, w których automat może zaakceptować dane słowo. Ten automat zaakceptowałby więc słowo 01010. Możemy spróbować zbudować podobne drzewo dla słowa 1000.

Obliczenie albo zostaje w stanie q₀, albo przechodzi do stanu q₁, ale stamtąd nie ma już dokąd pójść, bo na wejściu są same zera, a stan q₁ ma przejście tylko dla symbolu 1. Żadna gałąź obliczenia nie kończy się w stanie akceptującym, więc automat słowa 1000 nie akceptuje.

Epsilon-przejścia

W automatach niedeterministycznych możemy dodatkowo używać epsilon-przejść. Są to przejścia, które możemy wykonać bez względu na to, jaki symbol jest na wejściu, i to bez czytania jakiegokolwiek symbolu ze słowa. Jak napisać automat niedeterministyczny, który akceptowałby słowo puste, wszystkie słowa złożone tylko z jedynek oraz słowa postaci (10)ⁿ, czyli 10, 1010, …?

Podzieliliśmy automat na dwa „podautomaty”. Górny dba o to, żeby rozpoznać słowa złożone z jedynek, dolny zajmuje się słowami postaci (10)ⁿ. Spróbujmy zaakceptować słowo 111. Automat na początku znajduje się w stanie q₀ i ma na wejściu słowo 111. Ponieważ ma do dyspozycji epsilon-przejścia, może zdecydować, czy przejść do stanu q₁, czy q₂, zależnie od tego, co mu bardziej pasuje. Widzimy, że opłaci mu się przejść do stanu q₁. Automat tam przechodzi. Przy tym na wejściu wciąż ma słowo 111! Dopiero w tym momencie zaczyna czytać symbole ze słowa i przechodzić ze stanu q₁ znowu do q₁, aż przeczyta całe słowo i je zaakceptuje.

Gdybyśmy spróbowali zaakceptować 1010, automat na początku przeszedłby do stanu q₂ i dopiero stamtąd zacząłby przetwarzać symbole – i znowu by słowo zaakceptował.

Przy słowie 1100 automat mógłby robić cokolwiek, takiego słowa nie ma jak zaakceptować.

Epsilon-przejścia i niedeterminizm w wielu sprawach ułatwiają nam pracę. Na przykład dowód tego, że suma języków regularnych jest znowu językiem regularnym, można z epsilon-przejściami zapisać znacznie prościej niż w przypadku automatów deterministycznych. W tamtym dowodzie mieliśmy przykłady takich automatów

i

a dalej zbudowaliśmy deterministyczny automat skończony, który akceptował sumę obu języków. Z epsilon-przejściami możemy taki automat zbudować tak:

Po prostu dodajemy nowy stan początkowy, z którego wychodzą dwa epsilon-przejścia do stanów początkowych obu pierwotnych automatów, i to wszystko. Automat niedeterministycznie zdecyduje, czy spróbuje zaakceptować słowo jednym, czy drugim „podautomatem”.

Definicja automatu niedeterministycznego

Pokazaliśmy już, czym różni się deterministyczny i niedeterministyczny automat skończony, pozostaje to tylko sformalizować. Deterministyczny automat skończony zdefiniowaliśmy jako piątkę $\left<Q, \Sigma, \delta, q_0, F\right>$, gdzie Q jest zbiorem stanów, $\Sigma$ alfabetem, δ funkcją przejścia, q₀ stanem początkowym, a F zbiorem stanów akceptujących. Jedyne, co się zmienia w definicji automatów niedeterministycznych, to definicja funkcji przejścia.

W wersji deterministycznej funkcja przy wywołaniu δ(q, w) mogła zwrócić tylko jeden stan, natomiast w wersji niedeterministycznej może zwrócić więcej stanów – jeśli dla jednego symbolu określono więcej przejść. Ponieważ musimy zdefiniować także epsilon-przejścia, oznaczymy zbiór $\Sigma\cup\left\{\varepsilon\right\}$ jako $\Sigma_\varepsilon$, czyli $\Sigma_\varepsilon=\Sigma\cup\left\{\varepsilon\right\}$. Funkcję δ definiujemy więc jako

$$ \delta: Q \times \Sigma_\varepsilon\rightarrow 2^Q $$

To 2^Q oznacza zbiór potęgowy, czyli zbiór wszystkich podzbiorów zbioru Q. Formalny opis obliczenia jest bardzo podobny jak w przypadku automatów deterministycznych. Konfiguracja automatu to znowu para $\left<q, w\right> \in Q \times \Sigma^\ast$. Krok obliczenia $\mapsto$ to relacja na zbiorze konfiguracji taka, że

$$ \left<q_i, w_0w_1\dots w_n\right> \mapsto \left<q_j, w_1\dots w_n\right>, $$

wtedy i tylko wtedy, gdy q_j ∈ δ(q_i, w₀). W tym zdaniu kryje się największa różnica. W automatach deterministycznych ten warunek zapisywaliśmy jako q_j = δ(q_i, w₀), bo funkcja δ zwracała zawsze jeden stan. Niedeterministyczna wersja funkcji przejścia zwraca zbiór stanów, dlatego jest tam symbol ∈. Domknięcie zwrotne i przechodnie tej relacji znowu oznaczymy $\mapsto^\ast$. Powiemy, że automat akceptuje słowo w wtedy i tylko wtedy, gdy istnieje q_f ∈ F taki, że

$$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>.$$

Źródła

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools