2
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ You can push a string $w \in \Gamma^*$, where $\Gamma$ is the stack alphabet $\endgroup$
    – abc
    Mar 31, 2017 at 13:43
  • 3
    $\begingroup$ 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. $\endgroup$
    – chi
    Mar 31, 2017 at 13:49
  • 3
    $\begingroup$ 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. $\endgroup$ Mar 31, 2017 at 13:50
  • $\begingroup$ A third option is to use multiple stack symbols encoding different things. $\endgroup$
    – Raphael
    Mar 31, 2017 at 17:27

3 Answers 3

3
$\begingroup$

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)
$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Jul 10, 2017 at 3:39
-1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ How does this answer the question? $\endgroup$ Apr 9, 2017 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.