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

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

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 (Tyes being its TM) and not holding for the other(Tno being its TM).

Tyes is the TM whose language is Φ. Can Tyes exist? yes
Tno is the TM whose language is (a+b)*. Can Tno 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

0

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

0
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..