The Gateway to Computer Science Excellence
+24 votes

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
in Theory of Computation by Veteran (52.2k points)
edited by | 1.7k views

3 Answers

+19 votes

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 by
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.
+15 votes

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

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 ...


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.

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)\}$


Sir , I think this answer needs review this accepts string 00000011 which it should not be



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.

+11 votes



$\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
What software did you use to construct this?
This is mentioned in Peter Linz's book:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,384 answers
105,331 users