544 views
0 votes
0 votes

If L1 is context free and L2 is not context free, then L1 ∩ L2 is context free.

Is this true or not?

2 Answers

0 votes
0 votes
No..in worst case it will not be CFL..

L1 intersection L2= higher order language among two..
0 votes
0 votes
take an example

L1= (a^n b^n | where n >=1  )   //CFL

L2=(a^n b^n c^n| where n >=1 )  // NCFL

there intersection are not CFL

BUT if

L1= (a^n b^n | where n >=0  )   //CFL

L2=(a^n b^n c^n| where n >=0 )  // NCFL

then there intersection will be empty language which is regular which is CFL

hence we may contradict here

 

BUT we always need do focus on worst case

so this statement is FALSE

Related questions

1 votes
1 votes
1 answer
2
practicalmetal asked Mar 20, 2023
358 views
The complement of the languages:i) {ww | w in (0+1)*}ii) {$a^n b^nc^n$ | n>1} area) Context Free b) Not Context Free c)are DCFL’s d)None
0 votes
0 votes
1 answer
3
swami_9 asked Jul 16, 2022
525 views
Why the complement of a CFL is CSL?
1 votes
1 votes
1 answer
4
Abhipsa asked Jan 22, 2019
279 views
Is this a deterministic context free language (DCFL) ? $a^{k}$ | k is evenThanks!