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.
A Thing to note here is s is anything or like any symbol on the top of the stack so whatever the top of the stack .S represents in that way not any special symbol of the language
AND
(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)
($ \epsilon$ is used to denote pop operation, $Z$ is the starting symbol on stack)
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?
@Puja,
It is maintaining n ≤ m ≤ 2n by using the 2nd choices for the first 2 IDs (in Bold)-
(q0,0,z0) |---- (q0,0z0) or (q0,00z0)
(q0,0,0) |---- (q0,00) or (q0,0000)
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.
@Arjun
Sir , I think this answer needs review this accepts string 00000011 which it should not be
@saurav04
What ayush said is true...
Transition in the answer is pushing 3 0's onto stack while we should be pushing only 2 0's.
Your answer would've been correct if they have asked for n<=m<=3n..
Please check it
Just drawing what's written in answer by @@saurav04 sir.
@avraw In that case one can simply add another state q2 from q1 where ∊,z/∊.
a)
b)
$\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.
a
on the state q0 edge from q0 to q0 add 0,s/0.s0,s/0.s and on state q1 edge from q1 to q1 add 0,0.s/s
64.3k questions
77.9k answers
244k comments
80.0k users