Question

Draw PDA transition diagram for the following language:

The set of strings over the alphabet {x, y} where 2 * (# of x's) = 3 * (#y's)

That is, if we let n_x be the number of x's and n_y be the number of y's, then the strings in these language are those where 2n_x = 3n_y

Try to find a PDA that is as simple and elegant as possible (do not convert from CFG).

------------------------------------------------------------------------------------------------------------------

USE Notation between transition:

for example x, a -> ε means read x, pop a and push ε

Answer 1

Given:

strings that can be generated by using this language must satisfy 2n_x = 3n_y

If n_x = 3 and n_y = 2 , 2* 3 = 3* 2, 6 = 6.

So the string For n_x = 3 and n_y = 2 the possibilities may be xxxyy, yyxxx, xyyxx, xxyyx, yxxxy, yxyxx, yxxyx, xyxyx, xyxxy, xxyxy.

Step 1:

If the y is first in string, push yy because n_x is greater than n_y .

if the x is first in string, push only x.

Step 2:

If the top of the stack is x and x is called, push xx. So, it cancels one x and adds one x to the stack.

If the top of the stack is y and y is called, push yy. So, it cancels one y and adds one y to the stack.

Step 3:

Suppose, if the top of the stack is x and y is called, pop x. (It gets cancels on each other)

Similarly if the top of the stack is y and x is called, pop y. (It gets cancels on each other)

step 4:

when string is finished and is called, Now the top of the stack must be Z₀. The final state q₁ is reached.