Register

TOC DPDA vs NPDA

1,957 views
1 votes
1 votes
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?
User Avatar

1 Answer

1 votes
1 votes

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
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
1
rahul sharma 5 asked Nov 21, 2017
2,328 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 choice.So how can i remove choice in this and make it deterministic?
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...
User Avatar
0 votes
0 votes
2 answers
2
akankshadewangan24 asked Jul 6, 2017
2,491 views
NPDA and DPDA
Can we make NPDA? L= {anbn| n>=0,a,b are input variables} if yes then make it .
Can we make NPDA? L= {anbn| n>=0,a,b are input variables}if yes then make it .
User Avatar
0 votes
0 votes
1 answer
3
Rahul Jain25 asked Feb 9, 2017
880 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 unique transition.
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...
User Avatar
Link Copied!