Question

TEACH YOUR NEIGHBORGROUP Design a PDA accepting the language w E a, b]:na(w) -nb(w). Please teach your group (for homework) and submit the TYG report noon of Wednesday. I will post the solution PDA on Thursday's lecture note.

Answer 1

"Language {w elementof (a,b);n_a(w) = n_b(w)}+: PDA should accept String that contains number of a's equal to number of b's Language = {E,ab,ba,aabb,abab,bbaa....} Idea is, push whenever see 'a' and POP whenever we see 'b' and pop if Stack already Contains 'a' So, in the end of stack if nothing is left then we can say it's CFL is accepted by PDA PDA explanation, Let's take input string ""abba"" 1. Scan String from left to right 2. First input is 'a' and follow the rule: on input 'a' Stack alphabet Z_0 push the input 'a' as (a,Z_0/a Z_0) and state will be q_0 \r\n 3. Second input is 'b' so on input 'b', stack alphabet 'a' as: (b,a/E) delete 'a' from stack 4. on input 'b', stack Symbol 'Z_0' as (b.Z_0/bZ_0) Push to the Stack 5. on input 'a', Stack Symbol 'b' as (b,a/E) POP 'b' from Stack. State is q_0 6. We reached end of String, on input E and Stack alphabet Z_0"