Closure Properties and Language Classification PYQs for GATE CS

Solve 14+ Closure Properties and Language Classification previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Closure Properties and Language Classification

Chapter Roadmap

Closure Properties and Language Classification

1. Regular Language Identification and Classification

Foundation: Finite memory, modular counting, and subset traps. (Weightage: ~3 questions)

2. Context-Free Language Classification and Structural Constraints

Advanced: Structural constraints, pumping lemma, and grammar ambiguity. (Weightage: ~6 questions)

3. Closure Properties of Language Classes

Application: Algebraic tools to prove language class membership without building machines. (Weightage: ~5 questions)

By the end of this chapter: You will have a complete, step-by-step decision framework to classify any language and prove its properties under various operations.

Regular Language Identification and Classification

Theory of Computation › Closure Properties and Language Classification

Regular Language Identification and Classification

The foundation of the Chomsky hierarchy: mastering finite memory constraints and spotting regularity in complex patterns.

1. Finite memory intuition 2. The finite language rule 3. Modular arithmetic patterns 4. Subset property traps

Closure Properties and Language Classification: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Theory of Computation · 2026_Set2 MSQ

Let

Σ = {a, b, c, d}

and let

L = {a^{i} b^{j} c^{k} d^{ℓ} ∣ i, j, k, ℓ \geq 0}

.
Which of the following constraints ensure(s) that the language

L

is context-free?

A.
$i + k = j + ℓ$
B.
$i = k$ and $j = ℓ$
C.
$i = ℓ$ and $j = k$
D.
$i + j = k + ℓ$

Correct Answer:

["C","D"]

Step-by-Step Solution

Key idea: This is a structural constraint question for Context-Free Languages, recognizable because it asks which arithmetic constraints on the exponents of a 4-part string allow it to be generated by a single stack (PDA).

Step 1: The base string format is $a^{i} b^{j} c^{k} d^{ℓ}$ . A PDA processes this left-to-right. It can push symbols for the first parts and pop for the later parts. The fundamental limit is that it can only maintain ONE active nested comparison at a time.

Step 2: Evaluate Option A: $i + k = j + ℓ$ . This requires matching the sum of the first and third parts with the sum of the second and fourth parts. Because $b$ and $c$ are in the middle, a single stack cannot simultaneously track $i$ against $j$ and $k$ against $ℓ$ in a crossed manner. This requires two independent comparisons. NOT CFL.

Step 3: Evaluate Option B: $i = k$ and $j = ℓ$ . This requires matching $a$ with $c$ and $b$ with $d$ . These are two independent comparisons separated by other symbols. A single stack cannot do this. NOT CFL.

Step 4: Evaluate Option C: $i = ℓ$ and $j = k$ . The string is $a^{i} b^{j} c^{j} d^{i}$ . The PDA can push $a$ 's, then push $b$ 's. When reading $c$ 's, it pops $b$ 's (matching $j = k$ ). When reading $d$ 's, it pops $a$ 's (matching $i = ℓ$ ). This is a single, perfectly nested comparison. IS CFL.

Step 5: Evaluate Option D: $i + j = k + ℓ$ . The PDA can push both $a$ 's and $b$ 's onto the stack. The total number of symbols pushed is $i + j$ . Then, it pops for every $c$ and every $d$ . The total number of symbols popped is $k + ℓ$ . Since $i + j = k + ℓ$ , the stack will empty exactly at the end. This is a single comparison of sums. IS CFL.

Answer: C, D

Question 2 · Theory of Computation · 2026_Set1 MSQ

Let

L_{1}

and

L_{2}

be two languages over a finite alphabet, such that

L_{1} \cap L_{2}

and

L_{2}

are regular languages.

Which of the following statements is/are always true?

A.
$L_{1}$ is regular
B.
$L_{1} \cup L_{2}$ is regular
C.
$L_{2}$ is context-free
D.
$L_{1}$ is context-free

Correct Answer:

["C"]

Step-by-Step Solution

Key idea: This is a closure properties question involving the subset fallacy, recognizable because it gives a condition on an intersection and asks what must be true about the individual languages.

Step 1: We are given that $L_{1} \cap L_{2}$ is regular and $L_{2}$ is regular. We need to determine which statements are ALWAYS true.

Step 2: Evaluate Option A ( $L_{1}$ is regular) and Option B ( $L_{1} \cup L_{2}$ is regular). Consider the counterexample where $L_{2} = \emptyset$ . The empty set is regular. Then $L_{1} \cap L_{2} = L_{1} \cap \emptyset = \emptyset$ , which is regular. This satisfies the given conditions for ANY language $L_{1}$ . If we choose $L_{1}$ to be a non-regular language (e.g., ${a^{n} b^{n} ∣ n \geq 0}$ ), then $L_{1}$ is not regular, and $L_{1} \cup L_{2} = L_{1} \cup \emptyset = L_{1}$ is not regular. Thus, A and B are NOT always true.

Step 3: Evaluate Option D ( $L_{1}$ is context-free). Using the same counterexample where $L_{1} = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ (which is not context-free) and $L_{2} = \emptyset$ , the conditions are met but $L_{1}$ is not CFL. Thus, D is NOT always true.

Step 4: Evaluate Option C ( $L_{2}$ is context-free). We are explicitly given that $L_{2}$ is regular. Since every regular language is also a context-free language (Regular $\subset$ CFL), $L_{2}$ MUST be context-free. This is ALWAYS true.

Answer: C

Question 3 · Theory of Computation · 2025_Set2 MSQ

Let

Σ = {a, b, c}

. For

x \in Σ^{*}

, and

α \in Σ

, let

#_{α} (x)

denote the number of occurrences of

α

x

.

Which one or more of the following option(s) define(s) regular language(s)?

A.
${a^{m} b^{n} ∣ m, n \geq 0}$
B.
${a, b}^{*} \cap {a^{m} b^{n} c^{m - n} ∣ m \geq n \geq 0}$
C.
${w ∣ w \in {a, b}^{*}, #_{a} (w) \equiv 2 (mod 7), and #_{b} (w) \equiv 3 (mod 9)}$
D.
${w ∣ w \in {a, b}^{*}, #_{a} (w) \equiv 2 (mod 7), and #_{a} (w) = #_{b} (w)}$

Correct Answer:

["A","C"]

Step-by-Step Solution

Key idea: This is a regular language identification question, recognizable because it asks which of the given string patterns can be recognized by a finite automaton (DFA), focusing on modular counting and intersection traps.

Step 1: Evaluate Option A: ${a^{m} b^{n} ∣ m, n \geq 0}$ . This is simply the language $a^{*} b^{*}$ . A DFA can easily recognize this by staying in a start state for $a$ 's, transitioning to a second state for $b$ 's, and rejecting if an $a$ appears after a $b$ . This IS regular.

Step 2: Evaluate Option B: ${a, b}^{*} \cap {a^{m} b^{n} c^{m - n} ∣ m \geq n \geq 0}$ . The intersection with ${a, b}^{*}$ means we only keep strings that contain NO $c$ 's. For the second language to have no $c$ 's, the exponent of $c$ must be 0, so $m - n = 0 ⟹ m = n$ . The language reduces to ${a^{m} b^{m} ∣ m \geq 0}$ . This requires unbounded counting and is NOT regular.

Step 3: Evaluate Option C: ${w ∣ w \in {a, b}^{*}, #_{a} (w) \equiv 2 (mod 7), and #_{b} (w) \equiv 3 (mod 9)}$ . This language only requires counting the number of $a$ 's modulo 7 and the number of $b$ 's modulo 9. A DFA can easily maintain two separate counters (one cycling every 7 states, one cycling every 9 states) using the product construction. This IS regular.

Step 4: Evaluate Option D: ${w ∣ w \in {a, b}^{*}, #_{a} (w) \equiv 2 (mod 7), and #_{a} (w) = #_{b} (w)}$ . While the modulo condition is regular, the condition $#_{a} (w) = #_{b} (w)$ requires unbounded counting to ensure the total number of $a$ 's exactly equals the total number of $b$ 's. A finite automaton cannot remember an arbitrarily large count. This is NOT regular.

Answer: A, C

Question 4 · Theory of Computation · 2025_Set2 MSQ

Consider the two lists List I and List II given below:

For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

A.
(i) – (a), (ii) – (b), and (iii) – (c)
B.
(i) – (b), (ii) – (a), and (iii) – (c)
C.
(i) – (b), (ii) – (c), and (iii) – (a)
D.
(i) – (a), (ii) – (c), and (iii) – (b)

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a language classification and closure properties matching question. We must verify the truth of each proposed pairing between a language class and its closure property.

Step 1: Analyze Context-Free Languages (CFLs).

CFLs are closed under union, concatenation, and Kleene star.

CFLs are NOT closed under intersection or complementation.

Therefore, (i) matches (a) "Closed under union" and (b) "Not closed under complementation".

Step 2: Analyze Recursive Languages.

Recursive languages are closed under union, intersection, complementation, concatenation, and Kleene star.

Therefore, (ii) matches (a) "Closed under union" and (c) "Closed under intersection".

Step 3: Analyze Regular Languages.

Regular languages are closed under all standard operations: union, intersection, complementation, concatenation, Kleene star, reversal, etc.

Therefore, (iii) matches (a) "Closed under union" and (c) "Closed under intersection".

Step 4: Evaluate the given options.

Option A: (i)-(a) [True], (ii)-(b) [False, Recursive IS closed under complement], (iii)-(c) [True]. Overall: False.

Option B: (i)-(b) [True], (ii)-(a) [True], (iii)-(c) [True]. Overall: True.

Option C: (i)-(b) [True], (ii)-(c) [True], (iii)-(a) [True]. Overall: True.

Option D: (i)-(a) [True], (ii)-(c) [True], (iii)-(b) [False, Regular IS closed under complement]. Overall: False.

Answer: Options B and C are correct.

Question 5 · Theory of Computation · 2025_Set1 MCQ

Consider the following two languages over the alphabet

{a, b, c}

, where

m

and

n

are natural numbers.

L_{1} = {a^{m} b^{m} c^{m + n} ∣ m, n \geq 1}

L_{2} = {a^{m} b^{n} c^{m + n} ∣ m, n \geq 1}

Which ONE of the following statements is CORRECT?

A.
Both $L_{1}$ and $L_{2}$ are context-free languages.
B.
$L_{1}$ is a context-free language but $L_{2}$ is not a context-free language.
C.
$L_{1}$ is not a context-free language but $L_{2}$ is a context-free language.
D.
Neither $L_{1}$ nor $L_{2}$ are context-free languages.

Correct Answer:

Step-by-Step Solution

Key idea: This is a language classification question comparing two similar-looking languages, recognizable because it tests the difference between multiple independent comparisons and a single nested sum comparison.

Step 1: Analyze $L_{1} = {a^{m} b^{m} c^{m + n} ∣ m, n \geq 1}$ . The string has three parts: $a^{m}$ , $b^{m}$ , and $c^{m + n}$ . The condition requires matching $a$ with $b$ (both have exponent $m$ ), AND then matching the $m$ from the first part with the first $m$ $c$ 's. This requires two independent comparisons ( $a$ with $b$ , and $a$ with $c$ ). A single stack cannot do this. Thus, $L_{1}$ is NOT context-free.

Step 2: Analyze $L_{2} = {a^{m} b^{n} c^{m + n} ∣ m, n \geq 1}$ . The string has three parts: $a^{m}$ , $b^{n}$ , and $c^{m + n}$ . The condition requires the total number of $c$ 's to equal the sum of $a$ 's and $b$ 's.

Step 3: Can a PDA recognize $L_{2}$ ? Yes. The PDA can push a symbol for every $a$ read, then push a symbol for every $b$ read. The stack now contains $m + n$ symbols. Then, for every $c$ read, it pops one symbol. Since the total number of $c$ 's is exactly $m + n$ , the stack will empty exactly at the end of the string. This is a single, valid stack operation. Thus, $L_{2}$ IS context-free.

Step 4: Compare with the options. $L_{1}$ is not CFL, $L_{2}$ is CFL. This matches Option C.

Answer: C

Question 6 · Theory of Computation · 2025_Set1 MCQ

Consider the following two languages over the alphabet

{a, b}

L_{1} = {α β α ∣ α \in {a, b}^{+} AND β \in {a, b}^{+}}

L_{2} = {α β α ∣ α \in {a}^{+} AND β \in {a, b}^{+}}

Which ONE of the following statements is CORRECT?

A.
Both $L_{1}$ and $L_{2}$ are regular languages.
B.
$L_{1}$ is a regular language but $L_{2}$ is not a regular language.
C.
$L_{1}$ is not a regular language but $L_{2}$ is a regular language.
D.
Neither $L_{1}$ nor $L_{2}$ is a regular language.

Correct Answer:

Step-by-Step Solution

Key idea: We must determine the regularity of two languages defined by string patterns. The key is to simplify the pattern definitions by analyzing the constraints on $α$ and $β$ .

Step 1: Analyze $L_{1} = {α β α ∣ α \in {a, b}^{+}, β \in {a, b}^{+}}$ .

$α$ is any non-empty string over ${a, b}$ . The shortest possible $α$ is a single character ('a' or 'b').

$β$ is any non-empty string over ${a, b}$ .

Therefore, any string in $L_{1}$ must have a length of at least $1 + 1 + 1 = 3$ , and it must start and end with the same single character.

Can any string of length $\geq 3$ starting and ending with the same character be formed? Yes. Let the first character be $α$ , the middle part be $β$ , and the last character be $α$ .

Thus, $L_{1}$ is exactly the set of strings of length $\geq 3$ that start and end with 'a', OR start and end with 'b'.

Regular Expression for $L_{1}$ : $a (a + b)^{+} a + b (a + b)^{+} b$ .

Since it can be described by a regular expression, $L_{1}$ is a Regular Language.

Step 2: Analyze $L_{2} = {α β α ∣ α \in {a}^{+}, β \in {a, b}^{+}}$ .

Here, $α$ is restricted to one or more 'a's. So $α = a^{k}$ for some $k \geq 1$ .

The string format is $a^{k} β a^{k}$ .

This requires the number of 'a's at the beginning to exactly match the number of 'a's at the end, with an arbitrary string $β$ in the middle.

This is a classic counting dependency (similar to $a^{n} b a^{n}$ ), which requires unbounded memory. A finite automaton cannot track the arbitrary count $k$ .

Therefore, $L_{2}$ is NOT a Regular Language.

Conclusion: $L_{1}$ is regular, but $L_{2}$ is not regular.

Answer: Option B.

Question 7 · Theory of Computation · 2024_Set1 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}} = ϕ$
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

Correct Answer:

["C","D"]

Step-by-Step Solution

Key idea: This question tests the closure properties of Regular languages and how they interact with non-regular languages. We evaluate each statement for universal truth.

Step 1: Evaluate Option A.

Statement: $L_{1} = L_{2}$ if and only if $L_{1} \cap \overline{L_{2}} = \emptyset$ .

The condition $L_{1} \cap \overline{L_{2}} = \emptyset$ is equivalent to $L_{1} \subseteq L_{2}$ . It does not guarantee $L_{2} \subseteq L_{1}$ .

Counterexample: $L_{1} = {a}$ , $L_{2} = {a, b}$ . $L_{1} \cap \overline{L_{2}} = \emptyset$ , but $L_{1} \neq = L_{2}$ . Thus, Option A is FALSE.

Step 2: Evaluate Option B.

Statement: $L_{1} \cup L_{3}$ is not regular.

Counterexample: Let $L_{1} = Σ^{*}$ (which is regular) and $L_{3}$ be any non-regular language. Then $L_{1} \cup L_{3} = Σ^{*}$ , which IS regular. Thus, Option B is FALSE.

Step 3: Evaluate Option C.

Statement: $\overline{L_{3}}$ is not regular.

Proof by contradiction: If $\overline{L_{3}}$ were regular, then its complement $\overline{\overline{L_{3}}} = L_{3}$ would also be regular (since Regular languages are closed under complementation). This contradicts the given fact that $L_{3}$ is not regular. Thus, Option C is TRUE.

Step 4: Evaluate Option D.

Statement: $\overline{L_{1}} \cup \overline{L_{2}}$ is regular.

Since $L_{1}$ and $L_{2}$ are regular, their complements $\overline{L_{1}}$ and $\overline{L_{2}}$ are also regular (closure under complement). The union of two regular languages is always regular (closure under union). Thus, Option D is TRUE.

Answer: Options C and D are always TRUE.

Question 8 · Theory of Computation · 2023 MSQ

Which of the following statements is/are CORRECT?

A.
The intersection of two regular languages is regular.
B.
The intersection of two context-free languages is context-free.
C.
The intersection of two recursive languages is recursive.
D.
The intersection of two recursively enumerable languages is recursively enumerable.

Question 9 · Theory of Computation · 2022 MSQ

Consider the following languages:

$L_{1} = {a^{n} w a^{n} ∣ w \in {a, b}^{*}}$

$L_{2} = {w x w^{R} ∣ w, x \in {a, b}^{*}, ∣ w ∣, ∣ x ∣ > 0}$

Note that $w^{R}$ is the reversal of the string $w$ . Which of the following is/are TRUE?

A.
$L_{1}$ and $L_{2}$ are regular.
B.
$L_{1}$ and $L_{2}$ are context-free.
C.
$L_{1}$ is regular and $L_{2}$ is context-free.
D.
$L_{1}$ and $L_{2}$ are context-free but not regular.

Question 10 · Theory of Computation · 2022 MSQ

Consider the following languages:

$L_{1} = {w w ∣ w \in {a, b}^{*}}$

$L_{2} = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$

$L_{3} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$

Which of the following statements is/are FALSE?

A.
$L_{1}$ is not context-free but $L_{2}$ and $L_{3}$ are deterministic context-free.
B.
Neither $L_{1}$ nor $L_{2}$ is context-free.
C.
$L_{2}$ , $L_{3}$ and $L_{2} \cap L_{3}$ all are context-free.
D.
Neither $L_{1}$ nor its complement is context-free.

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Key idea: This question requires classifying three specific languages and evaluating statements about them. We must identify which statements are FALSE.

Step 1: Classify $L_{1} = {w w ∣ w \in {a, b}^{*}}$ .

This language requires matching an arbitrary string with an identical copy of itself. A single stack cannot remember an unbounded, unconstrained string to verify the second half. Thus, $L_{1}$ is NOT context-free.

However, its complement $\overline{L_{1}}$ IS context-free (a PDA can non-deterministically guess a mismatched character or an odd length).

Step 2: Classify $L_{2} = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$ .

This requires matching the count of 'a's and 'b's, while 'c's are independent. A single stack can push for 'a' and pop for 'b', then ignore 'c'. This is a Deterministic Context-Free Language (DCFL), and therefore a CFL.

Step 3: Classify $L_{3} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$ .

Similar to $L_{2}$ , the 'a's are independent, and the stack matches 'b's and 'c's. This is also a DCFL, and therefore a CFL.

Step 4: Evaluate the statements.

Statement A: " $L_{1}$ is not context-free but $L_{2}$ and $L_{3}$ are deterministic context-free." -> This is a TRUE statement.

Statement B: "Neither $L_{1}$ nor $L_{2}$ is context-free." -> FALSE, because $L_{2}$ IS context-free.

Statement C: " $L_{2}$ , $L_{3}$ and $L_{2} \cap L_{3}$ all are context-free." -> FALSE. $L_{2} \cap L_{3} = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ , which is the classic non-context-free language.

Statement D: "Neither $L_{1}$ nor its complement is context-free." -> FALSE, because $\overline{L_{1}}$ IS context-free.

Answer: Statements B, C, and D are FALSE.

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Closure Properties and Language Classification PYQs for GATE CS

Chapter Roadmap: Closure Properties and Language Classification

Chapter Roadmap

1. Regular Language Identification and Classification

2. Context-Free Language Classification and Structural Constraints

3. Closure Properties of Language Classes

Regular Language Identification and Classification

Regular Language Identification and Classification

Closure Properties and Language Classification: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit