decidable and undecidable problem : https://gatecse.in/grammar-decidable-and-undecidable-problems/

Question

Soutce : https://gatecse.in/grammar-decidable-and-undecidable-problems/

Why L(G1) ⋂ L(G2) = Φ ?? is undecidable for dcfl, cfl etc ?? please explain it anyone

Comments

I am giving it an attempt but I am pretty new to this topic..so anyone finding it wrong is requested to rectify me and give the correct explanation.

We know that cfls are not closed under intersection. So  L(G1) ⋂ L(G2) may or may not be a cfl. But we can always say that L(G1) and L(G2) are recursively enumerable languages and so their intersection is also RE(as RE languages are closed under intersection).

Let L(G)= L(G1) ⋂ L(G2) where L(G) is RE. So now we can reduce the problem statement to "L(G)=Φ is decidable or not".

By Rice Theorem, every non trivial property of RE set is undecidable. For a property to be non trivial there should exist atleast 2 RE languages(hence 2 TMs),the property holding for one (T_yes being its TM) and not holding for the other(T_no being its TM).

T_yes is the TM whose language is Φ. Can T_yes exist? yes
T_no is the TM whose language is (a+b)*. Can T_no exist? yes

So we can say that this property is non trivial. And hence we can conclude that whether a RE language is Φ  is an undecidable problem.

=> L(G)=Φ  is undecidable

=> L(G1) ⋂ L(G2) =Φ  is undecidable

---

@daksirp

G1 and G2 here both CFL right?

here think about one example with 2 CFL

$a^{n}b^{n}c^{m}\cap a^{m}b^{n}c^{n}=a^{n}b^{n}c^{n}$

which cannot be CFL

 

---

Srestha I think his doubt is about something else..he is not asking whether cfl is closed under intersection or not..he wants to know whether intersection of two CFLs is null is undecidable or not..and how..

---

exactly !!!

Answer 1

we can do it in two ways one is in informal way and another in formal way 

(1) we have to check every length string in both language ,if there is some thing common then we can say yes ,but if we have nothing in common then we have to check every possible string forever

---

(2) we can use reduction to proove this.we all know PCP(post correspondance problem)  is undecidable . somehow if we are able to reduce PCP to Empty Intersection problem then we can say that  Empty Intersection problem also undecidable.

let's try in PCP we have to find some solution of given two  sequence of strings .

for example A and B are two sequence ,A have set strings {1,10111,10} and B={ 111,10,0} .both have three strings name as 1,2,3 . we can use these string as many times to find solution. like 2113 is the solution of above sequences .

$A_2A_1A_1A_3$=10111 11 10

$B_2B_1B_1B_3$=10 111 111 0

now we can convert these sequences into grammars-

$S_A =1S_Aa|10111S_Ab|10S_Ac|1a|10111b|10c$

$S_B=111S_Ba|10S_Bb|0S_Bc|111a|10b|0c$

a,b,c repesent the record which string is concancated .

these two grammars generate languages have something common which also be solution of PCP and they have no common then no way to solve .so we have reduced  PCP to   Empty Intersection problem . so   Empty Intersection problem also undecidable.