CS 172: Computability and ComplexityPushdown Automata & Equivalence with CFGsSanjit A. SeshiaEECS, UC BerkeleyAcknowledgments: L.von Ahn, L. Blum, M. BlumS. A. Seshia 2Chomsky Normal FormA CFG is in Chomsky Normal Form (CNF) if every rule is in one of the following three forms:S εA B C B, C are variables ≠ SA a a is a terminal(S is the start variable; A is any variable, including S)Theorem: Any CFG can be converted into an equivalent CFG (generating the same CFL) in Chomsky Normal Form(proof done on the board – read Sipser Thm 2.9)S. A. Seshia 3FINITE STATE CONTROLINPUTFinite AutomatonS. A. Seshia 4FINITE STATE CONTROLSTACK(Last in, first out)INPUTPushdown AutomatonS. A. Seshia 5ε,ε →$0,ε →01,0→ ε1,0→ εε,$ → εinput pop push0011 001101111$1STACK00What happens if the input is 001?PUSHDOWN AUTOMATON EXAMPLES. A. Seshia 6Informal Definition of Acceptance• A pushdown automation accepts if, after reading the entire input, it ends in an accept state• Sometimes: (with an empty stack)S. A. Seshia 7Definition: A (non-deterministic) PDA is a tupleP = (Q, Σ, Γ, δδδδ, q0, F), where: Q is a finite set of statesΓ is the stack alphabetq0∈∈∈∈ Q is the start stateF ⊆⊆⊆⊆ Q is the set of accept statesΣ is the input alphabetδδδδ : Q ×××× Σε×××× Γε→ 2 Q ×××× Γε2Sis the set of subsets of SΣε= Σ ∪∪∪∪ {ε}, Γε= Γ ∪∪∪∪ {ε}(non-determinism)S. A. Seshia 8Formal Definition of AcceptancePDA P = (Q, Σ, Γ, δ, q0, F) accepts a word w ∈∈∈∈ Σ* where w = w1w2w3. . .wm with wi∈∈∈∈ Σεif there exists a sequence(q0, s0)  (q1, s1)  (q2, s2)  …  (qm, sm) where si∈∈∈∈ Γ*(represent the stack), with s0= ε,qm∈∈∈∈ F,(qi+1, b) ∈∈∈∈ δ(qi, wi+1, a) where si= at and si+1= bt , a,b ∈∈∈∈ Γε, t ∈∈∈∈ Γ*S. A. Seshia 9ε,ε →$0,ε →01,0→ ε1,0→ εε,$ → εq0q1q2q3Q = {q0, q1, q2, q3} Γ =Σ =δδδδ : Q ×××× Σε×××× Γε→ 2 Q ×××× Γε{0,1} {$,0,1}δδδδ(q1,1,0) = { (q2,ε) }δδδδ(q2,1,1) = ∅∅∅∅S. A. Seshia 10EVEN-LENGTH PALINDROMESΣΣΣΣ = {a, b, c, …, z}, σσσσ ∈∈∈∈ ΣΣΣΣε,ε →$ε,ε → εσσσσ,σσσσ → εε,$ → εq0q1q2q3σσσσ,ε → σσσσS. A. Seshia 11Build a PDA to recognize L = { aibjck| i, j, k ≥ 0 and (i = j or i = k) }ε,ε →$b,a→ εε,$ → εq0q5q1q3a,ε →aq2q4ε,ε→εq6ε,ε → εε,ε → εε,$ → εb,ε → εc,a→ εc,ε → εS. A. Seshia 12A Language is generated by a CFG ⇔⇔⇔⇔It is recognized by a PDATheoremS. A. Seshia 13A Language is generated by a CFG ⇒⇒⇒⇒It is recognized by a PDASuppose L is generated by a CFG G = (V, Σ, R, S)Construct P = (Q, Σ, Γ, δδδδ, q, F) that recognizes LTheoremS. A. Seshia 14Intuition (warning: not a formal proof!)Map a derivation in the CFG G to an accepting sequence for the PDA PLet w ∈∈∈∈L(G)There is a derivation in G:S α1α2. . . αm-1w where αi∈ ∈ ∈ ∈ (Σ∪V)*We map it to an accepting sequence (q0, s0) (q1, s1) … (q2, s2) …(qm, sm) (qf, sf)where q1= q2= … = qm= qloop, qf∈∈∈∈F, s0= S$, si= αi$ (1 i m) siis obtained from si-1(1 i m) by using substitution at corresponding step of the derivation and matching terminals on the top of the stack with the input(see picture on slide 16)S. A. Seshia 15Suppose L is generated by a CFG G = (V, Σ, R, S)Construct P = (Q, Σ, Γ, δδδδ, q, F) that recognizes L(1) Place the marker symbol $ and the start variable S on the stack(2) Repeat the following steps forever:(a) If top of stack is a variable, non-deterministically select rule that matches the variable and push result into the stack(b) If top of stack is a terminal, read next symbol from input and compare it to terminal. If different, reject.(c) If top of stack is $, then enter accept state. Accept if the input has all been read.S. A. Seshia 16ε,ε → S$ε,$ → εε,A → w for rule A → wa,a → ε for terminal aqloopqfq0Note: RHS is a string(non-std notation just for intuition)S. A. Seshia 17S → aTbT → Ta | εε,ε →$ε,$ → εε,ε →Sε,S →bε,ε →Tε,T →aε,ε →aε,ε →Tε,T → εa,a→ εb,b→ εS. A. Seshia 18A Language is generated by a CFG It is recognized by a PDA⇒⇒⇒⇒Next:S. A. Seshia 19Next Steps• Read Sipser 2.3 in preparation for next