decidable problem

Question

Let L be a DCFL and R is a regular language. Consider the below given problems.
P: Is L=R ?
Q: Is R ⊆L ?
Discuss decidablity of P and Q.

Comments

Thank you for this piece of information :)

"..if it does then check a production which iteratively can generate same strings." Can you please elaborate this part..

---

S->aS/$\epsilon\Rightarrow a^*$

Now to check same production convert production into gnf
then find a production :
$S->aV_1$

$V_1->aS/a$

or

$V_1->aV_1/a$

checking a production with same production can be solved by using pattern or other similiar concept though i never implemented but this should be implementable.

---

PART 2: To check whether ( R  ⊆ L ) we need to get ( R ∩ L'= Φ ).

R ∩ L' i.e. Regular ∩ DCFL =DCFL we know.

And whether DCFL=Φ is decidable (If no string can be generated from the DCFG then it is NULL and that can be checked from it's grammar. Hence decidable).

PART 1: If (R⊆L and L⊆ R) then we can say that R=L.

So we just need to check if R⊆L and L⊆ R both are decidable or not.

R⊆L is already decidable as done in previous part.

Similarly for L⊆ R,

L ∩ R' i.e. DCFLr ∩ Reg =DCFL we know.

And whether DCFL=Φ is decidable (If no string can be generated from the DCFG then it is NULL and that can be checked from it's grammar. Hence decidable).

  Anu007 Sir I hope this is the way you asked me to follow.

 

Answer 1

i think both are undecidable

Answer 2

1^st is decidable and 2^nd is undecidable. This can be concluded from the Decidablity table.