A specific push down automaton for a language (PDA)-CodePudding

I'm wondering how could I design a pushdown automaton for this specific language. I can't solve this..

L2 = { u ∈ {a, b}∗ : 3 ∗ |u|a = 2 ∗ |u|b 1 }

So the number of 'a's multiplied by 3 is equals to number of 'b's multiplied by 2 and added 1.

CodePudding user response：

The grammar corresponding to that language is something like:

S -> ab | ba |B
B -> abB1 | baB1 | aB1b | bB1a | B1ab | B1ba
B1 -> aabbbB1 | baabbB1 | [...] | aabbb | baabb | [...]

S generates the base case (basically strings with #a = 1 = #b) or B

B generates the base case B1 (in every permutation)

B1 adds 2 'a' and 3 'b' to the base case (in fact if you keep adding this number of 'a' and 'b' the equation 3#a = 2#b 1 will always be true!). I didn't finish writing B1, basically you need to add every permutation of 2 'a' and 3 'b'. I think you'll be able to do it on your own :)

When you're finished with the grammar, designing the PDA is simple. More info here.

CodePudding user response：

3|u|_a = 2|u|_b 1 <=> 3|u|_a - 2|u|_b = 1

The easiest way to design a PDA for this is to implement this equation directly.

For any string x, let f(x) = 3|x|_a - 2|x|_b. Then design a PDA such that, after processing any string x:

The stack depth is always equal to abs( floor( f(x)/3 ) );
The symbol on the top of the stack (if any), reflects the sign of floor( f(x)/3 ). You only need 2 kinds of stack symbols
The current state number = f(x) mod 3. Of course you only need 3 states.

From the state number and the symbol on top of the stack, you can detect when f(x) = 1, and at that condition the PDA accepts x as a string in the language.