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

is it a partical decidable problem?

---

@ Vaishali Trivedi 

this problem is related to closure property of Regular Grammar and Context Free Grammar . 

please see the best solution now.

---

@Bikram Sir,

Let A = {1, 3, 5}

B = {1, 5}

We can say that B is proper subset of A.

According to Chomsky Hierarchy,

 CFL encloses the Regular language, which means  L(G2) has at least one string that is not in L(G1). Which is nothing but, L(G1) is a proper subset of L(G2).

Hence it will become decidable.

Please correct me if I am wrong.

I am not able to follow the given solution.

---

@Anilgoudar

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 .

now , intersection of CFG and Regular is CFG. Hence it is decidable because intersection with regular language is always decideble .

A table about decidability https://www.cs.wcupa.edu/rkline/fcs/grammar-undecidable.html

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

---

@Bikram Sir,

 Is the answer to this question modified?? Yesterday it says problem is undecidable.

---

@Anil

yes , i change it yesterday, you ae correct , it is decidable , i modify previous answer , it is fine now right ?

---

@ Bikram sir,

Thanks Sir..just wanted to get clarified.

---

@ Bikram sir,

 i got till    intersection of CFG and Regular is CFG.

after could you explain how to see in table?

for this problem which row and which clm.

how " intersection with regular language is always decideble "  ?????

---

@ 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 ??