3.4 deterministic pda

deterministic pda

1. Deterministic Pushdown Automata (DPDA) Sampath Kumar S, AP/CSE, SECE

2. Types of PDA The PDA can be classified into: Deterministic PDA – PDA that has at most one choice of move in any state. Non-deterministic PDA - PDA that has more than one choice of move in any state. 12 September 2017 Sampath Kumar S, AP/CSE, SECE 2

3. Problems to discuss: 111. Design a PDA which accepts L={ a n b n |n > 1} Solution: Let q be the initial stat, q 3 be the final state and z be bottom of the stack. Read each ‘ a ’ and push into stack. Then read each ‘ b ’ and pop out the stack for matching a’s . Where all b’s are read if the stack is empty then it is successful If any a’s are left over on the stack or b’s on input tape, it is rejected. 12 September 2017 Sampath Kumar S, AP/CSE, SECE 3

4. Solution for sum 111: The PDA moves are as follows: δ ( q , a, z ) = ( q 1 , a z ) ….. (PUSH a) δ ( q 1 , a, a) = ( q 1 , a a ) ….. (PUSH a) δ ( q 1 , b, a) = ( q 2 , ε ) ….. (POP a) δ ( q 2 , b, a) = ( q 2 , ε ) ….. (POP a) δ ( q 2 , ε , z ) = ( q 3 , z ) ….. (Accept and HALT) 12 September 2017 Sampath Kumar S, AP/CSE, SECE 4

5. Problems to discuss: 112. Design a PDA which accept the language containing equal number of a’s and b’s over Σ ={a, b}. 113. Design a PDA which accepts L={a n b 2n |n > 1} 114. Design a PDA which accepts L={a 3 b n c n |n>0} 115. Design a PDA which accepts L={ wcw r |w  ( a+b )*} 116. Design a PDA which accepts the set of balanced parenthesis. ([{()}]) 12 September 2017 Sampath Kumar S, AP/CSE, SECE 5

6. Problems to discuss: 117. Design a PDA which accepts L={ a p b n c m |p+m =n}. 118. Design a PDA which accepts L={0 m 1 n m |m,n > 1}. 119. Design a PDA which accepts L={a i b j c k |i+j=k; i , j > 1}. 12 September 2017 Sampath Kumar S, AP/CSE, SECE 6

7. Problems to discuss: 120. Design a PDA which accepts L={ a n b m c n d m |n,m > 1}. 121. Design a PDA which accepts L={ a n b 2n+1 |n > 1 } 12 September 2017 Sampath Kumar S, AP/CSE, SECE 7

8. 12 September 2017 Sampath Kumar S, AP/CSE, SECE 8

9. நன்றி  12 September 2017 Sampath Kumar S, AP/CSE, SECE 9