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

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.

• You can push a string $w \in \Gamma^*$, where $\Gamma$ is the stack alphabet – abc Mar 31 '17 at 13:43
• I think that, 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. So, it does not really matter, if we only care about the languages. – chi Mar 31 '17 at 13:49
• The answer is: take a look at the definition of PDA introduced in class. There are several possible definitions, and only you know which definition is the one your professor prefers. – Yuval Filmus Mar 31 '17 at 13:50
• A third option is to use multiple stack symbols encoding different things. – Raphael Mar 31 '17 at 17:27

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)
• A third option is to use multiple stack symbols encoding different things. (from Raphael's comment)

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

• This doesn't appear to answer the question. The question asks: "Can we push two symbols? Eg: for every a I encounter I push two symbols." - in other words, the question already mentions that approach, and is asking whether that is actually valid. So I don't see how this is addressing the question that was asked. – D.W. Jul 10 '17 at 3:39

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)$

• How does this answer the question? – Yuval Filmus Apr 9 '17 at 18:15