Answer would have been C if question did not have any mistakes.
Explanation : odd length palindrome has format $WaW^r$ or $WbW^r$ and transition is denoted as input,stacktop| new stack top
e.g 1. a,a|aa means on input a if top is a then push a : top becomes aa
- a,a|$\epsilon$ means on input a if top is a then pop : top becomes empty $\epsilon$
- a,a|a means on input a if top is a then pass/no operation : top stays same a
We need to make a NPDA as middle character is not unique. (like c or something else then DPDA will be possible)
Now,
- The link from $X\rightarrow A$ there is an error , the transition should be $\epsilon,\epsilon | Z$ meaning insert Z in empty stack or alternatively $a,Z | aZ$ and $b,Z|bZ$ meaning push first symbol.
- The self loop on $A$ pushes any input to stack irrespective of previous top.
- After that we should “assume”(non determinism) that next input is middle letter which we don’t care what it is just skip it meaning
perform no operation on stack for middle element.
Means on input anything(a or b) if top is anything(a or b) then pass/no operation thus transitoins $A\rightarrow B$ will be : $(a,a|a)(b,a|a)(a,b|b)(b,b|b)$
- The self loop on $B$ pops stack if input and stack top is matching, if it doesn’t that instance of NPDA will terminate. This termination will occur for all those wrong “assumptions” we made about next symbol while we were at state $A$ and only true middle symbol will not cause this termination in string that should get accepted.
- Transition $B\rightarrow C$ means on input $ (end of input) if top is z then pop and go to final state $C$.
