Pda

covers def of PDA and various problems

1. Push Down Automata(PDA)

2. Model of PDA Push Down Automaton : "Finite state machine" + "a stack"

3. A pushdown automaton has three components − input tape, control unit, and stack with infinite size. The stack head scans the top symbol of the stack. A stack does two operations − Push  − a new symbol is added at the top. Pop  − the top symbol is read and removed.

4. Def: PDA A PDA can be formally described as a 7-tuple (Q, ∑, Γ , δ, q , Z , F) Q- finite number of states ∑  -input alphabet Γ  -stack symbols δ  -transition function: Q × (∑ ∪ {ε}) × Γ  Q × Γ * Ex: δ( q ,a, Z ) = ( q 1 ,a Z ) Q initial state (q  ∈ Q) Z  is the initial stack top symbol (Z ∈ Γ ) F  is a set of accepting states (F ∈ Q)

5. Graphical Representation of PDA

6. Instantaneous Description of PDA Instantaneous Description (ID) is an informal notation of how a PDA “computes” a input string and make a decision that string is accepted or rejected. It is denoted by a triple (q, w, γ) where; q is the current state w is the unread part of the input string or the remaining input alphabets γ is the current contents of the PDA stack

7. Ex 1: Write down the IDs or moves for input string w = “ aabb ” of PDA as M = ({q , q 1 }, {a, b}, {a, b, Z }, δ, q0, Z , {q 1 }), where δ is defined by following rules: δ( q , a, Z )       = {(q , aZ )}     Push δ( q , a, a)         = {(q , aa )}      Push δ( q , b, a)         = {(q 1 , ε )}        Pop δ( q 1 , b, a)         = {(q 1 , ε )}        Pop Also check string w is accepted by PDA or not?

8. Solution:  Instantaneous Description for string w = “ aabb ” (q , aabb , Z )   |- (q , abb , aZ )            |- (q , bb, aaZ )            |- (q 1 , b, aZ )                |- (q 1 , ε, Z )                                 Finally the input tape is empty or input string w is completed, PDA stack is empty and PDA has reached a final state. So the string ‘w’ is  accepted . δ( q , a, Z )       = {(q , aZ )}     Push δ( q , a, a)         = {(q , aa )}      Push δ( q , b, a)         = {(q 1 , ε )}        Pop δ( q 1 , b, a)         = {(q 1 , ε )}        Pop

9. Example 2:  Write down the Ids for input string w = “ aaabb ” of the above PDA. Also check it is accepted by PDA or not? (q , aaabb , Z ) |- (q , aabb , aZ ) |- (q , abb , aaZ ) |- (q , bb, aaaZ ) |- (q 1 , b, aaZ ) |- (q 1 , ε , aZ ) |- There is no defined move So the pushdown automaton stops at this move and the string is not accepted because the input tape is empty or input string w is completed but the PDA stack is not empty. So the string ‘w’ is  not accepted . Note: The above method is also called testing of a string using final state method δ( q , a, Z )       = {(q , aZ )}     Push δ( q , a, a)         = {(q , aa )}      Push δ( q , b, a)         = {(q 1 , ε )}        Pop δ( q 1 , b, a)         = {(q 1 , ε )}        Pop

10. Language Acceptance by PDA Method-1: Acceptance by final state method(Ids Method) Method-2: Stack Empty Method

11. Ex: Design a PDA to recognize the language L={ wcw r : w ∈ ( a+b ) * }

12. Test the string w= aabbcbbaa is accepted by final state method

13. Test the string w= aabbcbbaa is accepted by Stack Empty Method

14. step1: a b b a c a b b a     current state=q0 Z0 operation=push(a) step2: a b b a c a b b a   a current state=q0 Z0 operation=push(b) step3: a b b a c a b b a b a current state=q0 Z0 operation=push(b) step 4: a b b a c a b b a b b current state=q0 a operation=push(a) Z0 step 5: a b b a c a b b a a b current state=q0 b operation= no push a no pop Z0 step 6: a b b a c a b b a a b current state=q1 b operation=pop() a Z0 step 7: a b b a c a b b a   b current state=q1 b operation=pop() a Z0 step 8: a b b a c a b b a     current state=q1 b operation=pop() a Z0 step 9: a b b a c a b b a     current state=q1   operation=pop() a Z0 step 10: a b b a c a b b a     current state=q1   string is empty   stack is empty Z0 Therefore String is accepted

15. Design a PDA which accepts L={ a n b n : n>=1}. Check whether the strings I) aaabb II) aabbb and III) aaabbb are accepted or not using i ) Final state method ii) Stack Method

16. step1: a a a b b     current state=q0 Z0 operation=push(a) step2: a a a b b   a current state=q0 Z0 operation=push(a) step3: a a a b b a a current state=q0 Z0 operation=push(a) step 4: a a a b b a a current state=q0 a operation=pop() Z0 step 5: a a a b b   current state=q1 a operation= pop() a Z0 step 6: a a a b b   current state=q1   Input string: empty a Z0 String is rejected Stack Method

17. Design a PDA which accepts only odd no of a’s defined over { a,b }. Check whether the string baababababbbbbaa is accepted or not using final state and stack methods Construct a PDA for the language L={a n b 2n : n>=1}. Check whether the string aabbbb is accepted or not by the given language using i ) Final state method ii) Stack Method Construct a PDA for the language L={a n cb 2n : n>=1}. Check the string aaacbbbbbbb Construct a PDA for the language L={a 2n b n : n>=1}. Check the string aaaacbb Design a PDA for well formed Parenthesis (),[],{} Design PDA for a language L={w/w is in ( a+b )* and na (w)= nb (w) }

18. Design PDA for a language L={w/w is in ( a+b )* and na (w)> nb (w) } Design PDA for a language L={w/w is in ( a+b )* and na (w)< nb (w)}

19. Types of PDA DPDA Previously constructed PDAs are DPDAs NPDA Ex1: Design a PDA to recognize the language L={ ww r : w ∈ ( a+b ) * } Ex2: construct PDA for language L containing all the strings which are palindrome over { a,b }

20. Two stack PDA A two stack PDA can be formally described as a 9-tuple (Q, ∑, Γ , Γ 1 , δ, q , Z 1 , Z 2 , F) Q- finite number of states ∑  -input alphabet Γ  –stack1 symbols Γ 1  –stack2 symbols δ  -transition function: Q × (∑ ∪ {ε}) × Γ x Γ 1  (Q, Γ , Γ 1 ) δ( q ,a, Z 1 , Z 2 ) = ( q 1 ,a Z 1 , Z 2 ) Q initial state (q  ∈ Q) Z 1  is the initial stack1 top symbol (Z 1 ∈ Γ ) Z 2  is the initial stack2 top symbol (Z 2 ∈ Γ 1 ) F  is a set of accepting states (F ∈ Q) Ex: Design a two stack PDA which accepts L={ a n b n c n : n>=1}.

21. Construction of PDA from CFG (or) CFG to PDA Conversion Step 1  − Convert the productions of the CFG into GNF. Step 2  − The PDA will have only one state {q}. Step 3  − The start symbol of CFG will be the start symbol in the PDA. Step 4  − All non-terminals of the CFG will be the stack symbols of the PDA and all the terminals of the CFG will be the input symbols of the PDA. Step 5  − For each production in the form  A → aX  make a transition  δ (q, a, A)=( q,X ) . Step 6 - For each production in the form  A → a  make a transition  δ (q, a, A)=(q,  ε ) .

22. Ex: Convert the following CFG in to PDA S aAA , AaS / bS /a The grammar is in GNF For S aAA : δ (q, a, S)=( q,AA ) . For A aS : δ (q, a, A)=( q,S ) . For A bS : δ (q, b, A)=( q,S ) For A a : δ (q, a, A)=(q,  ε ) . The Equivalent PDA: δ (q, a, S)=( q,AA ) . δ (q, a, A)=( q,S ) . δ (q, b, A)=( q,S ) δ (q, a, A)=(q,  ε ) For A → aX  : δ (q, a, A)=( q,X ) . For   A → a  : δ (q, a, A)=(q,  ε ) .

23. I a /b SaA AaABC / bB /a Bb Cc

24. S aBB BbS /c