1
$\begingroup$

I am trying to create a PDA with at most 7 states that accepts the following language over the alphabet $\Sigma = \{a,b\}$:

$$ \{a^{2k}b^{3k} \mid k \geq 0\} $$

The tricky part is that multiple push allowed but multiple pop is not allowed. I was able to find the easy solution when multi push/pop is allowed. I am looking for solutions where multi push/pop is not allowed and multi push is allowed but multi pop is not allowed.

Improve this question
$\endgroup$
4
  • $\begingroup$ Multiple pop can be simulated by adding additional states to keep track of the pop-ed symbols. $\endgroup$
    – Steven
    Commented May 15, 2022 at 18:11
  • $\begingroup$ For every second $a$ that you read, push $BBB$ into the stack. $\endgroup$
    – Yuval Filmus
    Commented May 15, 2022 at 18:20
  • $\begingroup$ my stack alphabet is a single character, i tried to simulate k multi-pop by adding k additional state, i use epsilon transitions between these states and pop per each state. i guess it should work. thanks for the tip $\endgroup$
    – Utku Kalkanlı
    Commented May 15, 2022 at 18:23
  • $\begingroup$ @YuvalFilmus exactly what i need thanks $\endgroup$
    – Utku Kalkanlı
    Commented May 15, 2022 at 18:26

2 Answers 2

Reset to default
1
$\begingroup$

For every second $a$ that you read, push $BBB$ into the stack.

Improve this answer
$\endgroup$
1
$\begingroup$

Here is another solution. For every $aa$ you could check every $bbb$(skips first $b$, keep stack's present top $a$ as it is and pop $2a$ against for last $2b$).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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