711 views
4 votes
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 votes
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

Related questions

6 votes
6 votes
1 answer
1
0 votes
0 votes
1 answer
2
target2017 asked Nov 20, 2016
1,605 views
Problems related to P-NP completeness are covered in syllabus or not (either in TOC or ALGO)?
0 votes
0 votes
0 answers
3
aditi19 asked Nov 16, 2018
330 views
Is Ex-NOR functionally complete? pls explain in details
0 votes
0 votes
1 answer
4
sanju77767 asked May 15, 2018
537 views
f(A,B,C)=A'+BC'is this functionally Complete For AND PLZZ give solution