Search code examples
computer-sciencestate-machineautomatacomputation-theoryautomata-theory

How to create a pushdown automata which accepts a language?

enter image description hereenter image description here

Can someone please explain to me how to create pushdown automata for this language. I don't understand the set notation for the language if you could explain that would be great too. Thank you

Solution

  • The notation means: the language which consists of all the words that start with n letters a followed by m letters b; further, the numbers n and m must not be equal.

    The obvious way to accept this with a PDA is this: From the start, for every a you read you put one on the stack; when you start seeing b, for every b you read you remove one of the a from the stack. If the last b removes the last stack symbol, then n=m and the PDA should reject; otherwise, if the word is from ab it should accept.