GATE CSE 1987 | Question: 2k

Question

State whether the following statements are TRUE or FALSE:

The intersection of two CFL's is also a CFL.

Comments

Need not be.

Answer 1

No intersection of two CFLs may or may not be a CFL i.e. CFL is not closed under intersection operation.

Example:

• $L_1: \{ a^nb^nc^m| n,m >=1 \} \cap L_2: \{ a^nb^mc^m | n,m >=1 \}$
• $L_3= \{ a^mb^mc^m | m >=1 \}$,  which is CSL.

Comments

Abhrajyoti00

so then ,  $L_{3} = {{a^nb^nc^n | n\geq 1}}$ is also correct.

---

Yes, both are same of course. Just variable names

---

Yup . Thanks again :)

Answer 2

false
aⁿbⁿc* is cfl and aⁿb*cⁿ is also cfl but their intersection aⁿbⁿcⁿ is not

Answer 3

False, context free language are not closed under intersection and complement.

Answer 4

FALSE,  as CFL’s are not closed under intersection operation and hence intersection of two CFL’s may or may not be a CFL. It could be CSL also.