Push two symbols to stack at once in a push down automata

Question

I am pretty new to PDAs and I was solving a problem which asked to design a PDA for the following: $a^n b^{2n}$.

The transitions on the PDAs I've encountered so far have pushed only one symbol onto the stack at any time. Can we push two symbols? Eg: for every $a$ I encounter I push two symbols. Thus, the transition will be:

$\Delta(q_0, a,0;000) \to \Delta(q_0)$
where "$a,0;000$" indicates pushing two zeroes onto stack for every $a$ that it encounters.

Answer 1

There are some options (from comments):

• By some definition of PDA, you can push a string $w \in \Gamma^\ast$, where $\Gamma$ is the stack alphabet. _{(from abc's comment)}
• Even if you could push only one symbol per transition, you could modify your PDA to push the first -> move to a new state -> push the second -> continue as usual. _{(from chi's comment)}
• The third option is to use multiple stack symbols encoding different things. _{(from Raphael's comment)}

Answer 2

Just push 2 a in the stack for each a you see on the input, then pop 1 a for each b.

Answer 3

Here, the number of $b$s is twice the number of $a$s, so we have to push the $a$s in stack first. Once we start encountering $b$s, we transition on the first $b$ (but put nothing on the stack, just move to next state). After reaching the second $b$, pop the top $a$ as we transition on that $b$.

$z(q_0,a,z_0)\to(q_0,az_0)$

$z(q_0,a,a)\to(q_0,aa)$

$z(q_0,b,a)\to(q_1,a)$

$z(q_1,b,a)\to(q_2,E)$

$z(q_2,b,a)\to(q_1,a)$

$z(q_2,E,z_0)\to(q_f,z0)$