• Pushdown automāti ir veids, kā ieviest CFG tādā pašā veidā, kā mēs izstrādājam DFA parastajai gramatikai. DFA var atcerēties ierobežotu informācijas daudzumu, bet PDA var atcerēties bezgalīgu informācijas daudzumu.
• Pushdown automāti ir vienkārši NFA, kas papildināts ar 'ārējo steka atmiņu'. Kaudzītes pievienošana tiek izmantota, lai Pushdown automātiem nodrošinātu atmiņas pārvaldības iespējas pēdējā vietā. Pushdown automāti var uzglabāt neierobežotu informācijas daudzumu kaudzē. Tas var piekļūt ierobežotam informācijas apjomam par steku. PDA var nospiest elementu skursteņa augšpusē un izmest elementu no kaudzes augšdaļas. Lai elementu nolasītu kaudzē, augšējie elementi ir jānoņem un tie tiek zaudēti.
• PDA ir jaudīgāks par FA. Jebkura valoda, ko var pieņemt FA, var būt pieņemama arī PDA. PDA pieņem arī valodu klasi, ko FA pat nevar pieņemt. Tādējādi PDA ir daudz pārāka par FA.

PDA komponenti:

Ievades lente: Ievades lente ir sadalīta daudzās šūnās vai simbolos. Ievades galviņa ir tikai lasāma, un tā var pārvietoties tikai no kreisās puses uz labo, pa vienam simbolam.

Ierobežota kontrole: Galīgajai vadībai ir kāds rādītājs, kas norāda uz pašreizējo nolasāmo simbolu.

Kaudze: Kaudze ir struktūra, kurā mēs varam stumt un noņemt vienumus tikai no viena gala. Tam ir bezgalīgs izmērs. PDA steks tiek izmantots, lai īslaicīgi uzglabātu vienumus.

PDA formāla definīcija:

PDA var definēt kā 7 komponentu kolekciju:

J: ierobežotā stāvokļu kopa

∑: ievades komplekts

C: kaudzes simbols, kuru var nostumt un izmest no kaudzes

q0: sākotnējais stāvoklis

vb un vb tīkls

AR: sākuma simbols, kas ir Γ.

F: gala stāvokļu kopums

d: kartēšanas funkcija, ko izmanto, lai pārietu no pašreizējā stāvokļa uz nākamo stāvokli.

Tūlītējs apraksts (ID)

ID ir neformāls apzīmējums tam, kā PDA aprēķina ievades virkni un pieņem lēmumu, vai virkne tiek pieņemta vai noraidīta.

Momentānais apraksts ir trīskāršs (q, w, α), kur:

q apraksta pašreizējo stāvokli.

In apraksta atlikušo ievadi.

šķēle java masīvu

a apraksta kaudzes saturu, augšpusē pa kreisi.

Turniketa apzīmējums:

⊢ zīme apraksta turniketa apzīmējumu un apzīmē vienu kustību.

⊢* zīme apraksta kustību secību.

Piemēram,

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

saira banu aktieris

Iepriekš minētajā piemērā, veicot pāreju no stāvokļa p uz q, tiek patērēts ievades simbols “b”, un kaudzes “T” augšdaļa tiek attēlota ar jaunu virkni α.

1. piemērs:

Izstrādāt PDA valodu pieņemšanai aⁿb²ⁿ.

Risinājums: Šajā valodā n skaitam a ir jāseko 2n b skaitam. Tādējādi mēs pielietosim ļoti vienkāršu loģiku, proti, ja mēs lasām vienu “a”, mēs ievietosim divus a uz steku. Tiklīdz mēs izlasām “b”, katram atsevišķam “b” tikai viens “a” ir jāizņem no steka.

ID var izveidot šādi:

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

Tagad, kad mēs lasām b, mēs mainīsim stāvokli no q0 uz q1 un sāksim parādīt atbilstošo “a”. Tāpēc

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

Tādējādi šis “b” uzspiešanas process tiks atkārtots, ja vien netiks nolasīti visi simboli. Ņemiet vērā, ka uznirstošā darbība notiek tikai stāvoklī q1.

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

Pēc visu b nolasīšanas visiem atbilstošajiem a vajadzētu tikt parādītiem. Tādējādi, kad mēs lasām ε kā ievades simbolu, kaudzē nedrīkst būt nekā. Tādējādi kustība būs šāda:

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

Kur

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

Mēs varam apkopot ID šādi:

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

Tagad mēs simulēsim šo PDA ievades virknei '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 

2. piemērs:

Izstrādājiet plaukstdatoru, lai pieņemtu valodu 0ⁿ1^m0ⁿ.

Risinājums: Šajā PDA n skaitam 0 seko jebkurš skaits 1, kam seko n skaits 0. Tādējādi šāda PDA dizaina loģika būs šāda:

Nospiediet visus 0 uz kaudzītes, saskaroties ar pirmajiem 0. Tad, ja mēs lasām 1, vienkārši nedariet neko. Pēc tam nolasiet 0 un katrā nolasītajā 0 no steka izvelciet vienu 0.

skeneris nākamais

Piemēram:

Šo scenāriju ID formā var uzrakstīt šādi:

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

Tagad mēs simulēsim šo PDA ievades virknei '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