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 | win{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?
