GATE 1999
December 6, 2023Theory-of-Computation
December 6, 2023Theory-of-Computation
|
Question 45
|
If L is context free language and L2 is a regular language which of the following is/are false?
|
L1 – L2 is not context free
|
|
|
L1 ∩ L2 is context free
|
|
|
~L1 is context free
|
|
|
~L2 is regular
|
|
|
Both A and C
|
Question 45 Explanation:
(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
So L1 – L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 – L2 is CFL. So False.
So L1 – L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 – L2 is CFL. So False.
(B) As we said that CFL is closed under regular intersection.
So True.
(C) CFL is not closed under complementation.
Hence False.
(D) Regular language is closed under complementation.
Hence True.
Correct Answer: E
Question 45 Explanation:
(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
So L1 – L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 – L2 is CFL. So False.
So L1 – L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 – L2 is CFL. So False.
(B) As we said that CFL is closed under regular intersection.
So True.
(C) CFL is not closed under complementation.
Hence False.
(D) Regular language is closed under complementation.
Hence True.