Test by Bikram | Theory of Computation | Test 1 | Question: 30

Question

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:

• A. Decidable
• B. Undecidable but semi-decidable
• C. Not even semi-decidable
• D. Indeterminable

Comments

@ Nitesh Choudhary

see the 3rd row and first column   https://www.cs.wcupa.edu/rkline/fcs/grammar-undecidable.html

and see in this table for 1st row, intersection with regular language is always decidable.

A reference  Gate question https://gateoverflow.in/118143/gate2017-2-04

---

@Nitesh Choudhary and @ AnilGoudar 

This problem is undecidable but semi decidable 

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

---

Sir this problem is undecidable but semidecidable na

Answer 1

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 ∩  L2^c
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. 

Comments

@Bikram Sir,

How does the  Whether L(G) is a regular language?(# 8 in the listed in the same document) is undecidable??  If we can able to give a regular expression for the given language, cant we say it is an regular language?

---

@ AnilGoudar 

Regularity is undecidable for general Context-Free Languages.

Read this please , it is discussed here https://cstheory.stackexchange.com/questions/30771/deciding-whether-a-context-free-language-is-regular

@Arjun Suresh any comment please ?

---

As per me, it is not even semi-decidable also.

for saying, semi decidable we have to say "yes" for "yes case".

if i really give the G$_1$ which generates, regular infinite language and G$_2$ which generates, strictly context free infinite language then I am busy with finding a counter case but isn't possible.

So, here we are not able to producing "yes" for "yes case".

So, it is not even Semidecidable.

 

What about it's complement ?

it's complement is " L(G$_1$) is not a proper subset of L(G$_2$) is "

then there are two cases : L(G$_1$) = L(G$_2$) or L(G$_1$) is not related to L(G$_2$)

if L(G$_1$) is not related to L(G$_2$), then we will find a string which is in L(G$_1$) but not in L(G$_2$), So we can produce yes

but if L(G$_1$) = L(G$_2$), then we will find a string which is in L(G$_1$) but not in L(G$_2$), but to check it, we are busy in loop, So here we are not able to producing "yes" for "yes case".

So, this also not even Semidecidable.

Answer 2

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. 

Comments

@arjun sir, if we reduce Post Correspondence Problem to given problem (regularity of CFG) in polynomial time. Then, the given problem is at least as hard as PCP.

And we already know that PCP is semi-decidable. see this https://cs.stackexchange.com/questions/53376/is-posts-correspondence-problem-recognizable.
Therefore, Given problem can be semi-decidable or can't be(Not RE). But it is undecidable for sure.
Here they are saying that they can reduce PCP to the given problem.
http://people.cs.ksu.edu/~rhowell/770s03/lectures/23-twoup.pdf

---

@ Hemant Parihar 

So that means for this problem it is Undecidable but semi decidable so option B is correct right ?

---

so finally,what is correct answer?? option B or ??