• Pushdown-automater är ett sätt att implementera en CFG på samma sätt som vi designar DFA för en vanlig grammatik. En DFA kan komma ihåg en ändlig mängd information, men en PDA kan komma ihåg en oändlig mängd information.
• Pushdown-automaten är helt enkelt en NFA utökad med ett 'externt stackminne'. Tillägget av stack används för att tillhandahålla en sista-in-först-ut minneshanteringskapacitet till Pushdown-automater. Pushdown-automater kan lagra en obegränsad mängd information i stacken. Den kan komma åt en begränsad mängd information på stacken. En handdator kan trycka in ett element på toppen av stacken och skjuta av ett element från toppen av stacken. För att läsa in ett element i stacken måste de översta elementen tas bort och gå förlorade.
• En handdator är kraftfullare än FA. Alla språk som kan accepteras av FA kan också accepteras av PDA. PDA accepterar också en språkklass som inte ens kan accepteras av FA. Således PDA är mycket mer överlägsen FA.

PDA-komponenter:

Inmatningsband: Inmatningsbandet är uppdelat i många celler eller symboler. Ingångshuvudet är skrivskyddat och kan bara flyttas från vänster till höger, en symbol i taget.

Ändlig kontroll: Den finita kontrollen har någon pekare som pekar på den aktuella symbolen som ska läsas.

Stack: Stapeln är en struktur där vi bara kan trycka och ta bort föremålen från ena änden. Den har en oändlig storlek. I PDA används stacken för att lagra föremålen tillfälligt.

Formell definition av PDA:

PDA kan definieras som en samling av 7 komponenter:

F: den ändliga uppsättningen av tillstånd

∑: ingångsuppsättningen

C: en stapelsymbol som kan skjutas och skjutas upp från stapeln

q0: initialtillståndet

java har nästa

MED: en startsymbol som är i Γ.

F: en uppsättning sluttillstånd

d: mappningsfunktion som används för att flytta från nuvarande tillstånd till nästa tillstånd.

Momentan beskrivning (ID)

ID är en informell notering av hur en PDA beräknar en indatasträng och fattar ett beslut om att strängen accepteras eller avvisas.

En momentan beskrivning är en trippel (q, w, α) där:

q beskriver det aktuella tillståndet.

I beskriver den återstående ingången.

bfs-sökning

a beskriver högens innehåll, överst till vänster.

Vändkorsnotation:

⊢-tecken beskriver vändkorset och representerar ett drag.

⊢*-tecknet beskriver en sekvens av drag.

Till exempel,

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

I exemplet ovan, medan man tar en övergång från tillstånd p till q, förbrukas ingångssymbolen 'b', och toppen av stacken 'T' representeras av en ny sträng α.

Exempel 1:

Designa en handdator för att acceptera ett språkⁿb²ⁿ.

Lösning: På det här språket ska n antal a:n följas av 2n antal b:n. Därför kommer vi att tillämpa en mycket enkel logik, och det är om vi läser enstaka 'a', kommer vi att trycka två a:n på stacken. Så fort vi läser 'b' så för varje enskilt 'b' bör bara ett 'a' komma från stapeln.

ID kan konstrueras enligt följande:

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

När vi nu läser b kommer vi att ändra tillståndet från q0 till q1 och börja poppa motsvarande 'a'. Därav,

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

Således kommer denna process att poppa 'b' att upprepas om inte alla symboler läses. Observera att popning endast sker i tillstånd q1.

något snabbt sortering

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

Efter att ha läst alla b:n bör alla motsvarande a:n bli poppade. När vi läser ε som ingångssymbol bör det därför inte finnas något i stacken. Därför blir flytten:

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

Var

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

Vi kan sammanfatta ID:t som:

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

Nu kommer vi att simulera denna PDA för inmatningssträngen 'aaabbbbbb'.

urval sortera i java

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

Exempel 2:

Designa en handdator för att acceptera ett språk 0ⁿ1^m0ⁿ.

Lösning: I denna PDA följs n antal nollor av valfritt antal 1:or följt av n antal nollor. Därför kommer logiken för designen av en sådan handdator att vara följande:

Tryck alla nollor på högen när du möter första nollor. Om vi ​​sedan läser 1, gör bara ingenting. Läs sedan 0, och vid varje läsning av 0, tryck en 0 från stacken.

Till exempel:

Detta scenario kan skrivas i ID-formuläret 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) 

Nu kommer vi att simulera denna PDA för ingångssträngen '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