Section: Pushdown AutomataCh. 7 - Pushdown AutomataADFA=(Q,Σ,δ,q0,F)head moves input tapetape headcurrent stateaab bab011Modify DFA by adding a stack. Newmachine is called PushdownAutomata (PDA).aabaaastackheadtapeinput tapecurrent stateba10Zhead moves 2Definition: Nondeterministic PDA(NPDA) is defined byM=(Q,Σ, Γ, δ, q0,z,F)whereQ is finite set of statesΣ is tape (input) alphabetΓ is stack alphabetq0is initial statez is start stack symbol (bottom of stack )F ⊆ Q is set of final states.δ:Q×(Σ ∪{λ})×Γ→ finite subsets of Q × Γ∗3Example of transitionsδ(q1,a,b) = {(q3,b),(q4,ab),(q6,λ)}The diagram for the above transitionsis:4Instantaneous Description:(q,w,u)Description of a Move:(q1,aw,bx) ` (q2,w,yx)iffDefinition Let M=(Q,Σ,Γ,δ,q0,z,F) bea NPDA. L(M)={w∈ Σ∗| (q0,w,z)∗`(p,λ,u), p∈F, u∈ Γ∗}. The NPDAaccepts all strings that start in q0andend in a final state.5Example: L={anbn|n ≥ 0}, Σ={a, b},Γ={z, a}6Another Definition for LanguageAcceptanceNPDA M accepts L(M) by emptystack:L(M)={w ∈ Σ∗|(q0,w,z)∗`(p, λ, λ)}7Example: L={wwR|w ∈ Σ+}, Σ={a, b},Γ={z, a, b}8Example: L={ww|w ∈ Σ∗}, Σ={a, b}9Examples for you to try on your own:(solutions are at the end of thehandout).• L={anbm|m>n,m,n>0},Σ={a, b},Γ={z, a}• L={anbn+mcm|n, m > 0}, Σ={a, b, c},• L={anb2n|n>0},Σ={a, b}10Theorem Given NPDA M thataccepts by final state, ∃ NPDA M’that accepts by empty stack s.t.L(M)=L(M’).• Proof (sketch)M=(Q,Σ,Γ,δ,q0,z,F)Construct M’=(Q’,Σ,Γ0,δ0,qs,z’,F’)11Theorem Given NPDA M thataccepts by empty stack, ∃ NPDA M’that accepts by final state.• Proof: (sketch)M=(Q,Σ,Γ,δ,q0,z,F)Construct M’=(Q’,Σ,Γ0,δ0,qs,z’,F’)12Theorem For any CFL L notcontaining λ, ∃ an NPDA M s.t.L=L(M).• Proof (sketch)Given (λ-free) CFL L.⇒∃CFG G such that L=L(G).⇒∃G’ in GNF, s.t. L(G)=L(G’).G’=(V,T,S,P). All productions in Pare of the form:13Example: Let G’=(V,T,S,P), P=S → aSA | aAA | bA → bBBBB → b14Theorem Given a NPDA M, ∃ aNPDA M’ s.t. all transitions have theform δ(qi,a,A)={c1,c2,...cn} whereci=(qj,λ)or ci=(qj,BC)Each move either increases ordecreases stack contents by a singlesymbol.• Proof (sketch)15Theorem If L=L(M) for some NPDAM, then L is a CFL.• Proof: Given NPDA M.First, construct an equivalentNPDA M that will be easier towork with. Construct M’ such that1. accepts if stack is empty2. each move increases or decreasesstack content by a single symbol.(can only push 2 variables or novariables with each transition)M’=(Q,Σ,Γ,δ,q0,z,F)Construct G=(V,Σ,S,P) whereV={(qicqj)|qi,qj∈Q, c ∈ Γ}Goal: (q0zqf) which will be thestart symbol in the grammar.16Example:L(M)={aa∗b},M=(Q,Σ,Γ,δ,q0,z,F),Q={q0,q1,q2,q3},Σ={a, b},Γ={A, z},F={}.45321q0q1q2a,z;Azb,A;,z;a,A;,z;Azλλλλλq317Construct the grammar G=(V,T,S,P),V={(q0Aq0), (q0zq0), (q0Aq1), (q0zq1),...}T=ΣS=(q0zq2)P=18From transition 1(q0Aq1) → bFrom transition 2(q1zq2) → λFrom transition 3(q0Aq3) → aFrom transition 4(q0zq0) → a(q0Aq0)(q0zq0)|a(q0Aq1)(q1zq0)|a(q0Aq2)(q2zq0)|a(q0Aq3)(q3zq0)(q0zq1) → a(q0Aq0)(q0zq1)|a(q0Aq1)(q1zq1)|a(q0Aq2)(q2zq1)|a(q0Aq3)(q3zq1)(q0zq2) → a(q0Aq0)(q0zq2)|a(q0Aq1)(q1zq2)|a(q0Aq2)(q2zq2)|a(q0Aq3)(q3zq2)(q0zq3) → a(q0Aq0)(q0zq3)|a(q0Aq1)(q1zq3)|a(q0Aq2)(q2zq3)|a(q0Aq3)(q3zq3)19From transition 5(q3zq0) → (q0Aq0)(q0zq0)|(q0Aq1)(q1zq0)|(q0Aq2)(q2zq0)|(q0Aq3)(q3zq0)(q3zq1) → (q0Aq0)(q0zq1)|(q0Aq1)(q1zq1)|(q0Aq2)(q2zq1)|(q0Aq3)(q3zq1)(q3zq2) → (q0Aq0)(q0zq2)|(q0Aq1)(q1zq2)|(q0Aq2)(q2zq2)|(q0Aq3)(q3zq2)(q3zq3) → (q0Aq0)(q0zq3)|(q0Aq1)(q1zq3)|(q0Aq2)(q2zq3)|(q0Aq3)(q3zq3)20Recognizing aaab in M:(q0, aaab, z) ` (q0, aab, Az)` (q3,ab,z)` (q0,ab,Az)` (q3,b,z)` (q0,b,Az)` (q1,λ,z)` (q2,λ,λ)Derivation of string aaab in G:(q0zq2) ⇒ a(q0Aq3)(q3zq2)⇒ aa(q3zq2)⇒ aa(q0Aq3)(q3zq2)⇒ aaa(q3zq2)⇒ aaa(q0Aq1)(q1zq2)⇒ aaab(q1zq2)⇒ aaab21Definition: A PDAM=(Q,Σ,Γ,δ,q0,z,F) is deterministic iffor every q ∈Q, a ∈ Σ ∪{λ}, b∈Γ1. δ(q, a, b) contains at most 1 element2. if δ(q, λ, b) 6= ∅ then δ(q, c, b)=∅ for allc ∈ ΣDefinition: L is DCFL iff ∃ DPDA Ms.t. L=L(M).Examples:1. Previous pda for {anbn|n ≥ 0} isdeterministic.2. Previous pda for{anbmcn+m|n, m > 0} is deterministic.3. Previous pda for{wwR|w ∈ Σ+},Σ={a, b} isnondeterministic.Note: There are CFL’s that are notdeterministic.22L={anbn|n ≥ 1}∪{anb2n|n≥1} is a CFLand not a DCFL.• Proof:L = {anbn: n ≥ 1}∪{anb2n:n≥1}It is easy to construct a NPDA for{anbn: n ≥ 1} and a NPDA for{anb2n: n ≥ 1}.Thesetwocanbejoined together by a new start stateand λ-transitions to create a NPDAforL.Thus,LisCFL.Now show L is not a DCFL.Assume that there is adeterministic PDA M such thatL = L(M). We will construct a PDAthat recognizes a language that isnot a CFL and derive acontradiction.Construct a PDA M0as follows:1. Create two copies of M: M1andM2. The same state in M1and M223are called cousins.2. Remove accept status fromaccept states in M1, removeinitial status from initial state inM2. In our new PDA, we willstart in M1and accept in M2.3. Outgoing arcs from old acceptstates in M1, change to end up inthe cousin of its destination inM2. This joins M1and M2intoone PDA. There must be anoutgoing arc since you mustrecognize both anbnand anb2n.After reading nb’s, must accept ifno more b’s and continue if thereare more b’s.4. Modify all transitions that read ab and have their destinations inM2to read a c.This is the construction of our newPDA.24When we read anbnand end up inan old accept state in M1, then wewill transfer to M2and read therest of anb2n. Only the b’s in M2have been replaced by c’s, so thenew machine accepts anbncn.The language accepted by our newPDA is anbncn. But this is not aCFL. Contradiction! Thus there isno deterministic PDA M such thatL(M)=L. Q.E.D.25Example: L={anbm|m>n,m,n>0},Σ={a, b}, Γ={z, a}q0q1q2q3a,z;aza,a;aab,a;b,a;b,z;zb,z;zλλExample: L={anbn+mcm|n, m > 0},Σ={a, b, c},a,z;aza,a;aab,z;bzb,b;bbq0 q1 q2q3b,a;b,a;c,b;q4q5,z;z c,b;Example: L={anb2n|n>0},Σ={a,