Decidablity+DCFL

Question

I) L-R where L is DCFl and R is regular. Is L-R also DCFL decidable or not???

II)If L1 is reducible to L2 and L2 is non-RE then L1 is also Non-RE???

III) If L1 is reducible to L2 and L1 is non-RE then L2 is also non-RE??

Answer 1

a)   L - R  is nothing but L  ∩  R'

So here L belongs to DCFL and R belongs to regular class..

Hence L  ∩  R'  means  DCFL  ∩  (Regular)'  which is regular DCFL only without loss of any generality..Actually this property is treated actually which is also known as "regular difference"..And DCFL is closed actually under this property..

So the resultant language is also DCFL for sure..

Hence the property is decidable as it is not the case that the resultant language may be a DCFL or may not ..

b) According to reducibility problem  ,  X --> Y if we consider hard problem then if X is known then Y is known so non RE is under the category of hard problem..So if X is non RE then Y is non RE but reverse way we cannot conclude..

Hence II) is undecidable and III) is decidable..

Comments

You are right. What about II) and III)???

---

third is alos decidable rt???   when L1 is reducible to L2 and L1 is non R.E then L2 is also non R.E??

Second is false I guess