0
$\begingroup$

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...

enter image description here

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – vonbrand
    Apr 4, 2013 at 19:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hendrik Jan
    Apr 4, 2013 at 20:12

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.