# Some questions regarding methods for solving pushdown automata problems

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

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?

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.