TOC_PDA

Question

Comments

Yes I think it is C)

---

Option C seems correct to me. not sure.

---

Option a) is wrong because after pushing 'a' and popping 'b' we have a transition back to initial state so we can again push more a's and pop b's i.e aabbaabb is possible which is not present in this option.

Option b) is wrong because for every 'a' we have 'b' to be popped but say we if take aaabb after reading this string we are at q1 and there is no transition at q1 in which are reading epsilon and top of the stack is 'b'. Hence rejected.

Option d) is wrong because in this same as above mentioned no of a's and no of b's can be different but will not be accepted by PDA

Option c) is correct as it is accepting epsilon, no of a's and no of b's are equal and we can perform push a pop b push a pop b (provided no of a's and no of b's are equal)

Answer 1

here for every a ....we do push and for every b we pop a ...but at 2nd state we have a transaction which send us back to 1st state so after a^nb^ we are again able to push a's and continue cycle.....even zero length string is also accepted due to transaction (episolon,Z0,episolon)...hence answer is

C)(a^nb^n)^* where n>0.......