Stany zbędne
Kapitoly: Stany nieosiągalne, Stany zbędne, Minimalizacja automatu
Automat skończony może mieć stany, z których nie da się dostać do stanu akceptującego, więc są niepotrzebne. Takie stany nazywamy stanami zbędnymi (spotkasz też nazwę stany bezużyteczne). Zwykle chcemy je usunąć, bo tylko niepotrzebnie komplikują cały automat.
Przykład stanów zbędnych
Weźmy taki automat skończony:
Widzimy, że gdy tylko dostaniemy się do stanu q4 albo q5, nigdy już nie uda nam się dostać do żadnego ze stanów akceptujących q1 i q2. Takie stany są więc zbędne i możemy je po prostu usunąć – otrzymalibyśmy w ten sposób nowy automat, który byłby jednak równoważny, czyli akceptowałby ten sam język. Po usunięciu stanów zbędnych automat wyglądałby tak:
Akceptowałby przy tym ten sam język. Bywają jednak sytuacje, kiedy warto mieć jakieś stany zbędne – na przykład gdy budujemy automat zupełny.
Definicja stanu zbędnego
Weźmy automat skończony $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Powiemy, że stan q ∈ Q jest zbędny, jeśli nie istnieje żadne słowo $w \in \Sigma^\ast$ i żaden stan qf ∈ F takie, że
$$ \left<q, w\right>\mapsto^\ast\left<q_f,\varepsilon\right>. $$
Jak usunąć stany zbędne
Zakładamy, że na wejściu mamy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$, który nie ma już stanów nieosiągalnych. Będziemy stopniowo znajdować stany, które prowadzą do stanów akceptujących, potem stany, które prowadzą do stanów prowadzących do stanów akceptujących, i tak w kółko. W ten sposób otrzymamy zbiór wszystkich stanów, które nie są zbędne. Na początku przyjmiemy S0 = F. Kolejne zbiory Si dla i ∈ ℕ będziemy budować według takiego przepisu:
$$ S_i = \left\{q \in Q,|,\exists 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ą zbędne, możemy zapisać tak:
$$ \bigcup_{i=1}^{\infty}S_i. $$
A zbiór stanów zbędnych jako
$$ Q \setminus \bigcup_{i=1}^{\infty}S_i. $$
Innymi słowy: jeśli zachodzi Si = Si + 1, to zbiór Q∖ Si zawiera stany zbędne. Postępowanie zilustrujemy na takim automacie:
Najpierw przyjmiemy równość S0 = {q1, q2}. Dalej zbudujemy zbiór S1 tak, że do zbioru S0 dodamy wszystkie stany, które prowadzą do jednego ze stanów ze zbioru S0. Dodamy więc stany q0 i q3, bo z q0 prowadzi przejście do q1, a z q3 prowadzi przejście do q2. Dostaniemy S1 = {q0, q1, q2, q3}. Ponieważ S0 ≠ S1, idziemy dalej.
Zbudujemy zbiór S2. Szukamy więc wszystkich stanów, z których da się dostać do S1, a które jeszcze nie należą do S1. Jest to tylko jeden stan, q6, z którego da się dostać do stanu q3. Dostaniemy S2 = {q0, q1, q2, q3, q6}. Ponieważ S1≠ S2, idziemy dalej.
Zbudujemy zbiór S3. Czy istnieje jakiś nowy stan, z którego da się dostać do któregoś ze stanów z S2? Nie istnieje – ze stanów q4 i q5 nie da się dostać do żadnego ze stanów z S2, a pozostałe stany już w S2 są. Zachodzi więc S3 = {q0, q1, q2, q3, q6}. Ponieważ S2 = S3, algorytm się kończy, a zbiór S2 jest zbiorem stanów, które nie są zbędne. Zbiór {q4, q5} jest zbiorem stanów, które zbędne są.
Formalnie nowy równoważny automat bez stanów zbędnych zbudujemy tak. Mamy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$ i budujemy do niego równoważny automat $A^\prime=\left<Q^\prime, \Sigma, \delta^\prime, q_0, F\right>$ bez stanów zbędnych.
- $Q^\prime = \bigcup_{i=1}^\infty S_i$
- $\forall q \in Q^\prime, a\in \Sigma:\quad \delta^\prime(q, a) = \delta(q, a)$, jeśli $\delta(q, a) \in Q^\prime$; w przeciwnym razie $\delta^\prime(q, a)$ nie jest określona