3,486 views
4 votes
4 votes
If the problem is L(G1)∩L(G2)= Empty , then if G1 and G2  are both cfl's then is it decidable ?

According to me it should be decidable since if the intersection is regular then we can identify whether the language is empty or not and if it is CFL then also through the grammar we can check it out seeing the start symbol .

1 Answer

3 votes
3 votes
NO.

CFLs are not closed under intersection. If you make an intersection of two CFLs, you may or may not get a CFL.
But the intersection of CFL with a regular language is always CFL. There are ways to do it.

So, CFL intersection CFL is undecidable while CFL intersection regular language is decidable.

Related questions

5 votes
5 votes
2 answers
1
radha gogia asked Nov 29, 2015
1,498 views
If I take L=a^n b^n and R=(a+b)* so I am getting the value of L/R to be regular ,Am I correct ?
4 votes
4 votes
2 answers
3
Vikrant Singh asked Jan 18, 2015
3,829 views
Which of the following are True?$S1$: Every NFA can be converted to equivalent PDA$S2$: Whether a given CFL is Regular is decidable.1. $S1$ ...
0 votes
0 votes
1 answer
4
mehul vaidya asked Sep 3, 2018
526 views
To find intersection of this two : If i proceed like thisregular ∩ CFG CFG ∩ CFG as regular lang is also CFGbut CFG is not closed under intersectionhence answer ma...