Register

DCFL COMPLETENESS PROBLEM

1,028 views
4 4 votes
DCFL COMPLETENESS PROBLEM is decidable or not?

L=(sigma)*

Not getting any discussion regarding it in GO,iN GO chart it is decidable but I am not able to conclude the reason please guide?

1 Answer

Best answer
4 4 votes
Completeness problem for dcfls is decidable.

It depends on emptiness problem.

Whether given DCFL is sigma*? is decidable problem.

Step 1) For given dcfl L, design DPDA D.

Step 2) Modify dpda to accept complement of  L by interchanging  finals and nonfinals.

Step 3) If modified DPDA accepts empty language, then given dpda D accepts sigma*. Otherwise not.

So completeness problem for dcfls is decidable.

Thanks,

Mallesham Devasane
• selected by
Voting & Accepting an answer helps improve the community
← Previous · Self DoubtNext → · MadeEasy Test Series...
← Previous in category · ME testNext in category → · Intersection of two ...
Position:
Show:

Related questions

6 6 votes
1 answers 1 answer
3.8k
3.8k views
himgta asked Feb 15, 2018
3,769 views
why completeness problem in case of DCFL is decidable, & it is undecidable in case of CFL?
0 0 votes
1 1 answer
2.1k
2.1k views
target2017 asked Nov 20, 2016
2,121 views
P NP completeness
Problems related to P-NP completeness are covered in syllabus or not (either in TOC or ALGO)?
6 6 votes
1 1 answer
223
223 views
GO Classes asked Jun 20
223 views
GO Classes DPP | GATE CS | Digital Logic | Functional Completeness
A Boolean operator $\odot$ is defined by the following truth table:\[\begin{array}{|c|c|c|}\hlineA & B & A \odot B \\\hline0 & 0 & 1 \\0 & 1 & 0 \\1 & 0 & 0 \\1 & 1 & 0\\...
7 7 votes
1 1 answer
210
210 views
GO Classes asked Jun 20
210 views
GO Classes DPP | GATE CS | Digital Logic | Functional Completeness
A set of Boolean operations is called functionally complete if:It contains only AND and OR gates It can be used to express every Boolean function It contains XOR operatio...