I had an assignment in which I had to design a pushdown automata that recognizes the language ${w \in [a,b,c]^*|w }$ have the same number of "ab" and "ba".

Tried to make a pushdown automata that if reads first ab pushes 1 to the stack and then if finds "ba" then pops it (and again reads "ab" and then "ba" , push / pop ) and the same if reads first "ba" and pops if finds "ab",but this approach fails for the case : ${baababbabaab}$ and many more cases. If someone could find whats wrong with my approach


1 Answer 1


To see what goes wrong with your approach, it's best to scale down a bit.

As you've defined it, the string $aba$ lies in the language. You should try to come up with a way to make your automata accept this string.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.