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

Zoomed imge

3 Answers

+14 votes

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

answered by Veteran (53.9k points)
edited ago 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.
+7 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.5k 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 ...
0 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 Boss (5.5k 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

32,443 questions
39,188 answers
36,563 users