# How to generate a pushdown automata for accepting a language?

I have an exercise in my book to come up with a pushdown automaton accepting a language.

The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings over $\{a, b\}$ with middle symbol $a$.

Here's what I have so far...

I wasn't sure how many states I needed, but I was thinking 3. State $q_0$ for pushing symbols onto the stack until reaching the middle symbol, $q_1$ for after middle symbol is found, and state $q_2$ the accepting state. I think in $q_1$ I need to cancel out input symbols from the stack with the input. I don't know how to account for the string being odd length, also.

Is there a smart, systematic way to do this?

• You sometime need to switch from "accumulating on stack" to "eating the stack"... and as it is on $\{a, b\}$ with a middle $a$, this has to be nondeterministic. Apr 4 '13 at 19:07
• If you have "guessed" the middle letter right (with equal numbers of letters before and after) you need not worry about odd length, as that is automatically taken care of. Apr 4 '13 at 20:12