1
$\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$
  • 3
    $\begingroup$ You can push a string $w \in \Gamma^*$, where $\Gamma$ is the stack alphabet $\endgroup$ – abc Mar 31 '17 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 '17 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$ – Yuval Filmus Mar 31 '17 at 13:50
  • $\begingroup$ A third option is to use multiple stack symbols encoding different things. $\endgroup$ – Raphael Mar 31 '17 at 17:27
1
$\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)
  • A 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
    $\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 '17 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
    $\begingroup$ How does this answer the question? $\endgroup$ – Yuval Filmus Apr 9 '17 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.