The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
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
asked in Theory of Computation by (49 points) | 32 views
+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

@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

 

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

Please log in or register to answer this question.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,995 questions
44,570 answers
126,774 comments
43,636 users