636 views
2 2 votes
Which of the following language is/are Turing decidable?

1. L = { <G1, G2> | G1 & G2 are regular grammar and L(G1) ⊆ L(G2)}

2. L = { <G, R> | G is a CFG & R is a regular expression and L(G) ⊆ L(R)}

3. L = { <G, R> | G is a CFG & R is a regular expression and L(R) ⊆ L(G)}

 (A) 1 only   (B) 1 & 2 only   (C) 2 & 3 only   (D) 1 & 3 only

1 Answer

Best answer
4 4 votes

1. L = { <G1, G2> | G1 & G2 are regular grammar and L(G1) ⊆ L(G2)}

True. Subset problem is decidable for regular grammars. You can use the method in (2) and (3) to prove the same.

 2. L = { <G, R> | G is a CFG & R is a regular expression and L(G) ⊆ L(R)}

True. Subset can be rewritten as $L(G)\cap \overline{L(R)}=\phi$.

We know that Regular languages are closed under complement. And for a CFL, the intersection with Regular language is also closed. Now we know that $L(G)\cap \overline{L(R)}$ is a CFL. So create the CFG of that. $L(G) = \phi$ is decidable for CFG. 

3. L = { <G, R> | G is a CFG & R is a regular expression and L(R) ⊆ L(G)}

False. We can use a similar approach of that of (2). Here  $L(R) \cap \overline{L(G)}$. But the issue here is L(G) is not closed under complement. So we dont know what kind of language this is. Therfore undecideable.

 

So option(B) 1&2 only.
 

References:

(1) https://gatecse.in/grammar-decidable-and-undecidable-problems/

(2) https://gatecse.in/closure-property-of-language-families/

• edited by
Position:
Show:

Related questions

1 1 vote
0 0 answers
694
694 views
admin asked Oct 17, 2019
694 views
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of te...
0 0 votes
0 0 answers
842
842 views
0 0 votes
0 0 answers
444
444 views
Abbas2131 asked Feb 23, 2018
444 views
In this lecture by Shai Simonson : https://youtu.be/77OG6ziPMu4 At 33:04 he mentions that "A = CFL that does not accept $\sum^*$ " is Undecidable.Also, we already know th...
0 0 votes
1 1 answer
397
397 views
ankith_mondal asked Nov 17, 2024
397 views
helloo just got a qstn, is universality problem for cfl decidable or undecidable? in toc sir taught it is deccidable , but in the chart sir shown it was writen undecidabl...