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

Updated 29 Oct 20268 min read71 views
Closure Properties MCQs: 12 Solved Regular Language PYQs with Explanations

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

Closure map deriving intersection, nor, and symmetric difference for regular languages.

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

Operation classifier showing repeat can be non-regular while prefix, suffix, and half stay regular.

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.

  1. Underline the quantifier, especially "always", "every", or "infinite".

  2. Rewrite the operation with union, intersection and complement where possible.

  3. Try empty set, Sigma^*, a finite language, and {a^n b^n} as witnesses.

  4. 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.