TechCodeview

• Zásobné automaty predstavujú spôsob implementácie CFG rovnakým spôsobom, akým navrhujeme DFA pre bežnú gramatiku. DFA si dokáže zapamätať obmedzené množstvo informácií, ale PDA si môže zapamätať nekonečné množstvo informácií.
• Zásobné automaty sú jednoducho NFA rozšírené o „externú zásobníkovú pamäť“. Pridanie zásobníka sa používa na poskytnutie možnosti správy pamäte typu posledný dnu, prvý von pre zásobníkové automaty. Zásobné automaty môžu na zásobník uložiť neobmedzené množstvo informácií. Má prístup k obmedzenému množstvu informácií v zásobníku. PDA môže zatlačiť prvok na hornú časť stohu a vysunúť prvok z vrchu stohu. Ak chcete načítať prvok do zásobníka, horné prvky musia byť odstránené a stratené.
• PDA je výkonnejší ako FA. Akýkoľvek jazyk, ktorý môže byť prijateľný pre FA, môže byť prijateľný aj pre PDA. PDA akceptuje aj triedu jazykov, ktorú nemôže akceptovať ani FA. PDA je teda oveľa lepšie ako FA.

Komponenty PDA:

Vstupná páska: Vstupná páska je rozdelená do mnohých buniek alebo symbolov. Vstupná hlava je len na čítanie a môže sa pohybovať len zľava doprava, vždy po jednom symbole.

Konečné ovládanie: Konečný ovládač má nejaký ukazovateľ, ktorý ukazuje aktuálny symbol, ktorý sa má čítať.

Stoh: Stoh je štruktúra, v ktorej môžeme tlačiť a odstraňovať predmety iba z jedného konca. Má nekonečnú veľkosť. V PDA sa zásobník používa na dočasné uloženie položiek.

Formálna definícia PDA:

PDA možno definovať ako súbor 7 komponentov:

Otázka: konečná množina stavov

∑: vstupná sada

C: symbol stohu, ktorý možno stlačiť a vytiahnuť zo stohu

q0: počiatočný stav

java dátum teraz

S: štartovací symbol, ktorý je v Γ.

F: súbor konečných stavov

d: mapovacia funkcia, ktorá sa používa na prechod z aktuálneho stavu do nasledujúceho.

Okamžitý popis (ID)

ID je neformálny zápis toho, ako PDA vypočítava vstupný reťazec a rozhoduje, či reťazec prijme alebo zamietne.

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

q popisuje súčasný stav.

In popisuje zostávajúci vstup.

binárny strom inorder traversal

a popisuje obsah zásobníka, vľavo hore.

Zápis turniketu:

⊢ znak popisuje notáciu turniketu a predstavuje jeden ťah.

Znak ⊢* popisuje postupnosť ťahov.

Napríklad,

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

linux ako premenovať adresár

Vo vyššie uvedenom príklade sa pri prechode zo stavu p do stavu q spotrebuje vstupný symbol 'b' a vrchol zásobníka 'T' je reprezentovaný novým reťazcom α.

Príklad 1:

Navrhnite PDA na akceptovanie jazyka aⁿb²ⁿ.

Riešenie: V tomto jazyku by po n číslach a malo nasledovať 2n počtu b. Preto použijeme veľmi jednoduchú logiku, a to, že ak čítame jediné 'a', vytlačíme dve a do zásobníka. Akonáhle prečítame 'b', potom pre každé jedno 'b' by malo zo zásobníka vypadnúť iba jedno 'a'.

ID možno zostaviť takto:

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

Teraz, keď čítame b, zmeníme stav z q0 na q1 a začneme objavovať zodpovedajúce 'a'. teda

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

Takže tento proces vyskakovania 'b' sa bude opakovať, pokiaľ sa neprečítajú všetky symboly. Všimnite si, že akcia prasknutia sa vyskytuje iba v stave q1.

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

Po prečítaní všetkých b by sa mali objaviť všetky zodpovedajúce a. Keď teda čítame ε ako vstupný symbol, v zásobníku by nemalo byť nič. Pohyb teda bude:

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

Kde

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

ID môžeme zhrnúť takto:

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

Teraz budeme simulovať toto PDA pre vstupný reťazec 'aaabbbbbb'.

 δ(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 

Príklad 2:

Navrhnite PDA na akceptovanie jazyka 0ⁿ1^m0ⁿ.

Riešenie: V tomto PDA po n číslach 0 nasleduje ľubovoľný počet 1 nasledovaných n číslami 0. Logika návrhu takéhoto PDA bude teda nasledovná:

Pri stretnutí s prvými nulami zatlačte všetky 0 do zásobníka. Potom, ak čítame 1, nerobte nič. Potom prečítajte 0 a pri každom prečítaní 0 vyberte jednu 0 zo zásobníka.

inštancia v jazyku Java

Napríklad:

Tento scenár môže byť napísaný vo forme ID ako:

 δ(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) 

Teraz budeme simulovať toto PDA pre vstupný reťazec '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