1,962 views
7 votes
7 votes
Is L(G) subset of L(R) decidable ? Where G is CFG and R is regular grammar.

Problem can be reduced to checking if L(G) $\cap$ ( L(R))' = phi.

Now L(R)' is regular, so it also CFL and determining whether

L(G1) $\cap$ L(G2) = phi is known to be  undecidable where L(G1) and L(G2) are CFL's . So above problem should also be undecidable.

Where am I going wrong ?

Please log in or register to answer this question.

Related questions

724
views
2 answers
1 votes
jugnu1337 asked Nov 7, 2022
724 views
M is a Turing Machine and M is the only Turing Machine that accepts L(M) is decidable. TRUE/FALSE
624
views
0 answers
0 votes
853
views
1 answers
0 votes
Rahul Jain25 asked Feb 7, 2017
853 views
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??