Question 3646 – 2005 Dec UGC NET Paper-1
December 2, 2023Question 5037 – Theory-of-Computation
December 2, 2023Question 4978 – Theory-of-Computation
Consider R to be any regular language and L1 .L2 be any two context-free languages Which one of the following is correct ?
Correct Answer: B
Question 440 Explanation:
Option 1: L 1 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 1 is a CFL and R is a Regular language and if we do L 1 – R the result will Regular language.
L 1 = {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 1 -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.
CFL. So when we will do subtraction the result may or may not be CFL.
Option 2: L 1 is a CFL and R is a Regular language and if we do L 1 – R the result will Regular language.
L 1 = {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 1 -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.
(L 1 ⋃ L 2 ) − R is context free
L 1 − R is context free
L 1 is context free
L 1 ⋂ L 2 is context free