A push down automation (pda) is given in the following extended notation of finite state diagram:
The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form $d$, $s/s'$ where $d$ is the input symbol read and $s, s'$ are the stack contents before and after the move. For example the edge labeled $1, s/1.s$ denotes the move from state $q_0$ to $q_0$ in which the input symbol $1$ is read and pushed to the stack.
In a) $x2x^R$
Say for some word $0112110$ we have to push every thing into the stack till $2$ . then we get $1$ then $1$ will be at top of stack so pop it or if get $0$ then $0$ will at top of stack so pop it. For any word of language it is applicable. $2$ is a mark that tell now we have to pop $0$ for $0$ and $1$ for $1$.
So, on the edge $q_0$ to $q_0$ add $0,s/0.s$
and on edge $q_1$ to $q_1$ add $0,0.s/s$
part(b) e is epsilon(to denote pop operation)
(q0,0,z0) |---- (q0,0z0) or (q0,00z0)
(q0,0,0) |---- (q0,00) or (q0,0000)
(q0,1,0) |---- (q1,e)
(q1,1,0) |---- (q1,e)
i dont think it is maintainning n≤m≤2n this...
@Arjun sir. I have a doubt here.
δ(q1,∊, z0) |---- (q1,∊) . This transition is required, right? otherwise, how stack top symbol will be popped? And if it is not popped then how stack will be emptied?
It is maintaining n ≤ m ≤ 2n by using the 2nd choices for the first 2 IDs (in Bold)-
They have been used to bound the n values to a maximum of 2n, using the non-determinism as asked in the question.
It should also have δ(q1,∊, z0) |---- (q1,∊) for the 2nd state for empty stack acceptance.
Sir , I think this answer needs review this accepts string 00000011 which it should not be
$\lambda$ in the stack part is used to indicate "whatever be the input". And the additional $(\lambda,Z,\lambda)$ was added to pop the initial symbol from the stack.
What should be the answer of question 1 in C...