Question

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?

Answer 1

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