Nadbytečné stavy
- Nedosažitelné stavy
- Nadbytečné stavy
- Minimalizace automatu
Konečný automat může mít stavy, ze kterých se není možné dostat do koncového stavu a jsou tak zbytečné. Takovým stavům říkáme nedosažitelné stavy. Tyto stavy typicky chceme odstranit, protože pouze zbytečně zkomplikovávají celý automat.
Příklad nadbytečných stavů #
Mějme tento konečný automat:
Vidíme, že ve chvíli, kdy se dostaneme do stavů q4 nebo q5, tak už se nám nikdy nepodaří dostat do jednoho z koncových stavů q1 nebo q2. Takové stavy jsou tak nadbytečné a můžeme je prostě odstranit, čímž bychom získali nový automat, který by byl ale ekvivalentní; přijímal by stejný jazyk. Po smazání nadbytečných stavů by automat vypadal takto:
Přijímal by přitom stejný jazyk. Nicméně jsou okamžiky, kdy je vhodné nějaké nadbytečné stavy mít – například když sestrojujeme totální automat.
Definice nadbytečného stavu #
Mějme konečný automat \(A=\left< Q, \Sigma, \delta, q_0, F\right>\). Řekneme, že stav \(q \in Q\) je nadbytečný, pokud neexistuje žádné slovo \(w \in \Sigma^+\) a žádný stav \(q_f \in F\) takový, že
Jak odstranit nadbytečné stavy #
Předpokládáme, že na vstupu máme automat \(A=\left< Q, \Sigma, \delta, q_0, F\right>\), který už je bez nedosažitelných stavů. Budeme postupně nalézet stavy, které vedou do koncových stavů a pak stavy, které vedou do stavů, které vedou do koncových stavů a tak pořád dokola. Tím získáme množinu všech stavů, které nejsou nadbytečné. Na začátku položíme S0 = F. Budeme sestrojovat další množiny Si pro \(i \in \mathbb{N}\) podle tohoto předpisu:
Výslednou množinu všech stavů, které nejsou nadbytečné můžeme vyjádřit takto:
A množinu nadbytečných stavů jako
Jinými slovy: pokud platí Si = Si + 1, pak množina \(Q\setminus S_i\) obsahuje nadbytečné stavy. Postup si budeme ilustrovat na tomto automatu:
Jako první položíme rovnost S0 = {q1, q2}. Dále sestavíme množinu S1 tak, že k množině S0 přidáme všechny stavy, které vedou do jednoho ze stavů v množině S0. Přidáme tak stavy q0 a q3, protože z q0 vede přechod do q1 a z q3 vede přechod do q2. Dostaneme S1 = {q0, q1, q2, q3}. Protože S0 ≠ S1, pokračujeme dále.
Sestavíme množinu S2. Hledáme tak všechny stavy, ze kterých se lze dostat do S1 a přitom ještě v S1 nejsou. Je to jediný stav, q6, ze kterého se lze dostat do stavu q3. Dostaneme S2 = {q0, q1, q2, q3, q6}. Protože S1≠ S2, pokračujeme dále.
Sestavíme množinu S3. Existuje nějaký nový stav, ze kterého se lze dostat do některého ze stavů v S2? Neexistuje, ze stavů q4 a q5 se nelze dostat do žádného ze stavů v S2 a ostatní stavy už v S2 jsou. Platí tak, že S3 = {q0, q1, q2, q3, q6}. Protože S2 = S3, algoritmus končí a množina S2 představuje množinu stavů, které nejsou nadbytečné. Množina {q4, q5} je množina stavů, které nadbytečné jsou.
Formálně nový ekvivalentní automat bez nadbytečných symbolů sestavíme takto. Máme automat \(A=\left< Q, \Sigma, \delta, q_0, F\right>\) a sestavíme k němu ekvivalentní automat \(A^\prime=\left< Q^\prime, \Sigma, \delta^\prime, q_0, F\right>\) bez nadbytečných symbolů.
- \(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)\)
Zdroje #
- M. Sipser: Introduction to the Theory of Computation
- Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools
- Teorie konečných automatů, regulárních gramatik, jazyků a výrazů