Computer Sciences > Gate 2017 Set-2 > Regular Language
Let L1 and L2 be any context-free language and R be any regular language. Then, which of the following is correct ?

I. L1 ∪ L2 is context-free.
II. L1' is context-free.
III. L1-R is context-free.
IV. L1 ∩ L2 context-free.
A
I only
B
I and III only
C
II and IV only
D
I, II and IV only

Correct : R

Given:
L1 and L2 are context-free languages (CFLs).
R is a regular language.
To find:
Which of the given statements are correct.
Solution:
Let me check statement I first.
Statement I says: L1 ∪ L2 is context-free.
I know that context-free languages are closed under union, so this statement is true.
Now let me check statement II.
Statement II says: L1' is context-free.
CFLs are not closed under complementation, so L1' is not necessarily context-free.
Thus, statement II is false.
Now checking statement III.
Statement III says: L1 - R is context-free.
I can rewrite set difference as: L1 - R = L1 ∩ R'
Since regular languages are closed under complement, R' is also a regular language.
Also, the intersection of a CFL and a regular language is always a CFL.
So, L1 ∩ R' is context-free, which means statement III is true.
Now checking statement IV.
Statement IV says: L1 ∩ L2 is context-free.
CFLs are not closed under intersection, so this is not necessarily context-free.
Thus, statement IV is false.
So only statements I and III are correct.
Answer: (B) I and III only

Similar Questions

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
#132 MCQ
For Σ = {a, b}, let us consider the regular language L = {x ∣ x = a2+ 3k or x = b10 + 12k, k ≥ 0} Which one of the following can be a pumping length (the co...
#252 MCQ
Consider the following languages. L1 = { wxyx ∣ w,x,y ∈ (0+1)+ } L2 = { xy ∣ x,y ∈ (a+b)*, ∣x∣=∣y∣, x≠y } Which one of the following is TRUE ?
#279 MCQ

Related Topics

context free language GATE 2017 regular language intersection union context free complement of context free GATE computer science set theory context free context free languages gate intersection context free languages

Unique Visitor Count

Total Unique Visitors

Loading......