836 views

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.

1. Introduce two edges with appropriate labels in the above diagram so that the resulting pda accepts the language $\left\{x2x^{R} \mid x \in \left\{0,1\right\}^*,x^{R} \text{ denotes reverse of x}\right\}$, by empty stack.
2. Describe a non-deterministic pda with three states in the above notation that accept the language $\left\{0^{n}1^{m} \mid n \leq m \leq 2n\right\}$ by empty stack
retagged | 836 views

Zoomed imge

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

edited ago
sir, here in 0,s/0.s..

's' is not any symbol, it means anything that is on top of stack, no matter what is it???...beacuse if it is not so we require more transitions..
@praveen sir ,pls verify once s is content of stack or only stack symbol
nitish is right.
In the diagram of a PDA which accepts by empty stack, there's no accept state, right?
@shraddha there should be one more transition on q2, eps| stackSymbol| eps, but seems it's some hypothetical PDA and they don't have any stack symbol at the bottom of the stack. so once input is a member of the language and when input is finished stack will be empty.

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)

edited by

i dont think it is maintainning nm2n this...

The no. of 0's in stack is between no. of 0's in string and its double (all possible due to non-determinism). Now, the string is accepted if the no. of 1's in string matches the no. of 0's on stack.

@saurav you have to remove the last 2 transitions. Otherwise strings like 00001 will be accepted.
right sir 00001 accepted which should'nt but if i remove last 2 transition then how can i maintain empty stack property?
String will be accepted if stack is empty- not otherwise. You don't have to do anything. Non-determinism will take care of it..
can we do it like this: for each 0 push two zeroes.When a 1 comes pop 2 0s.If stack becomes empty and there are still 1 left keep on reading it or in other words do nothing just read them till input gets over.Or if $is reached and top of stack is s then also accept it. in the solution why the same state q0 is maintained in both the transitions?? @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? How it i is maintaining n ≤ m ≤ 2n this ... 0 votes 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.