Gate@zeal Test Series 2022

Question

 Please explain with simplified diagram the transition in the pda. Ans (d)

 

Answer 1

Answer: (d)
Just see the diagram,

State q1 – q2: Push $ on the top of the stack,

State q2: On getting 0 or 1 in the input push it on the top of the stack

State q2 – q3: On getting 0 or 1 in the input don’t push anything on stack just go to state q3. 

State q3: On getting 0 in the input if top of the stack is 0 pop it, similarly on getting 1 in the input if top of the stack is 1 pop it.
State q3 – q4: If top of the stack is $ pop it and go to q4 and accept the input string.

Now notice string will be a palindrome, example
01010

Initially 0 and 1 are pushed on to the stack. Now on 0 it will go to the state q3. 1 is on the top of the stack and next input is also 1 so it is popped off. Similarly 0 will pop. Now top of the stack is $ so it will move from state q3 to q4 and string is accepted.

Why length of palindrome can’t be even?

Let’s assume we push $x$ number of alphabets on to the stack, we need one alphabet to go from state q2 to q3 in order to pop alphabets from the stack. And we need to pop $x$ alphabets.

Therefore total alphabets in input string should be $x + 1 + x = 2x + 1$ which is odd.