Closure Properties MCQs: 12 Solved Regular Language PYQs with Explanations
Solve 12 regular-language PYQs with proofs, counterexamples, and step-by-step transformations. The set targets the quantifier traps that make closure questions difficult.
KnowledgeGate Team
Exam prep & CS education

Closure properties are easy as a table, but PYQs test quantifiers, counterexamples, and transformations. Avoid finite/infinite-union and subset traps. In each question, identify the quantifier, rewrite the operation, and find one witness before reading answers. See GATE CS exam preparation.
Regular-language closure uses these rules. The earlier CFL closure MCQ set is for context-free families; the earlier Turing-machine closure MCQ set is for machine-model closure.
1. Closure under union, complement and derived Boolean operations

Regular languages are closed under union, intersection, complement and difference; De Morgan's laws derive the Boolean cases.
Q1. GATE 2024, see the solved page, MSQ
Let L1 , L2 be two regular languages and L3 a language which is not regular. Which of the following statements is/are always TRUE?
(a) L1 = L2 if and only if L1 intersection complement(L2) = empty set
(b) L1 union L3 is not regular
(c) complement(L3) is not regular
(d) complement(L1) union complement(L2) is regular
Answer: (c) and (d).
For (a), take L1={a} and L2={a,b}: the intersection is empty although the languages differ; for (b), L1=Sigma^* makes the union regular. If complement(L3) were regular, double complementation would make L3 regular, a contradiction; (d) follows from complement and union closure.
Q2. GATE 2011, MCQ
Let P be a regular language and Q be a context-free language such that Q subset of P. (For example, let P be the language represented by the regular expression p*q* and Q be {p^nq^n | n in N}). Then which of the following is ALWAYS regular?
(a) P intersection Q
(b) P-Q
(c) Sigma^*-P
(d) Sigma^*-Q
Answer: (c).
Because Sigma^*-P=complement(P), option (c) is regular. With the supplied P=p*q* and Q={p^nq^n | n in N}, P intersection Q=Q is not regular; regularity of P-Q or Sigma^*-Q would force Q to be regular, so neither is guaranteed.
Q3. UGC NET 2017, see the solved page, MCQ
Given the following statements: (A) A class of languages that is closed under union and complementation has to be closed under intersection. (B) A class of languages that is closed under union and intersection has to be closed under complementation. Which of the following options is correct?
(a) Both (A) and (B) are false.
(b) Both (A) and (B) are true.
(c) (A) is true, (B) is false.
(d) (A) is false, (B) is true.
Answer: (c).
Statement (A) follows from L1 intersection L2 = complement(complement(L1) union complement(L2)). Statement (B) fails for the class of all finite languages over Sigma={a,b}: finite union and intersection stay finite, but the complement of {a} is infinite and leaves the class.
Q4. UGC NET 2016, MCQ
The symmetric difference of two sets S1 and S2 is defined as S1 xor S2 ={x | x in S1 or x in S2, but x is not in both S1 and S2}. The nor of two languages is defined as nor(L1,L2)={w | w not in L1 and w not in L2}. Which of the following is correct?
(a) The family of regular languages is closed under symmetric difference but not closed under nor.
(b) The family of regular languages is closed under nor but not closed under symmetric difference.
(c) The family of regular languages are closed under both symmetric difference and nor.
(d) The family of regular languages are not closed under both symmetric difference and nor.
Answer: (c).
For S1={a,b} and S2={b,c}, the symmetric difference is {a,c}; generally it is (L1 intersection complement(L2)) union (complement(L1) intersection L2). Also, nor(L1,L2)=complement(L1 union L2), so the basic closure rules prove both constructions regular.
2. Finite union, infinite union and subset traps
Finite closure is safe. Claims using "infinite", "every", or "always" need proof or a counterexample.
Q5. GATE 2020, MCQ
Consider the following statements. I. If L1 union L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?
(a) I only
(b) II only
(c) Both I and II
(d) Neither I nor II
Answer: (d).
For I, set L1={a^n b^n | n >= 0} and L2=Sigma*; their union is the regular language Sigma*, although L1 is not regular. For II, every singleton L_n={a^n b^n} is regular, but union over n >= 0L_n={a^n b^n | n >= 0} is not.
Q6. GATE 2007, MCQ
Which of the following is TRUE?
(a) Every subset of a regular set is regular.
(b) Every finite subset of a non-regular set is regular.
(c) The union of two non-regular sets is not regular.
(d) Infinite union of finite sets is regular.
Answer: (b).
Every finite language is regular; for example, F={a,bb} has the regular expression a | bb. Option (a) fails because {a^n b^n | n >= 0} subset of {a,b}*, (d) fails by Q5's singleton union, and (c) fails because a non-regular language and its complement unite to Sigma*.
Q7. GATE 2016, MCQ
Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is Sigma^*. II. There exists a regular language A such that for all languages B, A intersection B is regular. Which one of the following is CORRECT?
(a) Only I is true
(b) Only II is true
(c) Both I and II are true
(d) Both I and II are false
Answer: (b).
For I, let Q={q_0}, make q_0 accepting, and add no transitions: the NFA accepts epsilon but rejects a. For II, choose A={a}; for every B, the intersection is either empty set or {a}, and both are regular.
3. Concatenation, repetition and quotient-style operations

Concatenation preserves regularity. Matching copies of an unknown string may exceed finite-state memory, so repeat, prefix, suffix, and half must be separated carefully.
Q8. GATE 2006, see the solved page, MCQ
Let L be a regular language. Consider the constructions on L below: I. repeat(L) = {ww | w in L}, II. prefix(L) = {u | exists v: uv in L}, III. suffix(L) = {v | exists u: uv in L}, IV. half(L) = {u | exists v: |v|=|u| and uv in L}. Which of the constructions could lead to a non-regular language?
(a) Both I and IV
(b) Only I
(c) Only IV
(d) Both II and III
Answer: (b).
For Sigma={0,1} and L=Sigma*, repeat(L) is the non-regular copy language {ww | w in Sigma*}, since its halves must match. Prefix and suffix are quotient constructions, while a finite-state paired simulation proves half regular by tracking the first-half DFA state and an equal-length path to acceptance.
Q9. GATE 2014, MCQ
If L1={a^n | n >= 0} and L2={b^n | n >= 0}, consider (I) L1 * L2 is a regular language (II) L1 * L2 = {a^n b^n | n >= 0}. Which one of the following is CORRECT?
(a) Only (I)
(b) Only (II)
(c) Both (I) and (II)
(d) Neither (I) nor (II)
Answer: (a).
Here L1=a* and L2=b*, so L1L2=a*b*={a^i b^j | i,j >= 0}, which is regular by concatenation closure. The string aab has i=2 and j=1, so it belongs to L1L2 but not to {a^n b^n}.
Q10. UGC NET 2014, MCQ
Let L be any language. Define even(W) as the strings obtained by extracting from W the letters in the even-numbered positions and even(L) = {even(W) | W in L}. We define another language Chop(L) by removing the two leftmost symbols of every string in L given by Chop(L) = {W | nu W in L, with |nu|=2}. If L is regular language then
(a) even(L) is regular and Chop(L) is not regular.
(b) Both even(L) and Chop(L) are regular.
(c) even(L) is not regular and Chop(L) is regular.
(d) Both even(L) and Chop(L) are not regular.
Answer: (b).
For even(W), abcd maps to bd; a two-state odd/even transducer preserves regularity. For Chop, with nu=ab, ab + cd = abcd and removing two symbols gives cd; generally it is a finite union of regular left quotients nu^{-1}L for length-2 strings nu.
4. Homomorphism and direct regular-set recognition
Translate symbols mechanically or reduce the language to a regular expression. Regular Expressions and Pumping Lemma: Worked Proof separates finite-state patterns from unbounded equality constraints.
Q11. UGC NET 2019, see the solved page, MCQ
Consider Sigma={w,x} and T={x,y,z}. Define homomorphism h by: h(x)=xzy, h(w)=zxyy. If L is the regular language denoted by r=(w+x*)(ww)*, then the regular language h(L) is given by
(a) (zxyy+xzy)(zxyy)
(b) (zxyy+(xzy)*)(zxyyzxyy)*
(c) (zxyy+xzy)(zxyy)^*
(d) (zxyy+(xzy)^*)(zxyyzxyy)
Answer: (b).
Substitution gives h(x*)=(xzy)*, h(ww)=h(w)h(w)=zxyyzxyy, and h((ww)*)=(zxyyzxyy)*. Combining the factors gives (zxyy+(xzy)*)(zxyyzxyy)*, exactly option (b).
Q12. GATE 2008, MSQ
Which of the following are regular sets?
(a) {a^n b^{2m} | n >= 0,m >= 0}
(b) {a^n b^m | n=2m}
(c) {a^n b^m n != m}
(d) {xcy | x,y in {a,b}^*}
Answer: (a) and (d).
Option (a) is a*(bb)*, allowing any number of a symbols and an independently even number of b symbols; option (d) is (a+b)*c(a+b)*. Option (b) requires the unbounded ratio n=2m, while (c) requires comparing two unbounded counts, so neither is regular.
5. How closure properties are tested in GATE and UGC NET
Direct closure gives way to counterexamples, custom operations, and homomorphism. Underline the quantifier, rewrite the operation, test empty and universal languages, then test for unbounded memory.
Underline the quantifier, especially "always", "every", or "infinite".
Rewrite the operation with union, intersection and complement where possible.
Try empty set, Sigma^*, a finite language, and {a^n b^n} as witnesses.
Ask whether one DFA would need to remember an unbounded count or an entire earlier substring.
A finite combination of closure rules proves regularity. If a machine must compare unbounded quantities or copy an unknown string, seek a counterexample.
6. Closure properties MCQs: the short revision rule
Finite Boolean operations preserve regularity. Arbitrary subsets and infinite unions do not; custom transformations need proof. Re-attempt Q1, Q5, Q8, and Q11 after a week, naming the closure rule or counterexample first.
Continue with GATE Guidance by Sanchit Sir. Rebuild the closure table, then re-solve Q1, Q5, Q8, and Q11 without options.
Keep learning
Regular Language Properties: Closure, Decision Tests, and Worked Examples
Connect closure properties, decision tests, and proof tools through product automata, pumping arguments, Myhill-Nerode reasoning, and checked string traces.
Closure Properties of Regular Languages: DFA Constructions and Exam Traps
Learn why regular languages remain regular under major operations. Build one product DFA, trace two strings, and compare the constructions operation by operation.
Closure Properties of Regular, Context-Free and Recursive Languages for GATE: The Complete Table with MSQ Drills
Learn the closure table through the few cells that cause most mistakes, then test the logic on four solved MSQ statements.
Closure Properties MCQs: 12 Solved CFL Questions with Explanations
Solve 12 CFL closure questions, then use concise explanations to separate general closure rules from regular-operand and particular-language exceptions.





