Question 4978 – Theory-of-Computation

Option 1: L​ ₁ ​ and L_{​ 2}​ are context free languages and context free languages are closed under union but not closed under complementation. It means intersection result may or may not br
CFL. So when we will do subtraction the result may or may not be CFL.
Option 2: L​ ₁​ is a CFL and R is a Regular language and if we do L​ ₁​ – R the result will Regular language.
L​ ₁ ​ = {a​ n​ b​ n​ | n>0} is a context free language which can generate strings {ab, aabb, aaabbb, …….}
R = (a+b)* which can generate language {∈, a, b, aa, bb, ab, ba, …….}
So L​ ₁​ -R = {ф} which is a regular language.
And since every regular language is also a CFL so option 2 is correct.
Option 3: context free languages are not closed under complementation. So option 3 is incorrect.
Option 4: context free languages are not closed under Intersection. So option 4 is incorrect.