Register

TOC DPDA vs NPDA

2,839 views
1 1 vote
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?

1 Answer

1 1 vote

PDA either deterministic (DPDA) or non-deterministic (NPDA) has only 1 stack. With two stacks it will get power of Turing Machine.

Regarding the given language:
L=( W |n(a)=n(b) and n(c)=n(d) ),where n(a) is number if a in words

this language is CSL not CFL hence can't be accepted by DPDA or NPDA.

we need LBA to accept this language!!

• edited
Voting & Accepting an answer helps improve the community
← Previous · Mod MachineNext → · Hamming Distance, Li...
← Previous in category · Mod MachineNext in category → · an intro to finite a...
Position:
Show:

Related questions

2 2 votes
2 2 answers
3.9k
3.9k views
rahul sharma 5 asked Nov 21, 2017
3,899 views
[TOC] Basic doubt in DPDA
Following is the PDA that accept equal number of a and b.How can this be converted to DPDA? When stack top is Z,that it can read epsillon or a or b,which can create choic...
0 0 votes
2 answers 2 answers
3.6k
3.6k views
akankshadewangan24 asked Jul 6, 2017
3,626 views
NPDA and DPDA
Can we make NPDA? L= {anbn| n>=0,a,b are input variables}if yes then make it .
0 0 votes
1 1 answer
1.2k
1.2k views
Rahul Jain25 asked Feb 9, 2017
1,185 views
TOC DPDA
A DPDA can have dead configurations?? True/False.I think answer should be true bcoz DPDA requires that for a combination of top symbol and input at each state there is un...
2 2 votes
1 1 answer
2.4k
2.4k views
Shubhanshu asked Jul 8, 2017
2,360 views
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...