- Pushdown automatai yra būdas įdiegti CFG taip pat, kaip mes kuriame DFA įprastai gramatikai. DFA gali prisiminti ribotą informacijos kiekį, o PDA gali prisiminti begalinį informacijos kiekį.
- Pushdown automatai yra tiesiog NFA, papildyta „išorine kamino atmintimi“. Papildymas naudojamas siekiant užtikrinti, kad „Pushdown“ automatai būtų valdomi „paskutinis pirmas“. Pushdown automatai gali saugoti neribotą kiekį informacijos rietuvėje. Jis gali pasiekti ribotą kiekį informacijos apie krūvą. PDA gali nustumti elementą ant krūvos viršaus ir ištraukti elementą iš krūvos viršaus. Norint nuskaityti elementą į krūvą, viršutiniai elementai turi būti iššokti ir prarasti.
- PDA yra galingesnis nei FA. Bet kuri kalba, kurią gali priimti FA, gali būti priimtina ir PDA. PDA taip pat priima kalbos klasę, kurios net negali priimti FA. Taigi PDA yra daug pranašesnis už FA.
PDA komponentai:
Įvesties juosta: Įvesties juosta yra padalinta į daugybę langelių arba simbolių. Įvesties galvutė yra tik skaitoma ir gali judėti tik iš kairės į dešinę, po vieną simbolį.
Baigtas valdymas: Baigtinis valdiklis turi tam tikrą rodyklę, kuri nurodo dabartinį simbolį, kurį reikia perskaityti.
Stack: Krūva yra struktūra, kurioje galime stumti ir išimti daiktus tik iš vieno galo. Jis turi begalinį dydį. PDA dėklas naudojamas elementams laikinai saugoti.
Oficialus PDA apibrėžimas:
PDA galima apibrėžti kaip 7 komponentų rinkinį:
K: baigtinė būsenų rinkinys
∑: įvesties rinkinys
C: krūvos simbolis, kurį galima nustumti ir ištraukti iš krūvos
q0: pradinė būsena
npm švarios talpyklos jėga
SU: pradžios simbolis, esantis Γ.
F: galutinių būsenų rinkinys
d: atvaizdavimo funkcija, kuri naudojama pereinant iš dabartinės būsenos į kitą.
Momentinis aprašymas (ID)
ID yra neoficialus žymėjimas, kaip PDA apskaičiuoja įvesties eilutę ir priima sprendimą, ar eilutė bus priimta arba atmesta.
Momentinis aprašymas yra trigubas (q, w, α), kur:
q apibūdina dabartinę būseną.
Į aprašo likusią įvestį.
viršutinis indeksas iliustratoriuje
a aprašo krūvos turinį, viršuje kairėje.
Turniketo žymėjimas:
⊢ ženklas apibūdina turniketo užrašą ir reiškia vieną judesį.
⊢* ženklas apibūdina judesių seką.
Pavyzdžiui,
(p, b, T) ⊢ (q, w, α)
Aukščiau pateiktame pavyzdyje, pereinant iš būsenos p į q, sunaudojamas įvesties simbolis „b“, o krūvos „T“ viršus pavaizduotas nauja eilute α.
1 pavyzdys:
Sukurti PDA, kad būtų galima priimti kalbą anb2n.
Sprendimas: Šioje kalboje po n skaičiaus a turėtų sekti 2n skaičių b. Taigi taikysime labai paprastą logiką, tai yra, jei perskaitysime vieną „a“, mes įstumsime du a į krūvą. Kai tik perskaitome „b“, kiekvienam „b“ turėtų būti iškelta tik viena „a“ iš krūvos.
ID gali būti sudarytas taip:
δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa)
Dabar, kai skaitysime b, pakeisime būseną iš q0 į q1 ir pradėsime rodyti atitinkamą „a“. Vadinasi,
δ(q0, b, a) = (q1, ε)
Taigi šis „b“ iššokimo procesas bus kartojamas, nebent visi simboliai bus perskaityti. Atminkite, kad iššokantis veiksmas vyksta tik būsenoje q1.
terminalas kali linux
δ(q1, b, a) = (q1, ε)
Perskaičius visus b, visi atitinkami a turėtų būti iššokti. Taigi, kai skaitome ε kaip įvesties simbolį, krūvoje neturėtų būti nieko. Taigi žingsnis bus toks:
δ(q1, ε, Z) = (q2, ε)
Kur
PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})
ID galime apibendrinti taip:
δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) δ(q0, b, a) = (q1, ε) δ(q1, b, a) = (q1, ε) δ(q1, ε, Z) = (q2, ε)
Dabar mes modeliuosime šį PDA įvesties eilutei „aaabbbbbb“.
mysql skaičius
δ(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 pavyzdys:
Sukurkite PDA, kad būtų galima priimti 0 kalbąn1m0n.
Sprendimas: Šiame PDA po n skaičiaus 0 seka bet koks skaičius 1, po kurio eina n skaičius 0. Taigi tokio PDA projektavimo logika bus tokia:
Nustumkite visus 0 į krūvą, kai susidursite su pirmaisiais 0. Tada, jei perskaitysime 1, tiesiog nieko nedarykite. Tada perskaitykite 0 ir kiekvieną kartą perskaitykite 0, išmeskite vieną 0 iš krūvos.
Pavyzdžiui:
Šį scenarijų ID formoje galima parašyti taip:
δ(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)
Dabar mes modeliuosime šį PDA įvesties eilutei „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