PDA (1) (1).pptx

pushdown automata

1. 1 Pushdown Automata (PDA) Reading: Chapter 6

2. 2 PDA - the automata for CFLs What is? FA to Reg Lang, PDA is to CFL PDA == [  -NFA + “a stack” ] Why a stack?  -NFA A stack filled with “stack symbols” Input string Accept/reject

3. 3 Pushdown Automata - Definition A PDA P := ( Q,∑,  , δ ,q , Z ,F ): Q: states of the  -NFA ∑: input alphabet  : stack symbols δ: transition function q : start state Z : Initial stack top symbol F: Final/accepting states

4. δ : The Transition Function δ(q,a,X) = {(p,Y), …} state transition from q to p a is the next input symbol X is the current stack top symbol Y is the replacement for X; it is in  * (a string of stack symbols) Set Y =  for: Pop(X) If Y=X: stack top is unchanged If Y=Z 1 Z 2 … Z k : X is popped and is replaced by Y in reverse order (i.e., Z 1 will be the new stack top) 4 Non-determinism old state Stack top input symb. new state(s) new Stack top(s) δ : Q x ∑ x  => Q x  q a X p Y Y = ? Action i ) Y=  Pop(X) ii) Y=X Pop(X) Push(X) iii) Y=Z 1 Z 2 .. Z k Pop(X) Push( Z k ) Push(Z k-1 ) … Push(Z 2 ) Push(Z 1 )

5. 5 Example Let L wwr = {ww R | w is in (0+1)*} CFG for L wwr : S==> 0S0 | 1S1 |  PDA for L wwr : P := ( Q,∑,  , δ,q ,Z ,F ) = ( {q , q 1 , q 2 },{0,1},{0,1,Z }, δ,q ,Z ,{q 2 } )

6. 6 PDA for L wwr δ(q ,0, Z )={(q ,0Z )} δ(q ,1, Z )={(q ,1Z )} δ(q , , 0)={(q , 0)} δ(q , , 1)={(q , 1)} δ(q , 1 , 0)={(q , 1 0)} δ(q , 1 , 1)={(q , 1 1)} δ(q ,  , 0)={( q 1 , 0)} δ(q ,  , 1)={( q 1 , 1)} δ(q ,  , Z )={( q 1 , Z )} δ( q 1 ,0 , 0)={( q 1 ,  )} δ(q 1 , 1 , 1)={( q 1 ,  )} δ( q 1 ,  , Z )={( q 2 , Z )} First symbol push on stack Grow the stack by pushing new symbols on top of old (w-part) Switch to popping mode, nondeterministically (boundary between w and w R ) Shrink the stack by popping matching symbols (w R -part) Enter acceptance state Z Initial state of the PDA: q Stack top

7. 7 PDA as a state diagram q i q j a, X / Y Current state Next input symbol Current state Current stack top Stack Top Replacement (w/ string Y) Next state δ(q i , a , X )={(q j , Y )}

8. 8 PDA for L wwr : Transition Diagram q q 1 q 2 0, Z /0Z 1, Z /1Z 0, 0/00 0, 1/01 1, 0/10 1, 1/11 0, 0/  1, 1/   , Z /Z  , 0/0  , 1/1  , Z /Z Grow stack Switch to popping mode Pop stack for matching symbols Go to acceptance ∑ = {0, 1} = {Z , 0, 1} Q = {q ,q 1 ,q 2 }  , Z /Z This would be a non-deterministic PDA

9. 9 Example 2: language of balanced paranthesis q q 1 q 2 (, Z / ( Z  , Z / Z  , Z / Z Grow stack Switch to popping mode Pop stack for matching symbols Go to acceptance ( by final state ) when you see the stack bottom symbol ∑ = { (, ) } = {Z , ( } Q = {q ,q 1 ,q 2 } (, ( / ( ( ) , ( /  ), ( /  To allow adjacent blocks of nested paranthesis ( , ( / ( ( ( , Z / ( Z  , Z / Z

10. 10 Example 2: language of balanced paranthesis (another design) ∑ = { (, ) } = {Z , ( } Q = {q ,q 1 } q (,Z / ( Z (,( / ( ( ), ( /  start q 1  ,Z / Z  ,Z / Z

11. 11 PDA’s Instantaneous Description (ID) A PDA has a configuration at any given instance: (q,w,y) q - current state w - remainder of the input (i.e., unconsumed part) y - current stack contents as a string from top to bottom of stack If δ( q,a, X )={( p, A )} is a transition, then the following are also true : ( q, a , X ) |--- ( p ,  , A ) ( q, a w, X B ) |--- ( p ,w, A B) |--- sign is called a “turnstile notation” and represents one move |---* sign represents a sequence of moves

12. 12 How does the PDA for L wwr work on input “1111”? (q ,1111,Z ) (q ,111,1Z ) (q ,11,11Z ) (q ,1,111Z ) (q ,  ,1111Z ) (q 1 ,  ,1111Z ) (q 1 ,  ,11Z ) (q 1 ,1,111Z ) (q 1 ,11,11Z ) (q 1 ,111,1Z ) (q 1 ,1111,Z ) Path dies… Path dies… (q 1 ,1,1Z ) (q 1 ,  ,Z ) (q 2 ,  ,Z ) Acceptance by final state: = empty input AND final state All moves made by the non-deterministic PDA Path dies… Path dies…

13. 13 Principles about IDs Theorem 1: If for a PDA, (q, x, A) |---* (p, y, B) , then for any string w  ∑* and    *, it is also true that: ( q, x w, A  ) |---* ( p , y w, B  ) Theorem 2: If for a PDA, ( q, x w, A ) |---* ( p, y w, B ) , then it is also true that: (q, x, A) |---* (p, y, B)

14. 14 Acceptance by… PDAs that accept by final state : For a PDA P, the language accepted by P, denoted by L(P) by final state , is: {w | (q ,w,Z ) |---* (q,  , A) } , s.t., q  F PDAs that accept by empty stack : For a PDA P, the language accepted by P, denoted by N(P) by empty stack , is: {w | (q ,w,Z ) |---* (q,  ,  ) } , for any q  Q. Checklist: - input exhausted? - in a final state? Checklist: - input exhausted? - is the stack empty? There are two types of PDAs that one can design: those that accept by final state or by empty stack Q) Does a PDA that accepts by empty stack need any final state specified in the design?

15. Example: L of balanced parenthesis 15 q (,Z / ( Z (,( / ( ( ), ( /  start q 1  ,Z / Z  ,Z / Z PDA that accepts by final state q start (,Z / ( Z (, ( / ( ( ), ( /   ,Z /  An equivalent PDA that accepts by empty stack  ,Z / Z P F : P N : How will these two PDAs work on the input: ( ( ( ) ) ( ) ) ( )

16. 16 PDA for L wwr : Proof of correctness Theorem: The PDA for L wwr accepts a string x by final state if and only if x is of the form ww R . Proof: (if-part) If the string is of the form ww R then there exists a sequence of IDs that leads to a final state: (q ,ww R ,Z ) |---* (q ,w R ,wZ ) |---* (q 1 ,w R ,wZ ) |---* (q 1 ,  ,Z ) |---* ( q 2 ,  ,Z ) (only-if part) Proof by induction on |x|

17. 17 PDAs accepting by final state and empty stack are equivalent P F <= PDA accepting by final state P F = (Q F ,∑,  , δ F ,q ,Z ,F ) P N <= PDA accepting by empty stack P N = (Q N ,∑,  , δ N ,q ,Z ) Theorem: (P N ==> P F ) For every P N , there exists a P F s.t. L(P F )=L(P N ) (P F ==> P N ) For every P F , there exists a P N s.t. L(P F )=L(P N )

18. 18 P N ==> P F construction Whenever P N ’s stack becomes empty, make P F go to a final state without consuming any addition symbol To detect empty stack in P N : P F pushes a new stack symbol X (not in  of P N ) initially before simultating P N q … p f p  , X /Z X New start  , X / X  , X / X  , X / X  , X / X P N P F : P F = (Q N U {p ,p f }, ∑,  U { X }, δ F , p , X , { p f }) P N :  , X / X How to convert an empty stack PDA into a final state PDA?

19. 19 Example: Matching parenthesis “(” “)” P N : ( {q }, {(,)}, {Z ,Z 1 }, δ N , q , Z ) δ N : δ N (q ,(,Z ) = { (q ,Z 1 Z ) } δ N (q ,(,Z 1 ) = { (q , Z 1 Z 1 ) } δ N (q ,),Z 1 ) = { (q ,  ) } δ N (q ,  ,Z ) = { (q ,  ) } q start (,Z /Z 1 Z (,Z 1 /Z 1 Z 1 ),Z 1 /   ,Z /  q (,Z /Z 1 Z (,Z 1 /Z 1 Z 1 ),Z 1 /   ,Z /  start p p f  ,X /Z X  ,X / X P f : ( {p ,q ,p f }, {(,)}, {X ,Z ,Z 1 }, δ f , p , X 0 , p f ) δ f : δ f (p ,  ,X ) = { (q ,Z ) } δ f (q ,(,Z ) = { (q ,Z 1 Z ) } δ f (q ,(,Z 1 ) = { (q , Z 1 Z 1 ) } δ f (q ,),Z 1 ) = { (q ,  ) } δ f (q ,  ,Z ) = { (q ,  ) } δ f (p ,  ,X ) = { (p f , X ) } Accept by empty stack Accept by final state

20. 20 P F ==> P N construction Main idea: Whenever P F reaches a final state, just make an  -transition into a new end state, clear out the stack and accept Danger: What if P F design is such that it clears the stack midway without entering a final state?  to address this, add a new start symbol X (not in  of P F ) P N = (Q U {p ,p e } , ∑,  U { X } , δ N , p , X ) p  , X /Z X New start  , any/   , any/   , any/  q … p e  , any/  P F P N : How to convert an final state PDA into an empty stack PDA?

21. 21 Equivalence of PDAs and CFGs

22. 22 CFGs == PDAs ==> CFLs CFG PDA by final state PDA by empty stack ? ≡

23. 23 Converting CFG to PDA Main idea: The PDA simulates the leftmost derivation on a given w, and upon consuming it fully it either arrives at acceptance (by empty stack ) or non-acceptance. This is same as: “implementing a CFG using a PDA” PDA (acceptance by empty stack) CFG w accept reject implements INPUT OUTPUT

24. 24 Converting a CFG into a PDA Main idea: The PDA simulates the leftmost derivation on a given w, and upon consuming it fully it either arrives at acceptance (by empty stack ) or non-acceptance. Steps: Push the right hand side of the production onto the stack, with leftmost symbol at the stack top If stack top is the leftmost variable, then replace it by all its productions (each possible substitution will represent a distinct path taken by the non-deterministic PDA) If stack top has a terminal symbol, and if it matches with the next symbol in the input string, then pop it State is inconsequential (only one state is needed) This is same as: “implementing a CFG using a PDA”

25. 25 Formal construction of PDA from CFG Given: G= (V,T,P,S) Output: P N = ({q}, T, V U T, δ , q, S) δ : For all A  V , add the following transition(s) in the PDA: δ (q,  ,A) = { (q,  ) | “A ==> ”  P } For all a  T, add the following transition(s) in the PDA: δ (q , a , a )= { (q,  ) } A Before: … a Before: …  After: … a After: … Note: Initial stack symbol (S) same as the start variable in the grammar pop a…

26. 26 Example: CFG to PDA G = ( {S,A}, {0,1}, P, S) P: S ==> AS |  A ==> 0A1 | A1 | 01 PDA = ({q}, {0,1}, {0,1,A,S}, δ, q, S ) δ: δ(q,  , S) = { (q, AS), (q,  )} δ(q,  , A) = { (q,0A1), (q,A1), (q,01) } δ(q, 0, 0) = { (q,  ) } δ(q, 1, 1) = { (q,  ) } How will this new PDA work? Lets simulate string 0011 q  ,S / S 1,1 /  0,0 /   ,A / 01  ,A / A1  ,A / 0A1  ,S /   ,S / AS

27. Simulating string 0011 on the new PDA … 27 PDA ( δ ) : δ(q,  , S) = { (q, AS), (q,  )} δ(q,  , A) = { (q,0A1), (q,A1), (q,01) } δ(q, 0, 0) = { (q,  ) } δ(q, 1, 1) = { (q,  ) } S Stack moves (shows only the successful path): S A S 1 A S 1 A S 1 1 S 1 1 S 1 1 S 1  Accept by empty stack q  ,S / S 1,1 /  0,0 /   ,A / 01  ,A / A1  ,A / 0A1  ,S /   ,S / AS S => AS => 0A1S => 0011S => 0011 Leftmost deriv.: S =>AS =>0A1S =>0011S => 0011

28. 28 Proof of correctness for CFG ==> PDA construction Claim: A string is accepted by G iff it is accepted (by empty stack) by the PDA Proof: ( only-if part ) Prove by induction on the number of derivation steps ( if part ) If (q, wx, S) |-- * (q,x,B) then S => * lm wB

29. 29 Converting a PDA into a CFG Main idea: Reverse engineer the productions from transitions If δ(q,a,Z) => (p, Y 1 Y 2 Y 3 …Y k ): State is changed from q to p; Terminal a is consumed; Stack top symbol Z is popped and replaced with a sequence of k variables. Action: Create a grammar variable called “[qZp]” which includes the following production: [qZp] => a[p Y 1 q 1 ] [q 1 Y 2 q 2 ] [q 2 Y 3 q 3 ]… [q k-1 Y k q k ] Proof discussion (in the book)

30. 30 Example: Bracket matching To avoid confusion, we will use b =“(“ and e =“)” P N : ( {q }, {b,e}, {Z ,Z 1 }, δ, q , Z ) δ(q ,b,Z ) = { (q ,Z 1 Z ) } δ(q ,b,Z 1 ) = { (q ,Z 1 Z 1 ) } δ(q ,e,Z 1 ) = { (q ,  ) } δ(q ,  ,Z ) = { (q ,  ) } 0. S => [q Z q ] [q Z q ] => b [q Z 1 q ] [q Z q ] [q Z 1 q ] => b [q Z 1 q ] [q Z 1 q ] [q Z 1 q ] => e [q Z q ] =>  Let A=[q Z q ] Let B=[q Z 1 q ] 0. S => A A => b B A B => b B B B => e A =>  Simplifying, 0. S => b B S |  B => b B B | e If you were to directly write a CFG: S => b S e S | 

31. 31 Two ways to build a CFG Build a PDA Construct CFG from PDA Derive CFG directly Derive a CFG Construct PDA from CFG Design a PDA directly Similarly… (indirect) (direct) (indirect) (direct) Two ways to build a PDA

32. 32 Deterministic PDAs

33. 33 This PDA for L wwr is non-deterministic q q 1 q 2 0, Z /0Z 1, Z /1Z 0, 0/00 0, 1/01 1, 0/10 1, 1/11 0, 0/  1, 1/   , Z /Z  , 0/0  , 1/1  , Z /Z Grow stack Switch to popping mode Pop stack for matching symbols Accepts by final state Why does it have to be non-deterministic? To remove guessing, impose the user to insert c in the middle

34. 34 D-PDA for L wcwr = {wcw R | c is some special symbol not in w} q q 1 q 2 0, Z /0Z 1, Z /1Z 0, 0/00 0, 1/01 1, 0/10 1, 1/11 0, 0/  1, 1/  c , Z /Z c , 0/0 c , 1/1  , Z /Z Grow stack Switch to popping mode Pop stack for matching symbols Accepts by final state Note: all transitions have become deterministic Example shows that: Nondeterministic PDAs ≠ D-PDAs