How to generate a pushdown automata for accepting a language?

Problem Detail: 

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?

Asked By : badjr

Answered By : vonbrand

Designing an PDA (or a NFA, DFA, or any other automaton) is essentially programming (in a weird, extremely limited language). Just as there is no sure-fire way to write a program from some description, there isn't for automata either. The only way of becomming proficient is to practice. You'll find plenty examples here...

For some cases there is a way of translating a more human-readable description of the language into an automaton, like starting with a regular expression and getting an NFA, massage that one and you'll finally get the minimal DFA; or starting with a context free grammar and constructing a PDA. The results aren't always exactly pretty, but guaranteed to work.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11023