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.

$\endgroup$
4
  • $\begingroup$ Multiple pop can be simulated by adding additional states to keep track of the pop-ed symbols. $\endgroup$
    – Steven
    May 15 at 18:11
  • $\begingroup$ For every second $a$ that you read, push $BBB$ into the stack. $\endgroup$ May 15 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$ May 15 at 18:23
  • $\begingroup$ @YuvalFilmus exactly what i need thanks $\endgroup$ May 15 at 18:26

2 Answers 2

1
$\begingroup$

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

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

$\endgroup$

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.