Unformatted text preview:

CPS 140 - Mathematical Foundations of CSDr. S. RodgerSection: Pushdown Automata (Ch. 7) (handout)Ch. 7 - Pushdown AutomataA DFA=(Q,Σ,δ,q0,F)head moves input tapetape headcurrent stateaab bab01Modify DFA by adding a stack. New machine is called Pushdown Automata (PDA).aabaaastackheadtapeinput tapecurrent stateba10Zhead moves Definition: Nondeterministic PDA (NPDA) is defined byM=(Q,Σ, Γ, δ, q0,z,F)where1Q is finite set of statesΣ is tape (input) alphabetΓ is stack alphabetq0is initial statez is start stack symbol (bottom of stack marker)F ⊆ Q is set of final states.δ:Q×(Σ ∪{λ})×Γ→finite subsets of Q × Γ∗Example of transitionsδ(q1,a,b) = {(q3,b),(q4,ab),(q6,λ)}Meaning: If in state q1with “a” the current tape symbol and “b” the symbol on top of the stack, then pop“b”, and eithermove to q3and push “b” on stackmove to q4and push “ab” on stack (“a” on top)move to q6Transitions can be represented using a transition diagram.The diagram for the above transitions is:Each arc is labeled by a triple: x,y;z where x is the current input symbol, y is the top of stack symbolwhich is popped from the stack, and z is a string that is pushed onto the stack.Instantaneous Description:(q,w,u)Notation to describe the current state of the machine (q), unread portion of the input string (w), and thecurrent contents of the stack (u).2Description of a Move:(q1,aw,bx) ` (q2,w,yx)iffDefinition Let M=(Q,Σ,Γ,δ,q0,z,F) be a NPDA. L(M)={w∈ Σ∗| (q0,w,z)∗` (p,λ,u), p∈F, u∈ Γ∗}.TheNPDA accepts all strings that start in q0and end in a final state.Example: L={anbn|n ≥ 0},Σ={a, b},Γ={z, a}Another Definition for Language AcceptanceNPDA M accepts L(M) by empty stack:L(M)={w ∈ Σ∗|(q0,w,z)∗`(p, λ, λ)}3Example: L={wwR|w ∈ Σ+},Σ={a, b},Γ={z, a, b}Example: L={ww|w ∈ Σ∗},Σ={a, b}Examples for you to try on your own: (solutions are at the end of the handout).• 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}4Theorem Given NPDA M that accepts 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’)Theorem Given NPDA M that accepts 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’)5Theorem For any CFL L not containing λ, ∃ 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 P are of the form:6Example: Let G’=(V,T,S,P), P=S → aSA | aAA | bA → bBBBB → b7Theorem Given a NPDA M, ∃ a NPDA M’ s.t. all transitions have the form δ(qi,a,A)={c1,c2,...cn}whereci=(qj,λ)or ci=(qj,BC)Each move either increases or decreases stack contents by a single symbol.• Proof (sketch)8Theorem If L=L(M) for some NPDA M, then L is a CFL.• Proof: Given NPDA M.First, construct an equivalent NPDA M that will be easier to work with. Construct M’ such that1. accepts if stack is empty2. each move increases or decreases stack content by a single symbol. (can only push 2 variables orno variables with each transition)M’=(Q,Σ,Γ,δ,q0,z,F)Construct G=(V,Σ,S,P) whereV={(qicqj)|qi,qj∈Q, c ∈ Γ}(qicqj) represents “starting at state qithe stack contents are cw, w ∈ Γ∗, some path is followed tostate qjand the contents of the stack are now w”.Goal: (q0zqf) which will be the start symbol in the grammar.Meaning: We start in state q0with z on the stack and process the input tape. Eventually we willreach the final state qfand the stack will be empty. (Along the way we may push symbols on thestack, but these symbols will be popped from the stack).9.10Example:L(M)={aa∗b}, M=(Q,Σ,Γ,δ,q0,z,F), Q={q0,q1,q2,q3},Σ={a, b},Γ={A, z},F={}. M accepts by emptystack.45321q0q1q2a,z;Azb,A;,z;a,A;,z;Azλλλλλq3Construct the grammar G=(V,T,S,P),V={(q0Aq0), (q0zq0),(q0Aq1), (q0zq1),...}T=ΣS=(q0zq2)11P=From 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)From 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)Recognizing 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)⇒ aaab12Definition: A PDA M=(Q,Σ,Γ,δ,q0,z,F) is deterministic if for every q ∈Q, a ∈ Σ ∪{λ},b∈Γ1. δ(q, a, b) contains at most 1 element2. if δ(q, λ, b) 6= ∅ then δ(q, c, b)=∅ for all c ∈ ΣDefinition: LisDCFLiff∃DPDA M s.t. L=L(M).Examples:1. Previous pda for {anbn|n ≥ 0} is deterministic.2. Previous pda for {anbmcn+m|n, m > 0} is deterministic.3. Previous pda for {wwR|w ∈ Σ+},Σ = {a, b} is nondeterministic.Note: There are CFL’s that are not deterministic.L={anbn|n ≥ 1}∪{anb2n|n≥1}is a CFL and 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}.Thesetwocanbe joined together by a new start state and λ-transitions to create a NPDA for L. Thus, L is CFL.Now show L is not a DCFL. Assume that there is a deterministic PDA M such that L = L(M). Wewill construct a PDA that recognizes a language that is not a CFL and derive a contradiction.Construct a PDA M0as follows:1. Create two copies of M : M1and M2. The same state in M1and M2are called cousins.2. Remove accept status from accept states in M1, remove initial status from initial state in M2.Inour new PDA, we will start in M1and accept in M2.3. Outgoing arcs from old accept states in M1, change to end up in the cousin of its destination inM2. This joins M1and M2into one PDA. There must be an outgoing arc since you mustrecognize both anbnand anb2n. After reading nb’s, must


View Full Document

Duke CPS 140 - Pushdown Automata

Download Pushdown Automata
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Pushdown Automata and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Pushdown Automata 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?