Question #38621
We are given two context-free languages L1 and L2 and L defined as below
a) L=(0+1)* if L1=L2
b) L=((0+00+000)*(1+11+111)*)* if L1 is contained in L2
c) L=((0(10)*)*(1(01)*)* if L2 is contained in L1
d) L=(00+11+0+1)*(0+00+000)* if L1 and L2 are incomparable
a) As all the conditions relating to L1 and L2 are undecidable we cannot say anything about L
b) L is recursively enumerable
c) L is recursive but not context-sensitive
d) L is context-sensitive but not context-free
e) L is context-free but not regular
a) L=(0+1)* if L1=L2
b) L=((0+00+000)*(1+11+111)*)* if L1 is contained in L2
c) L=((0(10)*)*(1(01)*)* if L2 is contained in L1
d) L=(00+11+0+1)*(0+00+000)* if L1 and L2 are incomparable
a) As all the conditions relating to L1 and L2 are undecidable we cannot say anything about L
b) L is recursively enumerable
c) L is recursive but not context-sensitive
d) L is context-sensitive but not context-free
e) L is context-free but not regular
Expert's answer
Answer on Question#38621 – Math - Other
We have two context-free languages and . By a property of recursively enumerable language that all regular, context-free, context-sensitive and recursive languages are recursively enumerable, we can see that the right answer is .
