I have to design a PDA that recognizes the language:
$$L=\{w \mid \#(a,w) - 3\#(b,w) = 2\} $$
where $\#(a,w)$ means the number of letters $a$ in $w$
My idea is to count $a$'s and $b$'s. I have to consider two cases:
1. I'm counting $b$'s on the stack
2. I'm counting $a$'s
If I'm counting $b$'s, I push three $b$'s every time I see one. When I see a I just pop one $b$ for each $a$. If I'm counting $a$'s, I push one every time I see one. When I see $b$ I pop three $a$'s.
But I'm not sure how to write it formally.
Do I need additional states to pop three $a$'s. Because with one move I can pop only one item from the stack.
Special character onto the bottom of the stack:
$$ <q_0, \epsilon , \epsilon, q_1,\#> $$
The stack is empty, I've got $a$, so push it.
$$ <q_1 , \# , a,q_1,a>$$
Now I need to add three $b$'s. Do I need additional states like that:
$$<q_1,\#, b,q_{b1} ,b>$$
$$<q_{b1},b, \epsilon,q_{b2} ,b>$$
$$<q_{b2},b, \epsilon,q_{1} ,b>$$
Or is it possible to write $q_1$ instead of $q_{b1},q_{b2}$ (epsilon transitions)?
How to check if at the end of the word, there are only two letters a on the stack?
Note: Maybe you have to clarify whether the PDA is deterministic. Here my answer is based on non-deterministic PDA, or simply CFG.
For a $w\in\{a,b\}^*$, define $$D_i=\#(a,w[1,i])-3\#(b,w[1,i])$$ and consider the gragh of this sequence. The trick here is always thinking of the first time when the polyline of $D_i$ comes across a certain horizontal line. For instance, if we denote the string $w$ which satisfies $\#(a,w)-3\#(b,w)=q$ by the symbol $S_q$, we have the production: $$S_2\rightarrow S_0aS_1$$ since we can think of the first time when $D_i=1$, and it must be the case that the polyline come across the line $D_i=1$ from below, indicating the occurence of a character $a$.
Similarly, we have the following productions which compose a complete grammar: $$\begin{eqnarray} S_0&\rightarrow& \epsilon \mid bS_3\mid aS_2bS_0\mid aS_1bS_1\mid aS_0bS_2 \\ S_1&\rightarrow& S_0aS_0 \\ S_2&\rightarrow& S_0aS_1 \\ S_3&\rightarrow& S_0aS_2 \end{eqnarray}$$
Each one of $\{S_0,S_1,S_2,S_3\}$ can be regarded as the starting symbol, resulting in a corresponding language. In fact, if you elaborate on the above technique, you can prove the following statement:
Statement: Given $p,q\in\mathbb{Z}$, $p>0$, the language $\{w\mid \#(a,w)-p\#(b,w)=q\}$ is a context free language.