Stany nadmiarowe
Kapitoly: Stany nieosiągalne, Stany nadmiarowe, Minimalizacja automatu
Automat skończony może mieć stany, z których nie da się przejść do stanu skończonego, a więc są one bezużyteczne. Takie stany nazywamy stanami nieosiągalnymi. Zazwyczaj chcemy je usunąć, ponieważ tylko niepotrzebnie komplikują działanie automatu.
Przykład nadmiarowych stanów
Rozważmy ten skończony automat:
Widzimy, że w momencie osiągnięcia stanów q4 lub q5, nigdy nie możemy osiągnąć jednego ze skończonych stanów q1 lub q2. Takie stany są tak nadmiarowe, że możemy je po prostu usunąć, co dałoby nam nowy automat, ale taki, który jest równoważny; akceptowałby ten sam język. Po usunięciu nadmiarowych stanów automat wyglądałby tak:
Akceptowałby ten sam język. Istnieją jednak sytuacje, w których nadmiarowe stany są wskazane - na przykład podczas konstruowania automatu całkowitego.
Definicja stanu nadmiarowego
Rozważmy automat skończony $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Mówimy, że stan q ∈ Q jest nadmiarowy, jeśli nie istnieje żadne słowo $w \in \Sigma^+$ i żaden stan qf ∈ F taki, że
$$ \left<q, w\right>\mapsto^\ast\left<q_f,\varepsilon\right>. $$
Jak usunąć stany nadmiarowe
Załóżmy, że jako dane wejściowe mamy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$, który jest już wolny od nieosiągalnych stanów. Będziemy kolejno znajdować stany, które prowadzą do stanów końcowych, a następnie stany, które prowadzą do stanów, które prowadzą do stanów końcowych, i tak dalej. W ten sposób otrzymamy zbiór wszystkich stanów, które nie są redundantne. Zaczynamy od S0 = F. Skonstruujemy inne zbiory Si dla i ∈ ℕ zgodnie z tą receptą:
$$ S_i = \left\{q,|,\forall q \in Q, a \in \Sigma:\quad \delta(q, a)\in S_{i-1}\right\}\cup S_{i-1} $$
Wynikowy zbiór wszystkich stanów, które nie są nadmiarowe, można wyrazić następująco:
$$ \bigcup_{i=1}^{\infty}S_i. $$
A zbiór stanów nadmiarowych jako
$$ Q \setminus \bigcup_{i=1}^{\infty}S_i. $$
Innymi słowy, jeśli Si = Si + 1 zachodzi, to zbiór Q∖ Si zawiera stany nadmiarowe. Zilustrujemy tę procedurę następującym automatem:
Najpierw tworzymy zbiór S0 = {q1, q2}. Następnie tworzymy zbiór S1, dodając do zbioru S0 wszystkie stany, które prowadzą do jednego ze stanów w zbiorze S0. W ten sposób dodajemy stany q0 i q3, ponieważ q0 prowadzi do q1, a q3 prowadzi do q2. Otrzymujemy S1 = {q0, q1, q2, q3}. Ponieważ S0 ≠ S1, postępujemy dalej.
Konstruujemy zbiór S2. W ten sposób szukamy wszystkich stanów, z których możemy dostać się do S1, a które nie znajdują się w S1. Istnieje jeden stan, q6, z którego możemy dostać się do q3. Otrzymujemy S2 = {q0, q1, q2, q3, q6}. Ponieważ S1≠ S2, kontynuujemy.
Konstruujemy zbiór S3. Czy istnieje nowy stan, z którego można dostać się do dowolnego ze stanów w S2? Nie, ze stanów q4 i q5 nie można dostać się do żadnego ze stanów w S2, a pozostałe stany są już w S2. Zatem prawdą jest, że S3 = {q0, q1, q2, q3, q6}. Ponieważ S2 = S3, algorytm kończy się, a zbiór S2 reprezentuje zbiór stanów, które nie są redundantne. Zbiór {q4, q5} jest zbiorem stanów, które są nadmiarowe.
Formalnie, konstruujemy nowy równoważny automat bez nadmiarowych symboli w następujący sposób. Mamy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$ i budujemy równoważny mu automat $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F\right>$ bez nadmiarowych symboli.
- $Q^\prime = Q \setminus \bigcup_{i=1}^\infty S_i$
- $\forall q \in Q^\prime, a\in \Sigma:\quad \delta^\prime(q, a) = \delta(q, a)$