Closure questions look like a memory test, but difficult options hide a change of operand. They mix a CFL with a regular language, disguise intersection as difference, or test one complement rather than the whole family.
Here are exactly 12 published questions, moving from the closure table to concrete intersections, homomorphism, reversal, powers and prefix closure. Mark every statement true or false before checking the choices. KnowledgeGate has over 60 published questions on Closure Properties under Pushdown Automata & CFG, within the wider GATE CS Exam Preparation route. Throughout, a family is closed under an operation only if applying it to every valid input in that family keeps the result in the family.
The CFL closure map to use before the questions
Operation | Result for CFLs |
|---|---|
Union, concatenation, Kleene star | Closed |
Reversal, homomorphism, inverse homomorphism, substitution | Closed |
Intersection, complement, difference | Not closed in general |
CFL intersected with regular | Context-free |
CFL minus regular | Context-free |
For the last row, \(L-R=L\cap\overline{R}\). Regular languages are closed under complement, and intersecting a CFL with a regular language preserves context-freeness.
The standard counterexample is worth working once. Let \(L_1=\{a^nb^nc^m\mid m,n\geq0\}\) and \(L_2=\{a^mb^nc^n\mid m,n\geq0\}\). Each is context-free, so \(L_1\cup L_2\) is context-free. In the intersection, \(L_1\) gives \(\#a=\#b\), while \(L_2\) gives \(\#b=\#c\). Together, \(\#a=\#b=\#c\), so \(L_1\cap L_2=\{a^nb^nc^n\mid n\geq0\}\), which is not context-free. Also, failure of general complement closure does not mean every individual CFL has a non-CFL complement.
Closure Properties MCQs 1-3: the rule table and a regular operand
Question 1
If L₁ is a context-free language and L₂ is a regular language, which of the following statements is/are false?
a. L₁ - L₂ is not context-free.
b. L₁ ∩ L₂ is context-free.
c. ~L₁ is context-free.
d. ~L₂ is regular.
(a) Only b
(b) Only c
(c) Both a and c
(d) Both b and c
Answer: (c) Both a and c. Difference becomes \(L_1\cap\overline{L_2}\), so a is false. General CFL complement failure makes c false; b and d are true.
Question 2
The statements s₁ and s₂ are given as :
s₁: Context sensitive languages are closed under intersection, concatenation, substitution and inverse homomorphism.
s₂: Context free languages are closed under complementation, substitution and homomorphism.
Which of the following is correct statement?
(a) Both s₁ and s₂ are correct.
(b) s₁ is correct and s₂ is not correct.
(c) s₁ is not correct and s₂ is correct.
(d) Both s₁ and s₂ are not correct.
Answer: (b) s₁ is correct and s₂ is not correct. The s₁ operations preserve context-sensitive languages. CFL complementation makes s₂ fail.
Question 3
Suppose that \( L_1\) is a regular language and \( L_2\) is a context-free language. Which one of the following languages is NOT necessarily context-free?
(a) \(L_1 ∩ L_2\)
(b) \(L_1 \cdot L_2\)
(c) \(L_1 - L_2\)
(d) \(L_1 ∪ L_2\)
Answer: (c) \(L_1-L_2\). This is \(L_1\cap\overline{L_2}\), and \(\overline{L_2}\) need not be context-free. The other listed operations are safe here.
Closure Properties MCQs 4-6: union and intersection with actual languages
Question 4
Consider the following languages over the alphabet \(\Sigma = \left \{ a, b, c \right \}\). Let \(L_{1} = \left \{ a^{n}b^{n}c^{m}\mid m,n \geq 0 \right \}\) and \(L_{2} = \left \{ a^{m}b^{n}c^{n}\mid m,n \geq 0 \right \}\).
Which of the following are context-free languages?
I. \(L_{1} \cup L_{2}\)
II. \(L_{1} \cap L_{2}\)
(a) I only
(b) II only
(c) I and II
(d) Neither I nor II
Answer: (a) I only. Union is safe. Intersection combines \(\#a=\#b\) and \(\#b=\#c\), producing the non-CFL \(\{a^nb^nc^n\}\).
Question 5
Let \(L_1\), \(L_2\) be any two context-free languages and \(R\) be any regular language. Then which of the following is/are CORRECT?
I. \(L_1 \cup L_2\) is context-free
II. \(\overline{L_1}\) is context-free
III. \(L_1 - R\) is context-free
IV. \(L_1 \cap L_2\) is context-free
(a) I, II and IV only
(b) I and III only
(c) II and IV only
(d) I only
Answer: (b) I and III only. The truth vector is T, F, T, F. For III, \(L_1-R=L_1\cap\overline R\), with \(\overline R\) regular.
Question 6
Let L = L1∩L2, where L1 and L2 are languages as defined below:
L1 = {aᵐ bᵐ caⁿ bⁿ | m, n >= 0}
L2 = {aⁱ bʲ cᵏ | i, j, k >= 0}
Then L is
(a) Not recursive
(b) Regular
(c) Context free but not regular
(d) Recursively enumerable but not context free.
Answer: (c) Context free but not regular. The form \(a^*b^c^\) forces \(n=0\), \(k=1\), and \(i=j=m\). Thus \(L=\{a^mb^mc\}\), generated by \(S\to Tc, T\to aTb\mid\varepsilon\). Its right quotient by \(\{c\}\) is the non-regular \(\{a^mb^m\}\).
Closure Properties MCQs 7-9: product construction, powers and homomorphism
Question 7
Let L be a context-free language and M a regular language. Then the language L ∩ M is
(a) always regular
(b) never regular
(c) always a deterministic context-free language
(d) always a context-free language
Answer: (d) always a context-free language. A PDA-DFA product retains one stack, so it is a PDA. It need not be regular or deterministic.
Question 8
Consider the following statements with respect to the language \(L = \{ a^n b^n \mid n \geq 0 \}\)
\(𝑆_1\): \(𝐿^2\) is a context free language
\(𝑆_2\):\(𝐿^𝑘\) is context free language for any given \(𝑘≥1\).
\(𝑆_3\): \( \overline{L}\) and \(𝐿^∗\) are context free languages
Which one of the following is correct?
(a) only \(𝑆_1\) and \(𝑆_2\)
(b) only 𝑆1 and \(𝑆_3\)
(c) only \(𝑆_2\) and \(𝑆_3\)
(d) \(𝑆_1\), \(𝑆_2\) and \(𝑆_3\)
Answer: (d) \(S_1,S_2,S_3\). Concatenation gives \(L^2,L^k\), and star closure gives \(L^*\). This complement splits into strings outside \(a^b^\), plus the CFL cases \(i<j\) and \(i>j\).
Question 9
Consider the following statements about Context Free Language (CFL) :
Statement I: CFL is closed under homomorphism.
Statement II: CFL is closed under complement.
Which of the following is correct ?
(a) Statement I is true and Statement II is false
(b) Statement II is true and Statement I is false
(c) Both Statement I and Statement 𝐼𝐼 are true
(d) Neither Statement I nor Statement II is true
Answer: (a) Statement I is true and Statement II is false. Homomorphism fits a CFG. Complement plus union and De Morgan would wrongly imply intersection closure.
Closure Properties MCQs 10-12: reversal, a non-CFL intersection and prefixes
Question 10
Given below are two statements Statement
I: The family of context free languages is closed under homomorphism Statement
II: The family of context free languages is closed under reversal
In light of the above statements, choose the correct answer from the options given below
(a) Both Statement I and Statement II are true
(b) Both Statement I and Statement II are false
(c) Statement I is true but Statement II is false
(d) Statement I is false but Statement II is true
Answer: (a) Both Statement I and Statement II are true. Substitute terminals for homomorphism; mirror production right-hand sides for reversal.
Question 11
Let
\(L_1 = \{ 0^n 1^n 0^m | n>=1, m>=1 \} \\L_2 = \{ 0^n 1^m 0^m | n>=1, m>=1 \} \\L_3 = \{ 0^n 1^n 0^n | n>=1\} \)
Which of the following are correct statements?
A. \( L_3 =L_1 \cap L_2\)
B. \(L_1\) and \(L_2\) are context free languages but L is not a context free language
C. \(L_1\) and \(L_2\) are not context free languages but L is a context free language
D. \(L_1\) is a subset of \(L_3\)
Choose the correct answer from the options given below:
(a) A and B only
(b) A and C only
(c) A and D only
(d) A only
Answer: (a) A and B only. Both equalities give the non-CFL \(L_1\cap L_2=L_3=\{0^n1^n0^n\}\). In B, L means \(L_3\). D fails: 0011000 is in \(L_1\) for \(n=2,m=3\), not \(L_3\).
Question 12
Define init(L) = {u | uv is in L for some v in {0, 1}*}. In other words, init(L) is the set of prefixes of strings in L.
Let L = {w | w is nonempty and has an equal number of 0s and 1s}. Then init(L) is
(a) the set of all binary strings with unequal numbers of 0s and 1s
(b) the set of all binary strings, including the null string
(c) the set of all binary strings with exactly one more 0 than 1, or exactly one more 1 than 0
(d) None of the above
Answer: (b) the set of all binary strings, including the null string. For \(u=00100\), choose \(v=111\); \(uv=00100111\) has four of each symbol. For \(u=\varepsilon\), choose \(v=01\).
The traps these 12 closure questions expose
Pattern | Fast conclusion |
|---|---|
CFL with CFL | Union, concatenation and star are safe; intersection, complement and difference are unsafe in general |
CFL with regular | Intersection and CFL minus regular are safe |
Regular minus CFL | Not guaranteed to be context-free |
One language versus the family | Test the given language, as in Question 8 |
Constructive operation | Homomorphism and reversal preserve CFLs |
Both sides impose equalities | Combine them; three equal counters often expose a non-CFL |
Identify each operand, rewrite difference, check whether the claim says “any”, then combine the equalities in an intersection. Learn the constructions in Context-Free Grammars and Pushdown Automata, compare Regular Language Properties: Closure and Decision Tests, and continue with Context-Free Grammar MCQs: 11 Solved GATE Questions.
Closure Properties MCQs: the next practice step
Redo Questions 1, 4, 6, 8 and 11 without looking. Together they test difference, a non-CFL intersection, intersection with a regular pattern, a particular complement and equality of three counters.
For a subject-specific route, study Theory of Computation / Automata Theory. For the wider exam sequence, use GATE Guidance by Sanchit Sir.
The short version is simple: do not turn “CFLs are not closed under intersection” into a universal ban. First identify the other operand, then decide whether the question concerns the whole family or one specified language. That distinction resolves most of the traps in this set.
