The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
70 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 Junior (883 points) | 70 views
+2

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

 

+1
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..
0
exactly !!!

1 Answer

0 votes

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.

answered by Loyal (5.8k points)


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

39,437 questions
46,622 answers
139,338 comments
56,999 users