Context-free grammar to a pushdown automaton

Question

I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have on a homework that's due later today, so I'd appreciate some kind of help, even if it's just an explanation of the correct answers diagram. I need a PDA corresponding to this CFG:

$$S \rightarrow aSa | bSb | B$$ $$B \rightarrow bB | \epsilon$$

I know it will have to push X every time 'a' is read before a 'b', and pop X every time 'a' is read after a 'b'. But I'm not sure how to arrange the PDA in order to tell which a's came after b's. Also, I'm unsure of how to deal with the b's in terms of the stack, as there can be as many in the middle of the string as you want. Help appreciated.

Thanks, Pachun

Answer 1

This is basically the language of all palindromes over $\{a, b\}$ which can contain an arbitrary number of $b$'s in the middle. First, you could build a PDA for palindromes. This is a fairly standard language, so you should be able to find plenty to get you started. Then, you need to add a way to read an arbitrary number of $b$'s after you're done pushing new symbols to the stack, and before you start popping symbols. So the basic steps here:

1. Read $a$'s and $b$'s and push to the stack;
2. Read any number of $b$'s;
3. Read $a$'s and $b$'s and pop from the stack.

Please let me know if you need more guidance. Note that you're going to need to use nondeterminism here, so don't worry about it. This is a not a deterministic language (unless I'm mistaken... which has happened before).