- Pushdown-automater er en måte å implementere en CFG på på samme måte som vi designer DFA for en vanlig grammatikk. En DFA kan huske en begrenset mengde informasjon, men en PDA kan huske en uendelig mengde informasjon.
- Pushdown-automater er ganske enkelt en NFA utvidet med et 'eksternt stabelminne'. Tillegget av stack brukes til å gi en siste-inn-først-ut-minneadministrasjonsfunksjon til Pushdown-automater. Pushdown-automater kan lagre en ubegrenset mengde informasjon på stabelen. Den kan få tilgang til en begrenset mengde informasjon på stabelen. En PDA kan skyve et element på toppen av stabelen og sprette av et element fra toppen av stabelen. For å lese et element inn i stabelen, må de øverste elementene fjernes og gå tapt.
- En PDA er kraftigere enn FA. Ethvert språk som kan aksepteres av FA kan også aksepteres av PDA. PDA aksepterer også en språkklasse som til og med ikke kan aksepteres av FA. Dermed er PDA mye mer overlegen FA.
PDA-komponenter:
Inndatabånd: Inndatabåndet er delt inn i mange celler eller symboler. Inndatahodet er skrivebeskyttet og kan bare bevege seg fra venstre til høyre, ett symbol om gangen.
Endelig kontroll: Den endelige kontrollen har en peker som peker på det gjeldende symbolet som skal leses.
Stable: Stabelen er en struktur der vi bare kan skyve og fjerne gjenstandene fra den ene enden. Den har en uendelig størrelse. I PDA brukes stabelen til å lagre varene midlertidig.
Formell definisjon av PDA:
PDA kan defineres som en samling av 7 komponenter:
Q: det endelige settet av tilstander
∑: inngangssettet
C: et stabelsymbol som kan skyves og sprettes fra stabelen
q0: den opprinnelige tilstanden
gimp lagring som jpeg
MED: et startsymbol som er i Γ.
F: et sett med slutttilstander
d: kartfunksjon som brukes for å flytte fra gjeldende tilstand til neste tilstand.
Øyeblikkelig beskrivelse (ID)
ID er en uformell notasjon av hvordan en PDA beregner en inndatastreng og tar en beslutning om at strengen aksepteres eller avvises.
En øyeblikkelig beskrivelse er en trippel (q, w, α) hvor:
q beskriver den nåværende tilstanden.
I beskriver de resterende innspillene.
lykke til
en beskriver stabelens innhold, øverst til venstre.
Turnstile-notasjon:
⊢-tegnet beskriver turnstile-notasjonen og representerer ett trekk.
⊢* tegnet beskriver en sekvens av trekk.
For eksempel,
(p, b, T) ⊢ (q, w, α)
I eksemplet ovenfor, mens du tar en overgang fra tilstand p til q, blir inngangssymbolet 'b' konsumert, og toppen av stabelen 'T' er representert av en ny streng α.
Eksempel 1:
Design en PDA for å akseptere et språknb2n.
Løsning: På dette språket skal n antall a-er etterfølges av 2n antall b-er. Derfor vil vi bruke en veldig enkel logikk, og det er at hvis vi leser enkelt 'a', vil vi skyve to a-er på stabelen. Så snart vi leser 'b' så for hver enkelt 'b' bør bare en 'a' komme ut av stabelen.
ID kan konstrueres som følger:
δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa)
Når vi nå leser b, vil vi endre tilstanden fra q0 til q1 og begynne å sprette tilsvarende 'a'. Derfor,
δ(q0, b, a) = (q1, ε)
Dermed vil denne prosessen med å poppe 'b' bli gjentatt med mindre alle symbolene er lest. Vær oppmerksom på at sprett-handling kun forekommer i tilstand q1.
solfylt deol
δ(q1, b, a) = (q1, ε)
Etter å ha lest alle b-ene, bør alle de tilsvarende a-ene bli spratt. Når vi leser ε som inngangssymbol, bør det derfor ikke være noe i stabelen. Derfor blir flyttingen:
δ(q1, ε, Z) = (q2, ε)
Hvor
PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})
Vi kan oppsummere ID-en som:
δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) δ(q0, b, a) = (q1, ε) δ(q1, b, a) = (q1, ε) δ(q1, ε, Z) = (q2, ε)
Nå skal vi simulere denne PDAen for inngangsstrengen 'aaabbbbbb'.
10 av 50,00
δ(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
Eksempel 2:
Design en PDA for å akseptere et språk 0n1m0n.
Løsning: I denne PDAen blir n antall 0-er etterfulgt av et hvilket som helst antall 1-er etterfulgt av n antall 0-er. Derfor vil logikken for utformingen av en slik PDA være som følger:
Skyv alle 0-ene på stabelen når du møter de første 0-ene. Så hvis vi leser 1, bare gjør ingenting. Les deretter 0, og for hver lesning av 0, stikk en 0 fra stabelen.
For eksempel:
Dette scenariet kan skrives i ID-skjemaet som:
δ(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)
Nå vil vi simulere denne PDAen for inngangsstrengen '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