Closure Properties MCQs: 12 Solved Regular Language PYQs with Explanations

Closure properties look easy when they are only a table, but PYQs rarely ask for the table alone. Students lose marks by missing words such as "always", treating finite union as infinite union, or assuming that every subset of a regular language must also be regular. These 12 solved PYQs cover direct closure, derived Boolean operations, counterexamples, and language transformations, and they come from KnowledgeGate's collection of over 30 published questions on this exact subtopic. Use them to strengthen your wider GATE CS exam preparation: identify the quantifier, rewrite the operation, and search for one decisive witness before reading each answer, even when the familiar table is not enough on its own.

Related reading: language closure rules and regular languages.

1. Closure under union, complement and derived Boolean operations

Regular languages are closed under union, intersection, complement and difference. Regular Language Properties: Closure and Decision Tests derives results with De Morgan's laws.

Q1. GATE 2024, see the solved page, MSQ

Let $L_1$, $L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

• (a) $L_1 = L_2$ if and only if $L_1 \cap \overline{L_2} = \text{𝜙}$

• (b) $L_1 \cup L_3$ is not regular

• (c) $\overline{L_3}$ is not regular

• (d) $\overline{L_1} \cup \overline{L_2}$ is regular

Answer: (c) and (d).

For (a), take $L_1=\{a\}$ and $L_2=\{a,b\}$: the intersection is empty although the languages differ; for (b), $L_1=\Sigma^*$ makes the union regular. If $\overline{L_3}$ were regular, double complementation would make $L_3$ 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 \subseteq P$. (For example, let $P$ be the language represented by the regular expression \(p^q^\) and $Q$ be $\{p^nq^n \mid n \in N\}$). Then which of the following is ALWAYS regular?

• (a) $P \cap Q$

• (b) $P-Q$

• (c) $\Sigma^*-P$

• (d) $\Sigma^*-Q$

Answer: (c).

Because $\Sigma^*-P=\overline P$, option (c) is regular. With the supplied \(P=p^q^\) and $Q=\{p^nq^n\mid n\in N\}$, $P\cap 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 $L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$. 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 $S_1$ and $S_2$ is defined as $S_1 \oplus S_2 =\{x \mid x \in S_1 \text{ or } x \in S_2, \text{ but x is not in both } S_1 \text{ and } S_2\}$. The nor of two languages is defined as $nor(L_1,L_2)=\{w \mid w \notin L_1 \text{ and } w \notin L_2\}$. 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 $S_1=\{a,b\}$ and $S_2=\{b,c\}$, the symmetric difference is $\{a,c\}$; generally it is $(L_1\cap\overline{L_2})\cup(\overline{L_1}\cap L_2)$. Also, $nor(L_1,L_2)=\overline{L_1\cup L_2}$, 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 $\cup$ 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 $L_1=\{a^n b^n\mid n\ge0\}$ and \(L_2=\Sigma^\); their union is the regular language \(\Sigma^\), although $L_1$ is not regular. For II, every singleton $L_n=\{a^n b^n\}$ is regular, but $\bigcup_{n\ge0}L_n=\{a^n b^n\mid n\ge0\}$ 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\mid bb$. Option (a) fails because \(\{a^n b^n\mid n\ge0\}\subseteq\{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 \cap 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 $\varnothing$ 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; Finite Automata: DFA vs NFA and Subset Construction explains that boundary.

Q8. GATE 2006, see the solved page, MCQ

Let L be a regular language. Consider the constructions on L below: I. repeat(L) = $\{ww \mid w \in L\}$, II. prefix(L) = $\{u \mid \exists v: uv \in L\}$, III. suffix(L) = $\{v \mid \exists u: uv \in L\}$, IV. half(L) = $\{u \mid \exists v: |v|=|u| \text{ 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\mid 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 $L_1=\{a^n\mid n\geq0\}$ and $L_2=\{b^n\mid n\geq0\}$, consider (I) $L_1\cdot L_2$ is a regular language (II) L1$\cdot$L2 = $\{a^n b^n\mid n\geq0\}$. 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 \(L_1=a^\) and \(L_2=b^\), so \(L_1L_2=a^b^=\{a^i b^j\mid i,j\ge0\}\), which is regular by concatenation closure. The string aab has $i=2$ and $j=1$, so it belongs to $L_1L_2$ 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)\mid 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\mid \nu W\in L, \text{ 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}\mid n\ge0,m\ge0\}$

• (b) $\{a^n b^m\mid n=2m\}$

• (c) $\{a^n b^m\ n\ne m\}$

• (d) $\{xcy\mid 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

These PYQs test direct closure in Q1 to Q4, counterexamples to "always" in Q5 to Q7, custom operations in Q8 to Q10, and construction or recognition in Q11 and Q12. Use one routine for all forms.

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

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

3. Try $\varnothing$, $\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 preserve it, and custom transformations must be proved rather than guessed. Re-attempt Q1, Q5, Q8 and Q11 after one week because together they cover direct closure, counterexamples, operation analysis, and symbolic construction. For each one, name the closure rule or counterexample before checking the option letter.

If you want the complete Theory of Computation lesson sequence and more PYQ practice, continue with GATE Guidance by Sanchit Sir. Your immediate task is simpler: rebuild the closure table from proofs, then solve those four questions again without looking at the options.