Question

Construct a PDA that matches all strings in the language over {x,y} such that each string has at least twice as many y's as x's.

Below, give a short description of the set of strings associated with each state of your PDA.

Answer 1

sol:It is given that in each string there must be atleast twice the no of y's as many x's.

Examples-xyy,xxyy,xyxy,xyyy,yyx,yxy ... and many more strings of this pattern.

  

LOGIC:

i) For every x or y encountered on the input tape

1)If the stack is empty or top of the stack has same letter as that of the letter at the input tape -

i)Push 2 x's if the letter is x.

ii)Push only one y if the letter is y.

2)If the top of the stack has different letter as that of the letter at the input tape

i)Pop 2 y's if the top of the stack is y and and input tape has letter x.If the top of the stack has only one y then pop y and push one x.

ii)Pop one x if the top of the stack is x and input tape has letter y.

3)Final state-Stack must be either empty or it must have only y at the top of the stack.

Note:- delta(state,input,stack)=(newstate,new stack Symbol) for the below rules.