PDA for this context-free grammar

Question

I have the following CFG $G$: $$ \begin{align} S &\rightarrow aAbb \mid aaBb \\ A &\rightarrow aAbb \mid \epsilon \\ B &\rightarrow aaBb \mid \epsilon \\ \end{align} $$

I have to create a PDA (pushdown automaton) to recognize this language however I am unsure on how to do it. So far I have this(revised based on feedback from user Hendrik Jan) :

I understand that it should accept the last one ($aaaabb$) however it does not for the current version.

Answer 1

From CFG to PDA is a simple construction. Set axiom $S$ as initial pushdown symbol. If the topmost symbol of the stack is nonterminal replace it according to a production of the grammar. If the topmost symbol is a terminal we are forced to read the same symbol from input tape (and pop the symbol). That is called expand-match. See wikipedia. The resulting PDA is single state, acceptance by empty stack.

(added) Your problem is on a special type of grammar, linear context-free. That means in every step of the derivation there is exactly one nonterminal. You can mimic this using a different construction. Basically the nonterminal is the state. All terminal symbols to the left are read, those to the right are pushed, to be read later. For $S\to aaBb$ the PDA goes from state $S$ to state $B$ while reading $aa$ (in usual models that takes two steps) and pushing $b$.

On your construction (it seems of the latter type). Concretely: the grammar generates $a$'s and $b$'s in a two-to-one / one-to-two ratio. In general: in order (for yourself) to see why it doesn't work you have to try to formulate the meaning of the states. How do they relate to things happening in the grammar?

Answer 2

While Hendrik Jan's answer is totally spot-on, it's worth noting that you don't always need to follow the algorithmic construction to get a PDA. If you can decide via analysis what the language is, you can often come up with a machine more easily.

The grammar you give generates $a^nb^{2n} \cup a^{2n}b^n$ where $n > 0$. In particular, any construction which uses the rule $S \rightarrow aAbb$ will generate a string in $a^nb^{2n}$, and any construction using the rule $S \rightarrow aaBb$ will generate a string in $a^{2n}b^n$.

Therefore, a simple procedure to obtain a correct PDA is the following:

1. Create a PDA $M_1$ to recognize $a^nb^{2n}$ for $n > 0$.
2. Create a PDA $M_2$ to recognize $a^{2n}b^n$ for $n > 0$.
3. Create a PDA $M$ which recognizes $L(M_1) \cup L(M_2)$.

Each of these steps is significantly easier than trying to create a PDA from the original grammar, in my opinion, anyway.

For (1), push two $a$'s onto the stack for each $a$ you read, then pop an $a$ each time you read a $b$. Accept if the stack is empty once the input is gone.

For (2), push an $a$ for every two $a$'s you read, then pop an $a$ for each $b$ you read. Accept if the stack is empty once the input is gone.

For (3), you can create a new initial state and non-deterministically jump to the initial state of either $M_1$ or $M_2$ without consuming any input or putting anything on the stack. This will ensure that if your input represents a string accepted by either of the automata, then there will be a path that accepts the input.