• A lenyomó automaták a CFG megvalósításának egyik módja, ugyanúgy, ahogy a DFA-t egy normál nyelvtanhoz tervezzük. Egy DFA véges mennyiségű információra képes megjegyezni, de egy PDA végtelen mennyiségű információra képes megjegyezni.
• A lenyomó automaták egyszerűen egy NFA, amelyet „külső veremmemóriával” egészítenek ki. A verem hozzáadásával a Pushdown automaták „utoljára az elsőben” memóriakezelési képességet biztosítják. A lenyomó automaták korlátlan mennyiségű információt tárolhatnak a veremben. Korlátozott mennyiségű információhoz férhet hozzá a veremben. A PDA képes egy elemet a verem tetejére tolni, és kipattanni egy elemet a verem tetejéről. Ahhoz, hogy egy elemet beolvassunk a verembe, a felső elemeket le kell ugrani, és elvesznek.
• A PDA erősebb, mint az FA. Bármely nyelv, amelyet az FA elfogad, elfogadható lehet a PDA számára is. A PDA egy olyan nyelvosztályt is elfogad, amelyet még az FA sem fogad el. Így a PDA sokkal jobb, mint az FA.

PDA komponensek:

Bemeneti szalag: A bemeneti szalag sok cellára vagy szimbólumra van felosztva. A beviteli fej csak olvasható, és csak egy szimbólumot mozgathat balról jobbra.

Véges vezérlés: A véges vezérlőnek van néhány mutatója, amely az aktuális beolvasandó szimbólumra mutat.

Kazal: A verem egy olyan szerkezet, amelyben csak az egyik végéről tudjuk tolni és kivenni a tárgyakat. Mérete végtelen. A PDA-ban a verem az elemek ideiglenes tárolására szolgál.

A PDA hivatalos meghatározása:

A PDA 7 komponens gyűjteményeként határozható meg:

K: az állapotok véges halmaza

∑: a bemeneti készlet

C: egy verem szimbólum, amelyet el lehet tolni és ki lehet emelni a veremből

q0: a kezdeti állapot

autocad stretch parancs

VAL VEL: egy kezdő szimbólum, amely Γ-ben van.

F: végső állapotok halmaza

d: leképezési funkció, amely az aktuális állapotból a következő állapotba való átlépéshez használható.

Azonnali leírás (azonosító)

Az azonosító egy informális jelölés arra vonatkozóan, hogy a PDA hogyan számítja ki a bemeneti karakterláncot, és hogyan dönt a karakterlánc elfogadása vagy elutasítása mellett.

A pillanatnyi leírás egy hármas (q, w, α), ahol:

q az aktuális állapotot írja le.

Ban ben leírja a fennmaradó bemenetet.

katódsugárcsöves monitor

a leírja a verem tartalmát, bal felső sarokban.

Forgóajtó jelölése:

⊢ jel leírja a forgókapu jelölését és egy mozdulatot jelent.

⊢* jel egy mozdulatsort ír le.

Például,

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

react inline stílusban

A fenti példában a p állapotból a q-ba történő átmenet során a „b” bemeneti szimbólum felhasználásra kerül, és a „T” verem tetejét egy új α karakterlánc képviseli.

1. példa:

Nyelv fogadására alkalmas PDA tervezése aⁿb²ⁿ.

Megoldás: Ebben a nyelvben n számú a-t 2n számú b-nek kell követnie. Ezért egy nagyon egyszerű logikát fogunk alkalmazni, vagyis ha egyetlen 'a'-t olvasunk, akkor két a-t fogunk a verembe tolni. Amint elolvassuk a „b”-t, akkor minden egyes „b”-hez csak egy „a” kerüljön ki a veremből.

Az azonosító a következőképpen állítható fel:

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

Most, amikor olvassuk a b-t, az állapotot q0-ról q1-re változtatjuk, és elkezdjük a megfelelő 'a'-t. Ennélfogva,

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

Így a „b” felbukkanásának folyamata megismétlődik, hacsak nem olvassa el az összes szimbólumot. Vegye figyelembe, hogy a felbukkanó művelet csak q1 állapotban történik.

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

Az összes b kiolvasása után az összes megfelelő a-nak fel kell bukkannia. Ezért amikor ε-t olvasunk bemeneti szimbólumként, akkor semmi sem lehet a veremben. A lépés tehát a következő lesz:

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

Ahol

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

Az azonosítót így foglalhatjuk össze:

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

Most ezt a PDA-t szimuláljuk az „aaabbbbbb” bemeneti karakterlánchoz.

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

2. példa:

Tervezzen egy PDA-t a 0 nyelv fogadásáraⁿ1^m0ⁿ.

Megoldás: Ebben a PDA-ban n számú 0 után tetszőleges számú 1, majd n számú 0 követi. Ezért az ilyen PDA tervezésének logikája a következő lesz:

Ha az első 0-val találkozik, helyezze az összes 0-t a verembe. Aztán ha elolvassuk az 1-et, ne csináljunk semmit. Ezután olvassa el a 0-t, és a 0 minden leolvasásakor emeljen ki egy 0-t a veremből.

java egyenlő módszer

Például:

Ez a forgatókönyv a következőképpen írható be az azonosító űrlapba:

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

Most ezt a PDA-t szimuláljuk a „0011100” bemeneti karakterlánchoz.

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