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 q0 to q0 in which the input symbol 1 is read and pushed to the stack.
in a) x2xR
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 q0 to q0 add 0,s/0.s
and on edge q1 to q1 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?
$\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.
On a lighter ...