STROJIRENSTVI.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Nadbytečné stavy

Zobrazit kapitoly článku
  1. Nedosažitelné stavy
  2. Nadbytečné stavy
  3. 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

\[\left< q, w\right>\mapsto^\ast\left< q_f,\varepsilon\right>.\]

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:

\[S_i = \left\{q\,|\,\forall q \in Q, a \in \Sigma:\quad \delta(q, a)\in S_{i-1}\right\}\cup S_{i-1}\]

Výslednou množinu všech stavů, které nejsou nadbytečné můžeme vyjádřit takto:

\[\bigcup_{i=1}^{\infty}S_i.\]

A množinu nadbytečných stavů jako

\[Q \setminus \bigcup_{i=1}^{\infty}S_i.\]

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 #