Zásobníkový automat: Porovnání verzí

Zásobníkový automat (PDA z anglického pushdown automaton) je teoretický výpočetní model používaný v informatice pro studium vyčíslitelnosti a obecně formálních jazyků. Popisuje jednoduchý počítač, který má jako pracovní paměť vedle konečně stavové jednotky k dispozici zásobník. Zásobníkový automat dokáže rozpoznávat bezkontextové jazyky.

Formální definice

Formálně je zásobníkový automat definován jako uspořádaná sedmice (Q, T, G, δ, q₀, z₀, F ), kde:

• Q je konečná množina vnitřních stavů,
• T je konečná vstupní abeceda,
• G je konečná abeceda zásobníku,
• δ (značeno řeckým písmenem delta) je tzv. přechodová relace, popisující pravidla činnosti automatu (jeho program), je definována jako konečná podmnožina kartézského součinu Q× (T ∪ {ε}) × G × Q × G*,
• q₀ je počáteční stav,
• Z₀ popisuje symboly uložené na počátku v zásobníku,
• F je množina přijímajících stavů, F ⊆ Q.

Prvek (q₁, a, z₁, q₂, η) přechodové relace znamená, že automat v situaci, kdy řídicí jednotka je ve stavu q₁, na vstupu je symbol a a na vrcholu zásobníku symbol z₁, může změnit vnitřní stav na q₂, načíst jeden symbol ze vstupu, vybrat jeden symbol z vrcholu zásobníku a místo něj na zásobník uložit řetězec η.

Prvek (q₁, ε, z₁, q₂, η) přechodové relace znamená, že automat v situaci, kdy řídicí jednotka je ve stavu q₁ a na vrcholu zásobníku symbol z₁ (na vstupním symbolu nezáleží), může změnit vnitřní stav na q₂, vybrat jeden symbol z vrcholu zásobníku a místo něj na zásobník uložit řetězec η (tak zvaný ε-pohyb).

Je vidět, že zásobníkový automat se v podstatě skládá z konečného automatu, který má navíc k dispozici potenciálně nekonečné množství paměti ve formě zásobníku. Obsah tohoto zásobníku ovlivňuje činnost automatu tím, že vstupuje jako jeden z parametrů do přechodové funkce.

Popis činnosti automatu

Na počátku se automat nachází v definovaném počátečním stavu a zásobník obsahuje pouze počáteční symbol. Dále v každém kroku podle aktuálního stavu, symbolů na vrcholu zásobníku a symbolu na vstupu provede přechod, při kterém vyjme ze zásobníku vrchní symbol, vloží místo něj jiné a ze vstupu přečte další symbol. Toto se opakuje.

Po dokončení činnosti (po přečtení celého vstupu, pokud do té doby nedojde k chybě) je rozhodnuto, jestli automat vstupní řetězec přijal. K tomu mohou sloužit dvě kritéria:

• stav, ve kterém se na konci automat nachází, patří do množiny přijímajících stavů, nebo
• zásobník je na konci prázdný.

Obě definice jsou ekvivalentní, automaty na sebe lze vzájemně převádět (u druhé možnosti je možno z definice automatu zcela vypustit množinu přijímajících stavů).

Ukázka činnosti

Jako příklad je možno ukázat následující zásobníkový automat:

Q = {q}

T = {a, b, c}

G = {A}

δ = {

(q, a, ε) → (q, A),

(q, b, ε) → (q, ε),

(q, c, A) → (q, ε),

}

q₀ = q

Z₀ = ε

Tento automat rozhoduje o přijetí tím, že po přečtení vstupu je zásobník prázdný, nejsou zde tedy přijímající stavy. Řekněme, že na vstupu je řetězec baabcbacc. Na počátku je automat ve stavu q (ostatně jako neustále, tento automat má pouze jeden stav, viz též níže), zásobník je prázdný (což se značí symbolem prázdného řetězce ε) a na vstupu zbývá celý řetězec, baabcbacc; tuto konfiguraci označíme jako (q, baabcbacc, ε). Z přechodové funkce je vidět, že ve stavu q při přečtení vstupu b se ze zásobníku nečte žádný symbol (ε), „přejde“ se do stavu q a na zásobník se nic neukládá (opět ε). Automat je tedy poté v konfiguraci (q, aabcbacc, ε) – jediná změna spočívá v přečtení symbolu b ze vstupu. Teď se má přečíst symbol a, z přechodové funkce je vidět, že se má na zásobník uložit symbol A. Automat tedy pokračuje konfigurací (q, abcbacc, A), dále následují konfigurace (q, bcbacc, AA), (q, cbacc, AA), (q, bacc, A), (q, acc, A), (q, cc, AA), (q, c, A), (q, ε, ε), vstup byl celý přečten, automat skončil ve stavu s prázdným zásobníkem, řetězec baabcbacc tedy byl přijat, patří do jazyka, který tento automat rozpoznává.

Pro úplnost: tento automat rozpoznává jazyk závorkových struktur, kde symbol a představuje otevírací závorku a symbol c zavírací závorku (symbol b je nevýznamný). Vstupní řetězec odpovídá řetězci x((x)x()), ve kterém jsou závorky správně párovány.

Další zadání:
L={aⁿbⁿ|n≥1}
Jedná se tedy o slova, která mají stejný počet znaků a na začátku, jako znaků b na konci.

Řešení:
(r1, a, Z) → (r1,A)
(r1, a,A) → (r1,AA)
(r1, b,A) → (r2, ε)
(r2, b,A) → (r2, ε)

Výpočet výše uvedeného zásobníkového automatu na vstupním slově aaabbb lze zapsat takto:
(r1, aaabbb, Z) ⊢ (r1, aabbb,A) ⊢ (r1, abbb,AA) ⊢ (r1, bbb,AAA) ⊢ (r2, bb,AA) ⊢ (r2, b,A) ⊢ (r2, ε, ε)

Výpočet je tedy posloupnost konfigurací, kde každá jednotlivá konfigurace zachycuje
• (aktuální) stav řídicí jednotky,
• obsah vstupní pásky, který zbývá přečíst,
• obsah zásobníku (zapsaný jako řetězec symbolů; nejlevější symbol od- povídá vrcholu zásobníku).

Síla modelu

Nejdůležitější částí zásobníkového automatu je jeho paměť, zásobník, samotný konečný automat bez zásobníku dokáže rozpoznávat pouze regulární jazyky. Jak je vidět z předešlého příkladu, „vnitřní“ konečný automat může být velice jednoduchý, dokonce s jediným stavem – důležitější částí je zásobník, který umožňuje automatu rozpoznávat bezkontextové jazyky.

Jelikož se tedy přidáním zásobníku rozšíří třída jazyků, které automat umí detekovat, nabízí se otázka, zda by se téhož nedosáhlo přidáním dalšího zásobníku. A skutečně, zásobníkový automat se dvěma zásobníky má výpočetní sílu ekvivalentní Turingovu stroji, neboť jedním zásobníkem může emulovat část pásky vlevo od polohy hlavy, druhým zásobníkem pak část pásky vpravo od hlavy. (Dalším přidáváním zásobníků už evidentně výpočetní síla neroste.)

Deterministický zásobníkový automat

Deterministický zásobníkový automat je zásobníkový automat, u něhož existuje v každé situaci nejvýše jedna instrukce, kterou může provést. Formálně:

1. Jestliže (q₁, a, z₁, q₂, η) ∈ δ a (q₁, a, z₁, q' ₂, η') ∈ δ, pak q₂ = q' ₂ a η' = η.
2. Jestliže (q₁, ε, z₁, q₂, η) ∈ δ, pak neexistuje žádné a, tak že (q₁, a, z₁, q'₂, η' ) ∈ δ.

První podmínka říká, že pro situaci danou trojicí (q₁, a, z₁) existuje nejvýše jedna instrukce, druhá podmínka, že v situaci, kdy je možné provést ε-pohyb, není možné provést načtení znaku ze vstupu. První podmínku je možné formulovat i tak, že místo přechodové relace má automat přechodovou funkci δ: (Q× (T ∪ {ε}) × G) → (Q × G*).

Rozpoznávací síla deterministického zásobníkového automatu závisí na tom, jaké kritérium používáme pro přijetí řetězce. V obou případech je rozpoznávací síla nižší než u nedeterministického zásobníkového automatu. Při přijímání koncovým (přijímajícím) stavem deterministický automat přijímá tak zvané deterministické jazyky, které jsou vlastní podmnožinou bezkontextových jazyků. Například bezkontextový jazyk L = { aⁿbⁿc^m | n, m ∈ N } ∪ { aⁿb^mcⁿ | n, m ∈ N } není deterministický.

Při přijímání prázdným zásobníkem automat rozpoznává třídu bezprefixových bezkontextových jazyků, která nepokrývá ani všechny regulární jazyky. Například jazyk L = { a, aa } není deterministickým zásobníkovým automatem prázdným zásobníkem rozpoznatelný. V praxi však toto omezení není významné, pokud máme informaci o konci řetězce (souboru, apod.). Výše uvedený jazyk se pak změní na L = { a$, aa$ } (kde $ je znak konce řetězce), který deterministickým zásobníkovým automatem prázdným zásobníkem rozpoznáván je.

Zásobníkový překladový automat

Je uspořádaná osmice:

• Q je konečná množina vnitřních stavů,
• T je konečná vstupní abeceda,
• D je konečná abeceda výstupních symbolů,
• G je konečná abeceda zásobníku,
• δ přechodová funkce, popisující pravidla činnosti automatu, je definována jako zobrazení z Q×(T ∪ {ε})×G* do Q×G*×D*,
• q₀ je počáteční stav,
• Z₀ popisuje symboly uložené na počátku v zásobníku,
• F je množina přijímajících stavů, F ⊆ Q.

Konfigurace ZPA je čtveřice $(q,x,\mathrm{\alpha <!--\; \alpha \; -->},y)\in <!--\; \in \; -->Q\times <!--\; \times \; -->T^{\ast <!--\; \ast \; -->}\times <!--\; \times \; -->G^{\ast <!--\; \ast \; -->}\times <!--\; \times \; -->D^{\ast <!--\; \ast \; -->}$, teda konfigurace má určitý stav, řetězec na vstupu, řetězec v zásobníku a řetězec na výstupu, respektive.

Související články

• Zásobníkový počítač
• Konečný automat
• Bezkontextový jazyk
• Turingův stroj