Stany nieosiągalne
Kapitoly: Stany nieosiągalne, Stany zbędne, Minimalizacja automatu
Automat skończony może mieć stany, do których nie da się dostać. Takie stany nazywamy stanami nieosiągalnymi. Zwykle chcemy je usunąć, bo tylko niepotrzebnie komplikują cały automat.
Przykład stanów nieosiągalnych
Weźmy taki automat:
Widzimy, że cokolwiek zrobimy, do stanu q3 nigdy się nie dostaniemy, bo nie prowadzi do niego żadne przejście. O stanie q3 powiemy więc, że jest nieosiągalny. Pytanie – czy stan q3 byłby osiągalny, gdyby prowadziło do niego jakieś przejście z innego stanu? Gdybyśmy poprowadzili krawędź z jednego ze stanów q0, q1, q2, q5, to byłby osiągalny. Gdybyśmy dodali kolejny węzeł i poprowadzili przejście z niego…
…to oczywiście oba stany q3 i q4 byłyby nieosiągalne.
Definicja stanu nieosiągalnego
Najpierw zdefiniujemy stan osiągalny. Weźmy automat skończony $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Powiemy, że stan q ∈ Q jest osiągalny, jeśli istnieje słowo $w \in \Sigma^\ast$ takie, że
$$ \left<q_0, w\right> \mapsto^\ast \left<q, \varepsilon\right>. $$
Stan q ∈ Q jest nieosiągalny, jeśli nie jest osiągalny.
Jak usunąć stany nieosiągalne
Jeśli automat ma już jakieś stany nieosiągalne, warto je usunąć. Zbudujemy więc równoważny automat $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F^\prime\right>$, który nie będzie miał stanów nieosiągalnych.
Zbiór stanów osiągalnych będziemy budować iteracyjnie. Zaczniemy od zbioru S0 = {q0}, bo stan początkowy na pewno jest osiągalny. Kolejny zbiór zbudujemy tak:
$$ S_i = \left\{r,|, \delta(q, a) = r \mbox{ dla pewnego } q \in S_{i-1}, a\in \Sigma \right\} \cup S_{i-1} $$
Mówiąc po ludzku: zbiór S0 jest zawsze dany, zbiór S1 zbudujemy tak, że weźmiemy wszystkie stany ze zbioru S0 i sprawdzimy, dokąd wszędzie prowadzą z nich przejścia dla wszystkich symboli z $\Sigma$. Te stany dodamy (suma zbiorów) do pierwotnego zbioru stanów S0. Tym samym sposobem wyznaczymy zbiór S2 i kolejne. Oczywiście będzie zachodzić $S_{i-1} \subseteq S_{i}$.
Zbiór stanów osiągalnych możemy wtedy otrzymać tak:
$$ \bigcup_{i=1}^\infty S_i $$
Może wyglądać dziwnie, że próbujemy wziąć sumę nieskończenie wielu zbiorów Si, ale automat ma tylko skończoną liczbę stanów. To znaczy, że w pewnym momencie zbiory Sj i Sj + 1 oraz wszystkie kolejne będą takie same, więc nawet po zsumowaniu nieskończenie wielu zbiorów możemy otrzymać skończony zbiór stanów.
Wróćmy do automatu
i spróbujmy znaleźć zbiór stanów osiągalnych. Zaczniemy od tego, że przyjmiemy podstawową równość
$$ S_0 = \left\{q_0\right\} $$
Teraz obliczymy zbiór S1. Musimy więc znaleźć wszystkie przejścia ze stanu q0 i ich stany docelowe dodać do zbioru S0. Ponieważ zachodzi $q_0\rightarrow^a q_1$ i $q_0\rightarrow^bq_2$, zbiór S1 będzie dodatkowo zawierał stany q1 i q2:
$$ S_1 = \left\{q_0, q_1, q_2\right\} $$
Dalej zbudujemy zbiór S2. Sprawdzamy, dokąd wszędzie możemy się dostać ze stanów q0, q1, q2. Jedynym nowym stanem jest q5, do którego możemy się dostać ze stanu q1:
$$ S_2 = \left\{q_0, q_1, q_2, q_5\right\} $$
Dalej zbudujemy zbiór S3. Czy ze stanów q0, q1, q2, q5 możemy dostać się do jakiegoś nowego stanu? Nie możemy, więc zbiór S3 będzie zawierał te same elementy co S2:
$$ S_3 = \left\{q_0, q_1, q_2, q_5\right\} $$
Ponieważ S2 = S3, to także S3 = S4 = S5 = … Jeśli zsumujemy wszystkie Si, otrzymamy zbiór S2, bo w żadnym kolejnym zbiorze nie przybędzie już żaden element.
Zbiór stanów osiągalnych automatu jest więc równy {q0, q1, q2, q5}. Stany nieosiągalne otrzymamy zwykłą różnicą zbiorów:
$$ Q \setminus \bigcup_{i=1}^\infty S_i $$
Zbiór stanów nieosiągalnych naszego automatu to {q3, q4}. Usuniemy z automatu A wszystkie stany nieosiągalne i wszystkie przejścia, w których występował jakiś stan nieosiągalny. Czyli równoważny automat bez stanów nieosiągalnych $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F^\prime\right>$ dla automatu $A=\left<Q, \Sigma, \delta, q_0, F\right>$ definiujemy jako:
- $Q^\prime = \bigcup_{i=1}^\infty S_i$
- $\forall q \in Q^\prime, a\in \Sigma:\quad \delta^\prime(q, a) = \delta(q, a)$
- $F^\prime = F \cap Q^\prime = F \cap \bigcup_{i=1}^\infty S_i$