Niedeterministyczny automat skończony

Automat skończony wprowadzony w poprzednich rozdziałach (w skrócie KA lub DKA) był zawsze deterministyczny, co przejawiało się tym, że było jasne, co automat zrobi w dowolnym momencie. Przyjrzymy się teraz bardziej ogólnej koncepcji niedeterministycznych automatów skończonych (w skrócie NKA), w których mogą występować przejścia rozpoczynające się od tego samego stanu i dotyczące tego samego symbolu.

Przykład

Spójrz na poniższy diagram automatu:

Co jest w nim szczególnego? To, że istnieją dwie krawędzie prowadzące od węzła q₀ dla symbolu 0. Tak więc, jeśli spróbujemy zaakceptować słowo 001, wydaje się, że automat nie będzie wiedział, czy pozostać w stanie q₀, czy też podążać za przejściem do q₁. Taki automat byłby niedeterministyczny.

Determinizm w tym sensie oznacza, że w każdej sytuacji jest jasne, co zrobi automat, nie ma miejsca na dwuznaczność. Automat deterministyczny ma tylko jedno przejście dla każdego stanu i każdego symbolu. Niedeterminizm oznacza niejednoznaczność - mogą istnieć trzy przejścia z jednego stanu dla tego samego symbolu.

Jak więc automat podejmuje decyzję? Niedeterministyczny automat zawsze wybiera (czasami mówimy też "zgaduje") przejście, które doprowadzi go do zaakceptowania słowa; jeśli to możliwe.

Jeśli umieścimy w automacie słowo 001, automat ma następujące opcje, co zrobić z tym słowem:

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

plus opcje, w których nie czyta całego słowa. W pierwszej z nich nadal pozostaje w stanie q₀, co z pewnością może, reguły przejścia na to pozwalają. W drugiej gałęzi zapuścił się w inne stany i ostatecznie osiągnął stan q₂, który jest stanem końcowym. W tej gałęzi automat zaakceptowałby słowo. Niedeterministyczny automat zawsze automatycznie wybierze gałąź, w której zaakceptuje słowo, jeśli taka gałąź istnieje.

W jaki sposób automatycznie wybiera "korzystną" gałąź? Możemy myśleć o tym jako o niedeterministycznym automacie przechodzącym przez wszystkie możliwe gałęzie i jeśli znajdzie gałąź, w której akceptuje słowo, to akceptuje słowo. Jak mógłby przejść przez wszystkie gałęzie? Krótko mówiąc, w momencie, gdy znajdzie się w stanie, z którego prowadzi dla bieżącego n symbolu krawędzi, automat n- skopiuje się kilka razy, a każda kopia obierze inną ścieżkę. W ten sposób przejdzie przez wszystkie możliwości jedna po drugiej.

Drzewiasta reprezentacja obliczeń automatu

Nieznacznie zmodyfikujemy poprzedni automat:

Niedeterminizm pozostaje w pierwszym stanie. Poprzedni automat akceptował wszystkie słowa kończące się na 01. Ten zmodyfikowany automat akceptuje wszystkie słowa zawierające podsłowo 01. Akceptuje więc na przykład słowo 101 lub 0101. Możemy łatwo zwizualizować wszystkie gałęzie obliczeń za pomocą drzewa, np. dla słowa 01010 drzewo może wyglądać następująco:

Na początku jesteśmy w stanie początkowym q₀. Na wejściu mamy słowo 01010, pierwszy nieodczytany znak to 0. Ze stanu q₀ są dwa przejścia dla symbolu 0, do stanów q₀ i q₁. Tak więc drzewo będzie miało dwa elementy potomne w tym węźle: q₀ i q₁. Następnie odczytujemy symbol 1. Nie ma tam niejednoznaczności, przechodzimy do stanów q₀ i q₂. Następnie odczytujemy symbol 0, ponownie występuje niejednoznaczność w lewej gałęzi, dzielimy obliczenia na dwie kolejne gałęzie. W jednej z nich pozostajemy ponownie w q₀, a w drugiej przechodzimy do q₁. I tak dalej.

Zauważ, że w sumie dwie gałęzie kończą się w q₂, stanie końcowym. Istnieją dwie gałęzie obliczeń, ponieważ automat może zaakceptować dane słowo. Tak więc ten automat zaakceptowałby słowo 01010. Możemy spróbować utworzyć podobne drzewo dla słowa 1000.

Obliczenia albo pozostaną w stanie q₀, albo przejdą do stanu q₁, ale stamtąd nie mają dokąd pójść, ponieważ na wejściu są już same zera, a stan q₁ ma przejście tylko dla symbolu 1. Żadna gałąź obliczeń nie kończy się w stanie końcowym, więc automat nie akceptuje słowa 1000.

Przejścia epsilon

W niedeterministycznych automatach możemy dodatkowo używać przejść epsilon. Są to przejścia, w których możemy wykonać dowolny symbol znajdujący się na wejściu bez odczytywania żadnego symbolu ze słowa. Jak moglibyśmy napisać niedeterministyczny automat, który akceptowałby puste słowo, wszystkie słowa składające się z samych jedynek oraz słowa postaci 10ⁿ, tj. 10, 1010, ...?

Podzielimy automat na dwa "pod-automaty". Górny zajmuje się rozpoznawaniem słów składających się z 1, dolny zajmuje się słowami postaci 10ⁿ. Spróbujmy zaakceptować słowo 111. Automat jest w stanie q₀ na początku i przyjmuje słowo 111 jako dane wejściowe. Ponieważ ma przejścia epsilon, może wybrać przejście do stanu q₁ lub q₂ według własnego uznania. Widzimy, że wygodne będzie dla niego przejście do stanu q₁. Automat tam przejdzie. Jednak na wejściu wciąż znajduje się słowo 111! Dopiero w tym momencie zacznie odczytywać symbole ze słowa i przejdzie ze stanu q₁ z powrotem do q₁, kiedy odczyta całe słowo i zaakceptuje je.

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

Dla słowa 1100 automat może zrobić wszystko, nie ma możliwości zaakceptowania takiego słowa.

Przejścia epsilon i niedeterminizm znacznie ułatwiają nam pracę na wiele sposobów, na przykład dowód, że unifikacja języka regularnego jest ponownie językiem regularnym, można zapisać znacznie bardziej jednoznacznie w przejściach epsilon niż w przypadku automatów skończonych. W tym dowodzie mieliśmy przykłady takich automatów

a

a następnie skonstruowaliśmy skończony automat deterministyczny, który akceptował unifikację obu języków. Z przejściami epsilon możemy skonstruować taki automat w następujący sposób:

W skrócie, dodajemy nowy stan początkowy, z którego dwa przejścia epsilon prowadzą do początkowych stanów oryginalnych automatów i to wszystko. Automat decyduje niedeterministycznie, czy spróbować zaakceptować słowo za pomocą jednej czy drugiej "pod-automaty".

Definicja niedeterministycznego automatu

Pokazaliśmy już, czym różnią się deterministyczne i niedeterministyczne automaty skończone, pozostaje tylko to sformalizować. Zdefiniowaliśmy deterministyczny automat skończony jako kwintyl $\left<Q, \Sigma, \delta, q_0, F\right>$, gdzie Q to zbiór stanów, $\Sigma$ to alfabet, δ to funkcja przejścia, q₀ to stan początkowy, a F to zbiór stanów końcowych. Jedyną rzeczą, która zmienia się w definicji niedeterministycznych automatów, jest definicja funkcji przejścia.

W wersji deterministycznej funkcja wywołująca δ(q, w) może zwracać tylko jeden stan, podczas gdy w wersji niedeterministycznej może zwracać wiele stanów - jeśli dla jednego symbolu zdefiniowano wiele przejść. Ponieważ musimy zdefiniować również przejścia epsilon, oznaczamy zbiór $\Sigma\cup\left\{\varepsilon\right\}$ jako zbiór $\Sigma_\varepsilon$, tj. $\Sigma_\varepsilon=\Sigma\cup\left\{\varepsilon\right\}$. W ten sposób definiujemy funkcję δ jako

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

To, że 2^Q oznacza zbiór potęgowy, zbiór wszystkich podzbiorów zbioru Q. Formalizacja obliczeń jest bardzo podobna do formalizacji automatów skończonych. Konfiguracją automatu jest ponownie para $\left<q, w\right> \in Q \times \Sigma^\ast$. Etap obliczania $\mapsto$ jest sesją na zbiorze konfiguracji takich, że

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

właśnie jeśli q_j ∈ δ(q_i, w₀). W tym twierdzeniu tkwi największa różnica. W automatach deterministycznych warunek ten zapisywaliśmy jako q_j = δ(q_i, w₀), ponieważ funkcja δ zawsze zwracała pojedynczy stan. Niedeterministyczna wersja funkcji przejścia zwraca zbiór stanów, stąd symbol ∈. Refleksyjne i przechodnie domknięcie sesji ponownie oznaczymy przez $\mapsto^\ast$. Powiemy, że automat akceptuje słowo w tylko wtedy, gdy istnieje q_f ∈ F taki, że

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

Zasoby

• M. Sipser: Wprowadzenie do teorii obliczeń
• Aho, Sethi, Ullman: Kompilatory: zasady, techniki i narzędzia