1.7k 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 $q_0$ to $q_0$ 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

edited | 1.7k views

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$

by Veteran (57k points)
edited
+3
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..
0
@praveen sir ,pls verify once s is content of stack or only stack symbol
0
nitish is right.
+1
In the diagram of a PDA which accepts by empty stack, there's no accept state, right?
+2
@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)

by Active (1.6k points)
edited by
+1

i dont think it is maintainning nm2n this...

+3
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.
0
right sir 00001 accepted which should'nt but if i remove last 2 transition then how can i maintain empty stack property?
+6
String will be accepted if stack is empty- not otherwise. You don't have to do anything. Non-determinism will take care of it..
0
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. 0 in the solution why the same state q0 is maintained in both the transitions?? 0 @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? 0 How it i is maintaining n ≤ m ≤ 2n this ... 0 @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. +3 I think the second transition must be of the form$\delta(q_0,0,0)=\{(q_0,00),(q_0,000)\}$instead of$\delta(q_0,0,0)=\{(q_0,00),(q_0,0000)\}$0 @Arjun Sir , I think this answer needs review this accepts string 00000011 which it should not be 0 @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 0 Just drawing what's written in answer by @@saurav04 sir. +11 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.

by Loyal (5.5k points)
edited by
0
What software did you use to construct this?
+1
This is mentioned in Peter Linz's book: http://www.jflap.org/