Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Give informal English descriptions of PDAs for the languages and draw the state diagrams for the PDAs.

The complement of the language $ [a^nb^n| n ≥ 0] $

My informal description: The PDA uses it's stack to count the number of a's and b's and it will enter and accepting state whenever this count is not equal.

  1. The PDA scans across input and if:
  2. it sees a a and its top stack symbol is a it pops the stack
  3. it sees a b and its top stack symbol is b it pops the stack
  4. in all other cases it pushes the input symbol in to the stack
  5. after we finish the input if a or b is on top of stack we accept other wise we reject

How to Draw the state diagrams for this PDA ?

share|improve this question
I think you need to describe your states and state transitions? –  copper.hat Jun 17 '13 at 21:58
you may have a better hit on this on cs.stackexchange.com. –  ashley Jun 17 '13 at 23:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.