Pushdown automata for $\left\{ a^nb^mc^{n+m} \colon m,n \in \mathbb{N}_0 \right\} $

Question

I am having trouble finding the pushdown automata for $\left\{ a^nb^mc^{n+m} \colon m,n \in \mathbb{N}_0 \right\} $. I tried starting off with the grammar: $$ S \rightarrow aSC | aBC | bBC | \epsilon$$ $$ B \rightarrow bBC | \epsilon $$ $$ C \rightarrow c$$

Is the grammar ok? I don't know how to write the pushdown automata because od the $\epsilon$-s, also I am having trouble with interpreting $ S \rightarrow aSC $ in the pushdown automata table ($z_0 = S$, beginning state: $q_0$). Does it go: $$ state: q_0, entry: a , top \: of \: the \: stack: z_0, new \: state:q_1,new \: stack: z_0Cz_0 $$ This does not seem right.

Answer 1

Your grammar looks correct.

Any grammar in that form can be turned into a pushdown automata as follows:

1. The machine has exactly one state $q$. The machine's stack initially contains the start symbol $S$.

2. In my notation, a rule like $$\delta(q, X)\xrightarrow{a}(q^\prime,Y)$$ means: If you're in state $q$ and you've just popped $X$ off of the stack and you read the next character $a$ from the input (or didn't read anything, if it's a rule like $\xrightarrow{\epsilon}$), you may transition to state $q^\prime$ and push $Y$ onto the stack. Some rules don't push anything new onto the stack, in which case I write $(q^\prime, -)$ instead.

3. You can read a character from the input if it matches the character on top of the stack. (This pops that character from the top of the stack, and doesn't add anything to the stack.) $$\delta(q, a)\xrightarrow{a} (q,-)$$

4. Whenever a nonterminal character $A$ is on top of the stack, nondeterministically pick one of the productions like $A\to B_1B_2B_3$. Push the right-hand symbols onto the stack in order so that $B_1$ is on top and $B_3$ is on the bottom. (This is an $\epsilon$ transition because it doesn't read any input characters.) $$\delta(q, A) \xrightarrow{\epsilon} (q, B_1B_2B_3)$$

5. As a special case of (3), when you have a nonterminal character $A$ and you pick the rule $A\rightarrow \epsilon$, the transition will simply pop $A$ off the stack without adding anything new: $$ \delta(q,A) \xrightarrow{\epsilon} (q, -)$$

6. If the machine's stack is ever empty, then it accepts the string. If the machine can't empty its stack, it rejects the string.

---

In particular, your grammar can be turned into a pushdown automaton with one state $q$ and the rules: \begin{align*} \delta(q, S)&\xrightarrow{\epsilon}(q,-)\\ \delta(q, S)&\xrightarrow{\epsilon}(q,aSC)\\ \delta(q, S)&\xrightarrow{\epsilon}(q,aBC)\\ \delta(q, S)&\xrightarrow{\epsilon}(q,bBC)\\ \delta(q, B)&\xrightarrow{\epsilon}(q,bBC)\\ \delta(q, B)&\xrightarrow{\epsilon}(q,-)\\ \delta(q, C)&\xrightarrow{\epsilon}(q,c)\\ &\\ \delta(q, a)&\xrightarrow{a}(q,-)\\ \delta(q, b)&\xrightarrow{b}(q,-)\\ \delta(q, c)&\xrightarrow{c}(q,-)\\ \end{align*}