The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 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
asked in Theory of Computation by Veteran (59.8k points)
edited by | 1.3k views

Zoomed imge

3 Answers

+15 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$

answered by Veteran (55.9k 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.
+10 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)

answered 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

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

answered by Active (4.9k points)
edited by

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,068 questions
53,206 answers
70,419 users