Dark Mode

Recent questions tagged pushdown-automata

8 votes

3 answers

151

True or False Question regarding DPDA and prefix property
a) A DPDA which accepts by empty stack cannot accept all Regular Languages? b) All Regular Languages doesn't satisfy prefix property?

iarnav asked in Theory of Computation Sep 16, 2017

by iarnav

5.4k views

2 votes

3 answers

152

What is Prefix Property in TOC?
Can someone explain what's this prefix property, there's no proper explanation on google and may you please explain with taking some examples. Thanks.

iarnav asked in Theory of Computation Sep 15, 2017

by iarnav

4.6k views

0 votes

2 answers

153

How to draw PDA for given Language?
$L=\{a^nb^n\mid n≥0\}$ Kindly draw a PDA for this, I'm confused, how to deal with epsilon string?

iarnav asked in Theory of Computation Sep 15, 2017

by iarnav

959 views

0 votes

2 answers

154

General Topic Doubt Theory of Computation: Context Free Language
I am confused in understanding DPDA and NPDA..........Also DCFL and CFL......bcz these are quit similar in looking so please explain in such a way that I 'm able to understand them well......thanks

sudhir singh asked in Theory of Computation Sep 9, 2017

by sudhir singh

370 views

0 votes

1 answer

155

TOC PDA
construct a pda fora^mb^n such that m=2n+1?

akshat16 asked in Theory of Computation Sep 7, 2017

1.1k views

1 vote

3 answers

156

PDA =FA+1stack??
we know that PDA = FA+1stack so why we use the stack data structure in PDA, we have much more data structure like linked liste,queue, array or tree/hashing???

Hira Thakur asked in Theory of Computation Sep 1, 2017

778 views

2 votes

0 answers

157

Prefix property and DPDA
Construct the DPDA with empty stack and final state method for the language L = ${ a^n b^n / n>= 0}$.

Shubhanshu asked in Theory of Computation Aug 28, 2017

2.6k views

1 vote

1 answer

158

Deterministic Push Down Automata
What is main difference between Deterministic Push down automata and simple Push down automata ?

ashutoshaay26 asked in Theory of Computation Aug 15, 2017

by ashutoshaay26

1.1k views

1 vote

0 answers

159

Push Down AUTOMATA
which PDA is more Powerful Deterministic or Non Deterministic and why?

Sunil8860 asked in Theory of Computation Aug 12, 2017

342 views

2 votes

2 answers

160

Test by Bikram | Theory of Computation | Test 2 | Question: 24
Consider the following Pushdown Automata Transition Function $\delta$ : 1. $\delta ( q_0 , \epsilon, z_0 ) = ( q_0 , \epsilon)$ 2. $\delta ( q_0 , 0, z_0 ) = ( q_0 , xz_0 )$ 3. $\delta ( q_0 , 0, x ) = ( q_1 , x)$ ... $\{0^{2n} 1^n \mid n \geq 0\}$ $\{0^{2n} 1^{2n} \mid n \geq 0\}$

Bikram asked in Theory of Computation Aug 12, 2017

by Bikram

526 views

1 vote

0 answers

161

How to construct a PDA for the language {a^mb^n:m<2n<3m}

Durgesh Singh asked in Theory of Computation Aug 11, 2017

by Durgesh Singh

1.2k views

1 vote

1 answer

162

Design PDA for
Design PDA for i) L={a^n b^m c^n|m,n>=1} ii) L={a^m b^n c^p|m+n=p} iii) L={a^i b^i c^j|i,j=1} iv) L={a^i b^j c^j|i,j>=1} I have made an attempt to draw pda Please can someone crosscheck the answer?

pricool84 asked in Theory of Computation Aug 6, 2017

2.0k views

1 vote

1 answer

163

TOC PDA
True/False 1. In PDA, if Final state = phi(empty) ,then language accepted =phi. 2. In PDA, if Final state != phi(empty) ,then PDA will always accept at least one string..

rahul sharma 5 asked in Theory of Computation Aug 2, 2017

by rahul sharma 5

588 views

1 vote

1 answer

164

Basic Dount in PDA functioning
Assume my language is WW^R (Palidromes) Now when we use PDA for this,we will guess middle everytime.It can be middle or it cant be middle,so a new branch is created everytime.Now each branch will get the current stack picture and starts its ... that branch fails,we need to proceed further but how single stack is able to manage this scenerio? Can some one explain this?

rahul sharma 5 asked in Theory of Computation Aug 2, 2017

by rahul sharma 5

181 views

1 vote

1 answer

165

TOC DPDA vs NPDA
How many stacks are available with DPDA and NPDA? I assume it is 1 with DPDA and n with NPDA where n is some constant. Assume i have a language ,over alphabet a,b,c,dL=( W |n(a)=n(b) and n(c)=n(d) ),where n(a) is number if a in words. It is a CFL. Now can DPA handle this ?If yes,then how?If not,then why?

rahul sharma 5 asked in Theory of Computation Jul 31, 2017

by rahul sharma 5

1.9k views

3 votes

3 answers

166

Following language: L = {a^n b^n c^n d^n , n ≥ 1} ,How it is CSL and not CFL?
My understanding : We can create PDA as follows for every 'a' push operation and on 'b' pop operation and again on 'c' push operation and on seeing 'd' pop operation. please correct me , if i am wrong. I am sorry, if it is not important. Thanks lot :)

sunil sarode asked in Theory of Computation Jul 11, 2017

by sunil sarode

10.6k views

2 votes

1 answer

167

Peter Linz Edition 4 Exercise 7.1 Question 3.c,3.d,4.f,4.j (Page No. 183)
Q3) Given, $L_1 = (aaa^*b)$ $L_2 = (aab^*aba^*)$ Find (c) the union of $L_1$ and $L_2$, and also find (d) $L_1 - L_2$. Q4) Find the npda's of the following: f) $L = \{ a^nb^m :n \leq m \leq 3n\}$ j) $L = \{w : 2n_a(w) \leq n_b(w)) \leq 3n_a(w) \}$.

Shubhanshu asked in Theory of Computation Jul 8, 2017

1.9k views

2 votes

2 answers

168

Doubt whether given language is CFL?
L={a^n b^(2n+1) | n>=1} Also can you give acceping PDA diagram...plz

Veeplob Singh asked in Theory of Computation Jul 6, 2017

by Veeplob Singh

865 views

0 votes

2 answers

169

NPDA and DPDA
Can we make NPDA? L= {anbn| n>=0,a,b are input variables} if yes then make it .

akankshadewangan24 asked in Theory of Computation Jul 6, 2017

by akankshadewangan24

2.4k views

1 vote

0 answers

170

#pda #tm #deterministic
How can a DTM can simulate a NTM, but a DPDA can not simulate a NPDA. ? Reason? I read the proedure for a DTM to simulate a NTM but can not get why its not so with pda. Any clue ?

Shivansh Gupta asked in Theory of Computation Jul 6, 2017

by Shivansh Gupta

344 views

0 votes

1 answer

171

Language which is not a CSL but can be accepted by TM
Can anyone give me an example of a language which is not a CSL but can be accepted using a Halting TM?

Xylene asked in Theory of Computation Jun 15, 2017

by Xylene

1.5k views

4 votes

1 answer

172

Peter Linz Edition 4 Exercise 7.1 Question 4.h(Page No. 183)
Construct npda for the following languages on $∑ =$ {$a,b,c$} $L =$ { $w : n_a(w) = 2*n_b(w)$ }

Vishal Goel asked in Theory of Computation Apr 30, 2017

1.8k views

12 votes

1 answer

173

ISI 2015 PCB C4 A
Design a context free grammar for the language consisting of all strings over $\mathbf{\{a,b\}}$ that are not the form $\mathbf{ww}$ for any string $\mathbf{w}$

Devasish Ghosh asked in Theory of Computation Mar 9, 2017

by Devasish Ghosh

1.4k views

1 vote

1 answer

174

PDA..
Plz describe your ans too

srestha asked in Theory of Computation Jan 28, 2017

374 views

1 vote

1 answer

175

TestBook
How to interpret the transitions? I interpreted as L={a*}

Sushant Gokhale asked in Theory of Computation Jan 16, 2017

by Sushant Gokhale

285 views

1 vote

1 answer

176

If L is any language accepted by DPDA with stack containing only one symbol. Then L can be

Ami Ladani asked in Theory of Computation Jan 13, 2017

1.9k views

1 vote

1 answer

177

Pda question
Is WcW CFG?

Adiaspirant asked in Theory of Computation Jan 11, 2017

1.7k views

0 votes

1 answer

178

MadeEasy Subject Test: Theory of Computation - Pushdown Automata
Here aa is accepted, in which number of a's and b's is not equal. So, shouldn't option D is correct.

Lucky sunda asked in Theory of Computation Jan 7, 2017

446 views

2 votes

1 answer

179

Working with PDA transitions
Either I dont understand PDA at all or this question is wrong or I am missing something very basic:

Mahesha999 asked in Theory of Computation Jan 1, 2017

340 views

0 votes

1 answer

180

Non deterministic PDA
Can the NPDA constructed to accept L, such that L = L1 U L2 , L1 = {1n 0n | n > 0} and L2 = {0n 12n | n > 0} be drawn like this? This is an informal representation of NPDA. Is this correct? Or should the NPDA accepting language L should have 2 final states?

Nithish asked in Theory of Computation Dec 14, 2016

1.6k views

Page:

« prev
1
2
3
4
5
6
7
8
next »

Recent questions tagged pushdown-automata