1
$\begingroup$

I have found some problems whose solving "patterns" appear quite recently, and I am not sure if the way I'm solving them is the most correct/efficient one:

For example, take this language:

$\{w | w\in\{a,b,c\}^* \text{ with }|w|_a=|w|_b \text{ or } |w|_b=|w|_c\}$

The solution would be as follows, where $\\\$$ is the bottom of the stack, and $\epsilon$ the empty string:

The top part is $|w|_a=|w|_b$ and the bottom is $|w|_b=|w|_c$

Taking the top part as an example (the other one is almost identical), what I do is to push $A$ whenever $a$ is read and $A$ is in the top of the stack, or remove $B$ if $B$ is in the top.

Whenever $b$ is read, I push $B$ if I don't find any $A$'s, or remove an $A$ if it's found.

Then, the rest of the characters without restrictions are read between those, leaving the stack alone.

The string would be accepted if input stops and the stack is empty.

I am not sure if this is the most graceful solution since I basically cram all possible cases in one state, though I think this works. This pattern is used basically whenever I find a restriction such as $|w|_x=|w|_y$

enter image description here


The other pattern I found that I'm unsure about is the following one, taking this language as an example:

$\{a^nb^m | n=3m\}$

In this one, I push one symbol into the pile only whenever 3 consecutive $a$'s are read, which will be then equal to $m$ and be consumed by reading $b$'s, accepting the string again if input is done and the stack is empty.

In these cases, I create a series of states where there is only one symbol pushed (when we enter into them), and the rest force to read a certain number of symbols without pushing of popping anything.

I am uncertain if this is the good way to do it. What if it were to be $n=56m$, would I need 55 sub-states?

enter image description here

$\endgroup$
1
$\begingroup$

Your first solution is fine. I would not call this cramming into one state, it is kind of elegant to handle all this at the same place.

For your second problem, yes you can add 55 extra states. But also here you can use a single state instead, by coding that state into the topmost stack symbol. Simply have many stack symbols $A_0$, $A_1$ to $A_{55}$ (or so) and replace $A_i$ by $A_{i+1}$ until 56 is reached.

In general every pushdown automaton can be replaced by one having at most two states.

$\endgroup$
1
  • $\begingroup$ I see, thank you very much! I hadn't thought of using more symbols... $\endgroup$ – Lightsong Dec 30 '20 at 20:14

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.