• Zásobníkové automaty představují způsob, jak implementovat CFG stejným způsobem, jakým navrhujeme DFA pro běžnou gramatiku. DFA si může zapamatovat omezené množství informací, ale PDA si může zapamatovat nekonečné množství informací.
• Zásobníkové automaty jsou jednoduše NFA rozšířené o „externí zásobníkovou paměť“. Přidání zásobníku se používá k poskytnutí schopnosti správy paměti typu last-in-first-out pro zásobníkové automaty. Zásobníkové automaty mohou do zásobníku uložit neomezené množství informací. Má přístup k omezenému množství informací v zásobníku. PDA může zatlačit prvek na horní část stohu a vysunout prvek z horní části stohu. Chcete-li načíst prvek do zásobníku, musí být horní prvky odstraněny a jsou ztraceny.
• PDA je výkonnější než FA. Jakýkoli jazyk, který může být přijatelný pro FA, může být také přijatelný pro PDA. PDA také akceptuje třídu jazyků, kterou nemůže přijmout ani FA. PDA je tedy mnohem lepší než FA.

Komponenty PDA:

Vstupní páska: Vstupní páska je rozdělena do mnoha buněk nebo symbolů. Vstupní hlava je pouze pro čtení a může se pohybovat pouze zleva doprava po jednom symbolu.

Konečné ovládání: Konečný ovládací prvek má nějaký ukazatel, který ukazuje aktuální symbol, který se má číst.

Zásobník: Zásobník je struktura, ve které můžeme tlačit a odebírat položky pouze z jednoho konce. Má nekonečnou velikost. V PDA se zásobník používá k dočasnému uložení položek.

Formální definice PDA:

PDA lze definovat jako soubor 7 komponent:

Q: konečná množina stavů

∑: vstupní sadu

C: symbol zásobníku, který lze vytlačit a vytáhnout ze zásobníku

q0: výchozí stav

seznam písem v gimpu

S: počáteční symbol, který je v Γ.

F: soubor konečných stavů

d: mapovací funkce, která se používá pro přechod z aktuálního stavu do dalšího stavu.

Okamžitý popis (ID)

ID je neformální zápis toho, jak PDA počítá vstupní řetězec a rozhoduje, zda je řetězec přijat nebo odmítnut.

Okamžitý popis je trojice (q, w, α), kde:

q popisuje aktuální stav.

v popisuje zbývající vstup.

bubble sort java

A popisuje obsah zásobníku, vlevo nahoře.

Zápis turniketu:

⊢ znak popisuje notaci turniketu a představuje jeden pohyb.

Znak ⊢* popisuje sekvenci tahů.

Například,

(p, b, T) ⊢ (q, w, α)

Ve výše uvedeném příkladu je při přechodu ze stavu p do q spotřebován vstupní symbol 'b' a vrchol zásobníku 'T' je reprezentován novým řetězcem α.

Příklad 1:

Navrhněte PDA pro akceptaci jazyka aⁿb²ⁿ.

Řešení: V tomto jazyce by za n číslem a mělo následovat 2n počtem b. Proto použijeme velmi jednoduchou logiku, a to, že pokud čteme jediné 'a', vytlačíme dvě a do zásobníku. Jakmile čteme 'b', pak pro každé jedno 'b' by se mělo ze zásobníku vytáhnout pouze jedno 'a'.

ID lze sestavit následovně:

 δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) 

Nyní, když čteme b, změníme stav z q0 na q1 a začneme objevovat odpovídající 'a'. Proto,

 δ(q0, b, a) = (q1, ε) 

Tento proces vyskakování 'b' se tedy bude opakovat, dokud nebudou přečteny všechny symboly. Všimněte si, že k akci praskání dochází pouze ve stavu q1.

25 c až k

 δ(q1, b, a) = (q1, ε) 

Po přečtení všech b by se měla objevit všechna odpovídající a. Když tedy čteme ε jako vstupní symbol, pak by v zásobníku nemělo být nic. Přesun tedy bude:

 δ(q1, ε, Z) = (q2, ε) 

Kde

PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})

ID můžeme shrnout takto:

 δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) δ(q0, b, a) = (q1, ε) δ(q1, b, a) = (q1, ε) δ(q1, ε, Z) = (q2, ε) 

Nyní budeme simulovat toto PDA pro vstupní řetězec 'aaabbbbbb'.

vypněte režim vývojáře

 δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ) ⊢ δ(q0, abbbbbb, aaaaZ) ⊢ δ(q0, bbbbbb, aaaaaaZ) ⊢ δ(q1, bbbbb, aaaaaZ) ⊢ δ(q1, bbbb, aaaaZ) ⊢ δ(q1, bbb, aaaZ) ⊢ δ(q1, bb, aaZ) ⊢ δ(q1, b, aZ) ⊢ δ(q1, ε, Z) ⊢ δ(q2, ε) ACCEPT 

Příklad 2:

Navrhněte PDA pro akceptování jazyka 0ⁿ1^m0ⁿ.

Řešení: V tomto PDA je n čísel 0 následováno libovolným počtem jedniček následovaných n počtem nul. Logika návrhu takového PDA bude tedy následující:

Při setkání s prvními nulami zatlačte všechny 0 do zásobníku. Pak když čteme 1, prostě nedělej nic. Poté přečtěte 0 a při každém čtení 0 vyjměte jednu 0 ze zásobníku.

Například:

Tento scénář lze zapsat ve formě ID jako:

 δ(q0, 0, Z) = δ(q0, 0Z) δ(q0, 0, 0) = δ(q0, 00) δ(q0, 1, 0) = δ(q1, 0) δ(q0, 1, 0) = δ(q1, 0) δ(q1, 0, 0) = δ(q1, ε) δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state) 

Nyní budeme simulovat toto PDA pro vstupní řetězec '0011100'.

 δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z) ⊢ δ(q0, 11100, 00Z) ⊢ δ(q0, 1100, 00Z) ⊢ δ(q1, 100, 00Z) ⊢ δ(q1, 00, 00Z) ⊢ δ(q1, 0, 0Z) ⊢ δ(q1, ε, Z) ⊢ δ(q2, Z) ACCEPT