edited by
1,174 views
6 votes
6 votes

Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:

  1. Decidable
  2. Undecidable but semi-decidable
  3. Not even semi-decidable
  4. Indeterminable
edited by

2 Answers

Best answer
9 votes
9 votes

G1: Regular Grammar and G2:Context Free Grammar
Suppose L1= L(G1)   and L2 = L(G2)

Take another language such that
L= L1 - L2,  if L is empty language then L1 is proper subset of L2
L= L1 - L2
L= L1 ∩  L2c
L2 is CFL which is not closed under complement hence complement of L2 will be CSL
L=Regular ∩ CSL = CSL

And CSL is not closed under emptiness property,

L(R) ⊆ L(G)  is undecidable and for any DCFG L(R) ⊆ L(G) is decidable as given in this list 

http://gatecse.in/grammar-decidable-and-undecidable-problems/

so this problem is undecidable but semi-decidable  which makes option B correct. 

selected by
0 votes
0 votes

In the question, it is given that a regular grammar G1 and a context free grammar G2, we have to decide  if  a language generated by regular grammar is a proper subset of a language generated by context free grammar .

L(R) ⊆ L(G)  is undecidable and for any DCFG L(R) ⊆ L(G) is decidable as given in this list 

http://gatecse.in/grammar-decidable-and-undecidable-problems/

so this problem is undecidable but semi-decidable  which makes option B correct. 

edited by
Answer:

Related questions

0 votes
0 votes
1 answer
1
Bikram asked Nov 26, 2016
294 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
201 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
3
1 votes
1 votes
1 answer
4