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.
- The PDA scans across input and if:
- it sees a a and its top stack symbol is a it pops the stack
- it sees a b and its top stack symbol is b it pops the stack
- in all other cases it pushes the input symbol in to the stack
- 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 ?