Automata theory - Push Down Automata (PDA)

Push down automata construction, types of language for empty stack and final state, Deterministic and non-deterministic PDA

1. 1 PUSH DOWN AUTOMATA

2. 2 Pushdown Automata (PDA) Informally: A PDA is an NFA-ε with a stack. Transitions are modified to accommodate stack operations. Questions: What is a stack? How does a stack help? A DFA can “remember” only a finite amount of information, whereas a PDA can “remember” an infinite amount of (certain types of) information, in one memory-stack

3. 3 Example: {0 n 1 n | 0=<n} is not regular, but {0 n 1 n | 0 ≤ n ≤ k, for some fixed k} is regular, for any fixed k. For k=3: L = {ε , 01, 0011, 000111} 0/1 q q 7 q 1 1 1 q 2 1 q 5 q 3 1 1 q 4 1 0/1 q 6

4. 4 In a DFA, each state remembers a finite amount of information. To get {0 n 1 n | 0 ≤ n} with a DFA would require an infinite number of states using the preceding technique. An infinite stack solves the problem for {0 n 1 n | 0 ≤ n} as follows: Read all 0’s and place them on a stack Read all 1’s and match with the corresponding 0’s on the stack Only need two states to do this in a PDA Similarly for {0 n 1 m n+m | n,m≥0}

5. Push down Automata 5

6. 6 Formal Definition of a PDA A pushdown automaton (PDA) is a seven-tuple: M = (Q, Σ, Г, δ, q , z , F) Q A finite set of states Σ A finite input alphabet Г A finite stack alphabet q The initial/starting state, q is in Q z A starting stack symbol, is in Г // need not always remain at the bottom of stack F A set of final/accepting states, which is a subset of Q δ A transition function, where δ: Q x (Σ U {ε}) x Г – > finite subsets of Q x Г*

7. 7 Consider the various parts of δ: Q x (Σ U {ε}) x Г – > finite subsets of Q x Г* Q on the LHS means that at each step in a computation, a PDA must consider its’ current state. Г on the LHS means that at each step in a computation, a PDA must consider the symbol on top of its’ stack. Σ U { ε } on the LHS means that at each step in a computation, a PDA may or may not consider the current input symbol, i.e., it may have epsilon transitions. “Finite subsets” on the RHS means that at each step in a computation, a PDA may have several options. Q on the RHS means that each option specifies a new state. Г* on the RHS means that each option specifies zero or more stack symbols that will replace the top stack symbol, but in a specific sequence .

8. 8 PDA transitions: δ(q, a, z) = {(p 1 ,γ 1 ), (p 2 ,γ 2 ),…, (p m ,γ m )} Current state is q Current input symbol is a Symbol currently on top of the stack z Move to state p i from q Replace z with γ i on the stack (leftmost symbol on top) Move the input head to the next input symbol : q p 1 p 2 p m a/z/ γ 1 a/z/ γ 2 a/z/ γ m

9. 9 Two types of PDA transitions: δ(q, ε , z) = {(p 1 ,γ 1 ), (p 2 ,γ 2 ),…, (p m ,γ m )} Current state is q Current input symbol is not considered Symbol currently on top of the stack z Move to state p i from q Replace z with γ i on the stack (leftmost symbol on top) No input symbol is read : q p 1 p 2 p m ε/z/ γ 1 ε/z/ γ 2 ε/z/ γ m

10. PDA - OPERATIONS 10 POP PUSH Skip / Do nothing

11. Construct a PDA Language: 0 n 1 n , n>=0 Transition function δ(q0, 0, z) = {(q , 0z)} δ(q , 0,00) = {(q , 00)} δ(q , 1, 0) = {(q1, λ)} δ(q 1 , 1, 0) = (q1, λ)} δ(q 1 , λ, Z) = {(q 2 , λ)} 11 Instantaneous description (ID): 0011 (q0, 011 λ , z ) push |- (q0, 11 λ , z) push |- (q0, 1 1 λ , 0z) pop |- (q1, 1 λ , z ) pop |- (q1, λ , z) no -operation |- (q2, λ , z): accept (q2 final state) Instantaneous description (ID): 011 (q0, 11 , z ) push |- (q0, 1 1, z) pop |- (q1, 1 , z ) no rule – halt at q1 reject

12. PDA Construction Problem 2 : L = = {0 n c 1 n  | n ≥ 1} 12

13. PDA Construction Problem 3 : L= { a m b n c n | m, n ≥ 0} - empy stack PDA 13

14. PDA Construction 14 Problem 4 : L = { wcw R  | w = (0+1)* }

15. PDA Construction 15 Problem 5: A = { w ∈ {0, 1} ∗ | w contains at least three 1s }

16. L={a n b 3n | n>=1 } 16

17. Exercise Construct PDA for acceptance by empty stack. L={a 2n b n | n>=0 } L = {0 n 1 n 2 m 3 m  | n>=1, m>=1} L={0 n 1 m n  | m, n>=1}. L= { a i b j c k | i, j, k ≥ 0 and i + j = k } Construct PDA for acceptance by Final state L = { a n b n c m | m, n ≥ 1 } L = {0 n 1 m 2 m 3 n  | n>=1, m>=1} L={a n b 2n | n>=0 } L={a n b 3n | n>=1 } L={a 3n b n | n>=0 } Note : L = {0 n 1 m 2 n 3 m  | n>=1, m>=1} (Hint This L is not CFL ) 17

18. 18 Definition: Let M = (Q, Σ, Г, δ, q , z , F) be a PDA. The language accepted by empty stack , denoted L E (M), is the set L E (M) = {w | (q , w, z ) |—* (p, ε, ε) for some p in Q} Definition: Let M = (Q, Σ, Г, δ, q , z , F) be a PDA. The language accepted by final state , denoted L F (M), is the set L E (M)= {w | (q , w, z ) |—* (p, ε, γ) for some p in F and γ in Г*} Definition: Let M = (Q, Σ, Г, δ, q , z , F) be a PDA. The language accepted by empty stack and final state , denoted L(M), is the set L E (M)= {w | (q , w, z ) |—* (p, ε, ε) for some p in F} Language Acceptance

19. Equivalence of CFG and PDA 19

20. CFG to PDA 20

21. Problem 1: CFG - PDA Convert the grammar S-> aAA, A->aS/bS/a to a PDA that accepts the same language by empty stack Solution : Let G be a CFG and G=(V,T,P,S) where V={S,A} T={a,b} p: S->aAA, A->aS/bS/a. To find the equivalent PDA Q={q0} ∑=T={a,b} Г=VUT={S,A,a,b} F=Ø Transition function for PDA : For each variable S,A δ(q0,Є,S)={(q0,aAA)} δ (q0,Є,A)={(q0,aS),(q0,bS),(q0,a)} For each terminal a,b δ (q0,a,a)={q0,Є} δ (0,b,b)={q0,Є} 21

22. Problem 2: CFG - PDA Convert the grammar S-> 0S1/A, A->1A0/S/є to a PDA that accepts the same language by empty stack. Solution : Let G be a CFG and G=(V,T,P,S) where V={S,A} T={a,b} p: S->aAA, A->aS/bS/a. To find the equivalent PDA Q={q0} ∑=T={0,1} Г=VUT={S,A,0,1} F=Ø Transition function for PDA : For each variable S,A δ (q0,Є,S)={(q0,0S1), (q0,A)} δ (q0,Є,A)={(q0,1A0),(q0,S),(q0, Є)} For each terminal 0,1 δ (q0,0,0)={q0,Є} δ (q0,1,1)={q0,Є} 22

23. Problem 3: CFG – PDA Construct PDA for the given CFG, and test whether 0104 is acceptable by this PDA. S → 0BB   B → 0S | 1S |    23   Solution: The PDA can be given as: A = {(q), ( ,  1 ), (S, B,  ,  1 ), δ, q, S, ?}   The production rule δ can be: R1: δ(q, ε, S) = {(q, 0BB)} R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)} R3: δ(q, 0, 0) = {(q, ε)} R4: δ(q, 1, 1) = {(q, ε)} Testing 010 4   i.e. 010000 against PDA: δ(q,  010000 , S) ⊢ δ(q,  010000 , 0BB)                   ⊢ δ(q,  10000 , BB)              R1                   ⊢ δ(q,  10000 ,1SB)              R3                     ⊢ δ(q,  0000 , SB)               R2                         ⊢ δ(q,  0000 , 0BBB)             R1                      ⊢ δ(q,  000 , BBB)               R3                         ⊢ δ(q,  000 , 0BB)               R2                       ⊢ δ(q,  00 , BB)                 R3                      ⊢ δ(q,  00 , 0B)                 R2                     ⊢ δ(q,  , B)                   R3                     ⊢ δ(q,  ,  )                   R2                   ⊢ δ(q, ε)                      R3                       ACCEPT   Thus 010 4  is accepted by the PDA.

24. 24 CFG to PDA conversion Formally, the given PDA is M = (Q, Σ, Г, δ, q , z , F). Define CFG G=(V, T, P, S), where V=[p x q] for all p & q Є Q and x Є Σ, T= Σ, P=Set of Production rules constructed from δ And S=Starting Symbol

25. Rules to construct P using δ R1 – Production Rules for S S 🡪 [q z p] for all p Є Q R2 – Production Rules corresponding to the transition move for pop operation (q, a, z) = (p, ϵ) [q z p] 🡪a

26. Cont… R3 - Production Rules corresponding to the transition move for push and read operation (q, a, z) = (q’, z 1 z 2 …….z n ) [q z p] 🡪 a [q’ z 1 q1] [q 1 z 2 q 2 ] ……… [q n z n p]

27. Convert the following PDA in to a CFG 27 Example 1

28. 28 Rule 1 Rule 2 Rule 3

29. Cont… 29

30. Cont… 30

31. Example 2 PDA TO CFG 31 Consider the given PDA and convert it to pda δ(p,0,z)=(p,A) δ(0,0,a)=(p,AA) δ (p,1,A)=(q, λ) δ (q,1,A)=(q, λ) Solution:

32.   EQUIVELANCE OF CFG AND PDA 32

33. Final State to Empty Stack PDA 33 (p , w,X ) |- (q , w, Z X 0) |-* (q, ε , α X ) |- ( p, ε ,ε ) Example : Design a PDA to check for well-formed parentheses

34. Empty Stack to Final State PDA 34 (p , w,X ) |- (q , w, Z X 0) |-* (q, ε , X ) |- ( pf, ε ,ε ) Example : Design a PDA to check for well-formed parentheses

35. Deterministic Pushdown automata DPDA- definition 35

36. Example - DPDA 36

37. Is Npda more powerful than DPDA? Power of NPDA is more than DPDA . It is not possible to convert every NPDA to corresponding DPDA. ... The languages accepted by DPDA are called DCFL (Deterministic Context Free Languages) which are subset of NCFL (Non Deterministic CFL) accepted by NPDA 37

38. Difference between DPDA and NDPA 38

39. Closure Properties of Context Free Grammar Context-free languages are closed under − Union - If L 1 and L 2 are CFL’s then L 1 ꓴL 2 is also CFL. Concatenation - If L 1 and L 2 are CFL’s then L 1 L 2 is also CFL. Kleene Star - If L 1 is CFL then L* 1 is also CFL.

40. Closure under Union Begin with two grammars: G 1 = ( V 1 , Σ , P 1 , S 1 ) and G 2 = ( V 2 , Σ , P 2 , S 2 ), generating CFL’s L 1 and L 2 respectively. The new CFG G x is made as: Σ remains the same S x is the new start variable V x = V 1 ∪ V 2 ∪ { S x } P x = P 1 ∪ P 2 ∪ { S x → S 1 |S 2 } Explanation: All we have done is augment the variable set with a new start state and then allowed the new start state to map to either of the two grammars. So, we’ll generate strings from either L 1 or L 2 , i.e. L 1 ꓴ L 2

41. Example Let L1 = { a n b n , n > 0}. Corresponding grammar G1 will have P: S1 → aAb|ab Let L2 = { c m d m , m ≥ 0}. Corresponding grammar G2 will have P: S2 → cBb| ε Union of L1 and L2, L = L1 ∪ L2 = { a n b n } ∪ { c m d m } The corresponding grammar G will have the additional production S → S1 | S2

42. Closure under Concatenation Begin with two grammars: G 1 = ( V 1 , Σ , P 1 , S 1 ) and G 2 = ( V 2 , Σ , P 2 , S 2 ), generating CFL’s L 1 and L 2 respectively. The new CFG G y is made as: Σ remains the same S y is the new start variable V y = V 1 ꓴ V 2 ꓴ { S y } P y = P 1 ꓴ P 2 ꓴ { S x → S 1 S 2 } Explanation: Again, all we have done is to augment the variable set with a new start state, and then allowed the new start state to map to the concatenation of the two original start symbols. So, we will generate strings that begin with strings from L 1 and end with strings from L 2 , i.e. L 1 L 2 .

43. Example Let L1 = { a n b n , n > 0}. Corresponding grammar G1 will have P: S1 → aAb|ab Let L2 = { c m d m , m ≥ 0}. Corresponding grammar G2 will have P: S2 → cBb| ε Concatenation of the languages L1 and L2, L = L1L2 = { a n b n c m d m } The corresponding grammar G will have the additional production S → S1 S2

44. Clouser under Kleene Star Begin with two grammars: G 1 = ( V 1 , Σ , P 1 , S 1 ) and G 2 = ( V 2 , Σ , P 2 , S 2 ), generating CFL’s L 1 and L 2 respectively. The new CFG G z is made as: Σ remains the same S z is the new start variable V z = V 1 ꓴ { S z } P z = P 1 ꓴ { S z → S 1 S z | ε } Explanation: Again we have augmented the variable set with a new start state, and then allowed the new start state to map to either S 1 S z or ε. This means we can generate strings with zero or more strings made from expanding the variable S 1 , i.e. L* 1 .

45. Example Let L = { a n b n , n ≥ 0}. Corresponding grammar G will have P: S → aAb| ε Kleene Star L1 = { a n b n }* The corresponding grammar G1 will have additional productions S1 → SS1 | ε

46. Context-free languages are not closed under − Intersection − If L1 and L2 are context free languages, then L1 ∩ L2 is not necessarily context free. Intersection with Regular Language − If L1 is a regular language and L2 is a context free language, then L1 ∩ L2 is a context free language. Complement − If L1 is a context free language, then L1’ may not be context free.