retagged by
814 views
0 votes
0 votes
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??
retagged by

1 Answer

Best answer
3 votes
3 votes

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..

selected by

Related questions

4 votes
4 votes
1 answer
1
AnilGoudar asked Jun 5, 2017
1,611 views
If L1 = { anbncm | n.m >0 }L2 = { anbmcm | n, m 0}Which of these following are false?1) L1 ∩ L2 is CFL.2) L1 ∪ L2 is CFL.3) L1 and L2 are CFL.4) L1 ∩ L2 is CSL...
0 votes
0 votes
0 answers
3