Zásobníkový automat

Z Wikipedie, otevřené encyklopedie

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ěť k dispozici pouze zásobník. Zásobníkový automat dokáže rozpoznávat bezkontextové jazyky.

[editovat] Formální definice

Formálně je zásobníkový automat definován jako uspořádaná sedmice $\left(Q, T, G, \delta, q_0, z_0, F \right)$ , 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,
δ je tzv. přechodová funkce, popisující pravidla činnosti automatu (jeho program), je definována jako zobrazení z Q×(T ∪ {ε})×G* do 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.

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.

[editovat] 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í symboly. 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 může vyjmout ze zásobníku několik symbolů, vložit místo nich jiné a na vstupu přečíst 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ů).

[editovat] 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, A, ABCBACC), dále následují konfigurace (q, AA, BCBACC), (q, AA, CBACC), (q, A, BACC), (q, A, ACC), (q, AA, CC), (q, A, C), (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.

[editovat] 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.)