3.3.3 Převody zásobníkových automatů

Zásobníkový automat je výpočetní model pro bezkontextové jazyky. Máme-li zadaný libovolný bezkontextový jazyk \(L\), pak platí, že každý ZA \(R_\varepsilon\) přijímající \(L\) s prázdným zásobníkem (tj. \(L_\varepsilon(R_\varepsilon) = L\)) lze algoritmicky převést na ZA \(R_f\) přijímající \(L\) přechodem do koncového stavu (tj. \(L(R_f) = L\)).

Toto tvrzení platí i obráceně. Pro každý bezkontextový jazyk tak existuje jak zásobníkový automat, který jej přijímá přechodem do koncového stavu, tak i zásobníkový automat, který jej přijímá prázdným zásobníkem.

(Převod ZA: Koncový stav \(\to\) Prázdný zásobník)

Převod ZA přijímajícího přechodem do koncového stavu na ZA přijímající prázdným zásobníkem

Tento převod zajistí, že jakmile původní automat vstoupí do koncového stavu, nový automat má možnost nedeterministicky přejít do speciálního stavu, ve kterém vymaže celý obsah zásobníku.

Vstup

Zásobníkový automat \(R_f = (Q_f, \Sigma, G_f, \delta_f, q_f, Z_f, F_f)\).

Výstup

Zásobníkový automat \(R_\varepsilon = (Q, \Sigma, G, \delta, q_0, Z_0, F)\), kde \(Z_0 \notin G_f\), takový, že \(L_\varepsilon(R_\varepsilon) = L(R_f)\).

Postup

1. Množina stavů: \(Q = Q_f \cup \{q_0, q_\varepsilon\}\), kde \(q_0, q_\varepsilon \notin Q_f\).
2. Zásobníková abeceda: \(G = G_f \cup \{Z_0\}\).

3. Přechodová funkce \(\delta\): Zobrazení \(\delta\) bude obsahovat všechny přechody původní funkce \(\delta_f\). Navíc přidáme následující přechody:

   • Inicializace zásobníku:

     \[\delta(q_0, \varepsilon, Z_0) = \{(q_f, Z_f Z_0)\}\]

     (Nový počáteční stav vloží na dno zásobníku nový symbol \(Z_0\) a původní počáteční symbol \(Z_f\), poté přejde do původního počátečního stavu \(q_f\).)

   • Přechod do mazacího stavu: Pro všechna \(q \in F_f\) (původní koncové stavy):

     \[\delta(q, \varepsilon, \varepsilon) = \delta_f(q, \varepsilon, \varepsilon) \cup \{(q_\varepsilon, \varepsilon)\}\]

     (Z koncového stavu můžeme kdykoliv přejít do stavu \(q_\varepsilon\).)

   • Vymazání zásobníku: Pro všechna \(\alpha \in G\):

     \[\delta(q_\varepsilon, \varepsilon, \alpha) = \{(q_\varepsilon, \varepsilon)\}\]

     (Ve stavu \(q_\varepsilon\) mažeme cokoliv, co je na zásobníku.)

4. Množina koncových stavů: \(F = \emptyset\).

---

(Převod ZA: Prázdný zásobník \(\to\) Koncový stav)

Převod ZA přijímajícího prázdným zásobníkem na ZA přijímající přechodem do koncového stavu

Tento převod vkládá na dno zásobníku speciální symbol. Pokud automat vyprázdní svůj původní zásobník, narazí na tento symbol, což mu umožní přejít do nového koncového stavu.

Vstup

Zásobníkový automat \(R_\varepsilon = (Q_\varepsilon, \Sigma, G_\varepsilon, \delta_\varepsilon, q_\varepsilon, Z_\varepsilon, F_\varepsilon)\). (Pozn.: \(F_\varepsilon\) je u automatu přijímajícího prázdným zásobníkem formálně irelevantní, často prázdná.)

Výstup

Zásobníkový automat \(R_f = (Q, \Sigma, G, \delta, q_0, Z_0, F)\), kde \(Z_0 \notin G_\varepsilon\), takový, že \(L(R_f) = L_\varepsilon(R_\varepsilon)\).

Postup

1. Množina stavů: \(Q = Q_\varepsilon \cup \{q_0, q_f\}\), kde \(q_0, q_f \notin Q_\varepsilon\).
2. Zásobníková abeceda: \(G = G_\varepsilon \cup \{Z_0\}\).

3. Přechodová funkce \(\delta\): Zobrazení \(\delta\) bude obsahovat všechny přechody původní funkce \(\delta_\varepsilon\). Navíc přidáme následující přechody:

   • Inicializace zásobníku:

     \[\delta(q_0, \varepsilon, Z_0) = \{(q_\varepsilon, Z_\varepsilon Z_0)\}\]

     (Nový počáteční stav vloží na dno zásobníku zarážku \(Z_0\) a nad ni původní počáteční symbol \(Z_\varepsilon\).)

   • Detekce prázdného zásobníku: Pro všechna \(q \in Q_\varepsilon\):

     \[\delta(q, \varepsilon, Z_0) = \{(q_f, \varepsilon)\}\]

     (Pokud automat narazí na dno zásobníku \(Z_0\), znamená to, že původní zásobník byl vyprázdněn. Přejdeme do koncového stavu \(q_f\).)

4. Množina koncových stavů: \(F = \{q_f\}\).