Symulacja automatu niedeterministycznego
Kapitoly: Automat skończony, Automat zupełny, Niedeterministyczny automat skończony, Symulacja NFA, Przekształcenie NFA w DFA
Jeśli mamy automat niedeterministyczny i chcemy sprawdzić, czy akceptuje dane słowo, możemy zamienić go na deterministyczny, możemy to jakoś wypróbować albo możemy użyć algorytmu, który będzie symulował działanie NFA.
Zasada algorytmu
Zasadę pokażemy poglądowo na odpowiednim przykładzie. Weźmy taki automat:
Jest to niedeterministyczny automat skończony, który akceptuje jakiś język. Jaki – to nas teraz zupełnie nie musi interesować. Pokażemy, jak może wyglądać obliczenie takiego automatu dla słowa wejściowego 11001. Rozumowanie będzie takie: przetworzymy symbol ze słowa i sprawdzimy, dokąd wszędzie możemy pójść dzięki wielu przejściom dla tego samego symbolu. Zapamiętamy wszystkie te stany i w kolejnym kroku będziemy już zakładać, że jesteśmy „we wszystkich tych stanach jednocześnie”, i będzie nas interesować, dokąd z tych stanów możemy dostać się dalej.
Będziemy więc pamiętać zbiór stanów, w których możemy się znajdować, oraz nieprzeczytaną część słowa. Na początku mamy więc parę <{q0}, 11001>. Zaczynamy w stanie q0 (stan początkowy), a na wejściu jest słowo 11001. Automat wygląda tak (stan, w którym jesteśmy, jest zaznaczony na czerwono i pogrubiony):
Pierwszym symbolem jest 1, ze stanu q0 wychodzi tylko jedno przejście dla symbolu 1, więc dostaniemy się do stanu q1. Zapamiętamy parę <{q1}, 1001>. Automat wygląda tak:
Idziemy dalej. Nieprzeczytana część słowa ma postać 1001, więc znowu szukamy przejść dla 1. Tym razem są dwa – z powrotem do stanu q0 i dalej do stanu q3. Teraz wyruszymy do obu stanów jednocześnie. Zapamiętamy więc parę <{q0, q3}, 001>.
Jaki to ma sens? Wiemy, że czytając słowo 11, możemy ze stanu początkowego dojść zarówno do stanu q3, jak i do stanu q0. Na razie jeszcze nie wiemy, która gałąź nam się przyda, więc po prostu zapamiętamy obie. Idziemy dalej. Na wejściu mamy symbol 0. Teraz musimy patrzeć zarówno na przejścia z q0, jak i na przejścia z q3. Ze stanu q0 wychodzą przejścia do stanów q1 i q2, ze stanu q3 wychodzi przejście z powrotem do q1. Uwzględniamy wszystkie te stany i dostajemy parę <{q1, q2}, 01>:
Ale w tym kroku jeszcze nie skończyliśmy. Widzimy, że ze stanu q2 wychodzi epsilon-przejście do stanu q4. Wiemy, że epsilon-przejściem możemy „pójść kiedykolwiek”, nie czytając kolejnego znaku. Innymi słowy – nie czytając kolejnego symbolu ze słowa wejściowego, możemy jeszcze przejść do stanu q4. Dodajemy więc stan q4 do stanów, w których możemy się znajdować: <{q1, q2, q4}, 01>. Automat pokolorowalibyśmy tak:
Dalej na wejściu jest 0. Sprawdzamy, dokąd możemy przejść z tych trzech stanów, w których jesteśmy. Z q1 nie możemy przejść nigdzie, bo brakuje przejścia dla 0. Obliczenie w tej gałęzi się kończy. Ze stanu q4 też nigdzie się nie dostaniemy. Ze stanu q2 dostaniemy się z powrotem do stanu q2. Ale ponieważ ze stanu q2 znowu wychodzi epsilon-przejście do stanu q4, możemy dostać się także do stanu q4. Ze zbioru stanów {q1, q2, q4} możemy więc dla symbolu 0 dostać się do zbioru stanów {q2, q4}, dostajemy parę <{q2, q4}, 1>:
Na koniec mamy na wejściu symbol 1. Ze stanu q2 nigdzie się nie dostaniemy, obliczenie w tej gałęzi się kończy. Ze stanu q4 dostaniemy się natomiast do stanów q3 i q5. Dostajemy parę $\left<\left\{q_3, q_5\right\}, \varepsilon\right>$:
Automat przeczytał teraz całe słowo i „znajduje się” w dwóch stanach: q3, q5. Ponieważ co najmniej jeden z nich jest stanem akceptującym, automat akceptuje słowo 11001.
Algorytm
Najpierw potrzebujemy funkcji, która jako argument przyjmie zbiór stanów i obliczy, do których stanów możemy się jeszcze dostać za pomocą epsilon-przejść. Wejściem jest więc automat $\left<Q, \Sigma, \delta, q_0, F\right>$ i zbiór stanów States, a wyjściem nadzbiór tych stanów, do których da się dostać za pomocą epsilon-przejść. Tę operację będziemy nazywać epsilon-domknięciem zbioru States (ang. epsilon closure).
$$\begin{align}\\ &\mathbf{Function} EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, States\right)\\ &\qquad NextStates \leftarrow \emptyset\\ &\qquad \mathbf{ForEach} q \in States \mathbf{Do}\\ &\qquad \qquad NextStates \leftarrow NextStates \cup \left\{q\right\} \cup \delta(q, \varepsilon)\\ &\qquad \mathbf{EndFor}\\ &\qquad \\ &\qquad \mathbf{If} NextStates \setminus States = \emptyset \mathbf{Do}\\ &\qquad \qquad \mathbf{Return} States\\ &\qquad \mathbf{Else}\\ &\qquad \qquad \mathbf{Return} EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, NextStates\right)\\ &\qquad \mathbf{EndIf}\\ &\mathbf{EndFunction}\\ &\end{align}$$
Tej funkcji użyjemy w funkcji, która będzie symulować działanie automatu niedeterministycznego. Wejściem jest automat, słowo wejściowe w = w1w2… wn i zbiór stanów, w których automat aktualnie się znajduje. Wyjściem jest odpowiedź TAK albo NIE, zależnie od tego, czy automat dane słowo akceptuje, czy nie.
$$\begin{align}\\ &\mathbf{Function} ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w, States\right)\\ &\qquad \mathbf{If} w = \epsilon \mathbf{Do}\\ &\qquad \qquad \mathbf{If} States \cap F \ne \emptyset \mathbf{Do}\\ &\qquad \qquad \qquad \mathbf{Return} \mbox{TAK}\\ &\qquad \qquad \mathbf{Else}\\ &\qquad \qquad \qquad \mathbf{Return} \mbox{NIE}\\ &\qquad \qquad \mathbf{EndIf}\\ &\qquad \mathbf{EndIf}\\ &\qquad NextStates \leftarrow \emptyset\\ &\qquad \mathbf{ForEach} q \in States \mathbf{Do}\\ &\qquad \qquad NextStates \leftarrow NextStates \cup \delta(q, w_1)\\ &\qquad \mathbf{EndFor}\\ &\qquad NextStates \leftarrow EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, NextStates\right)\\ &\qquad \mathbf{Return} ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w_2w_3\dots w_n, NextStates\right)\\ &\mathbf{EndFunction}\\ &\end{align}$$
Jeśli chcemy sprawdzić, czy automat akceptuje słowo w, wywołujemy funkcję tak: $ComputeNFA\left(\left<Q, \Sigma, \delta, q_0, F\right>, w, EpsilonClosure\left(\left<Q, \Sigma, \delta, q_0, F\right>, \left\{q_0\right\}\right)\right)$. Epsilon-domknięcie zbioru początkowego jest potrzebne, gdy ze stanu początkowego wychodzą epsilon-przejścia.