Theory of Computation PYQs for GATE CS

GATE CS Theory of Computation: 4 chapters, 47 previous year questions (100% of Theory of Computation), 0 practice questions and one solved question from each chapter.

About Theory of Computation Previous Year Questions (PYQs)

47 previous year questions from Theory of Computation in GATE CS, grouped by chapter with the exam year, answer key and step-by-step solution for each.

Theory of Computation Weightage in GATE CS

Theory of Computation accounts for 47 of 47 Theory of Computation previous year questions in our bank (100%), about 4.7 per paper across 10 papers.

Theory of Computation Chapter Matrix

Chapter	Topics	PYQs	Share of unit PYQs
Finite Automata and Regular Expressions	NFA-to-DFA Conversion and State Complexity, DFA Minimization, Distinguishability and Language Equivalence, Regular Expressions, String Counting and Divisibility Languages, Conversion between Finite Automata and Regular Expressions, DFA Design and Recognition of String Patterns	17	36%
Context-Free Grammars and Pushdown Automata	CFG Language Generation and Symbol-Count Properties, Chomsky Normal Form and Derivation Length, Grammar Ambiguity and Multiple Derivations, Pushdown Automata, Transitions and Accepted Languages	10	21%
Closure Properties and Language Classification	Regular Language Identification and Classification, Context-Free Language Classification and Structural Constraints, Closure Properties of Language Classes	14	30%
Turing Machines, Decidability and Undecidability	Decidable Problems for Grammars and Automata, Recursive and Recursively Enumerable Languages, Undecidable Turing Machine Language Properties, Turing Machine Deciders and Halting Behaviour	6	13%

One Solved Question from Each Theory of Computation Chapter

Question 1 · Finite Automata and Regular Expressions · 2025_Set2 NAT

Let

Σ = {1, 2, 3, 4}

. For

x \in Σ^{*}

, let

p r o d (x)

be the product of symbols in

x

modulo 7. We take

p r o d (ϵ) = 1

, where

ϵ

is the null string.

For example,

p r o d (124) = (1 \times 2 \times 4) mod 7 = 1

.

Define

L = {x \in Σ^{*} ∣ p r o d (x) = 2}

.

The number of states in a minimum state DFA for

L

is ___________. (Answer in integer)

Correct Answer:

Step-by-Step Solution

Key idea: This is a minimum state DFA design question based on modular arithmetic, recognizable by the "product modulo \ $m\$ " condition.

Step 1: Identify the states needed. The DFA must remember the product of symbols modulo 7. The possible remainders are 0, 1, 2, 3, 4, 5, 6.

Step 2: Check reachability. The alphabet is $Σ = {1, 2, 3, 4}$ . None of these is 0 or a multiple of 7. Therefore, the product modulo 7 will NEVER be 0. The reachable states are a subset of ${1, 2, 3, 4, 5, 6}$ .

Step 3: Verify all 6 non-zero states are reachable from the start state (product = 1).

1: start state ( $ϵ$ )
2: read '2' ( $1 \times 2 = 2$ )
3: read '3' ( $1 \times 3 = 3$ )
4: read '4' ( $1 \times 4 = 4$ )
5: read '4' then '3' ( $1 \times 4 \times 3 = 12 \equiv 5 (mod 7)$ )
6: read '3' then '2' ( $1 \times 3 \times 2 = 6 \equiv 6 (mod 7)$ )

All 6 states are reachable.

Step 4: Check distinguishability. The accepting condition is $p r o d (x) = 2$ . For any two distinct states $a$ and $b$ , we need a string that leads from one to 2 but not the other. Since all alphabet symbols are coprime to 7, multiplication by them is invertible modulo 7.

From 1, read "2" $\to 2$
From 2, read "1" $\to 2$
From 3, read "3" $\to 9 \equiv 2$
From 4, read "4" $\to 16 \equiv 2$
From 5, read "32" $\to 5 \times 3 \times 2 = 30 \equiv 2$
From 6, read "43" $\to 6 \times 4 \times 3 = 72 \equiv 2$

Since every state has a path to the accepting state, and the operations are deterministic and invertible, no two states can be equivalent.

Step 5: Conclude the number of states is exactly 6. No dead state is needed because 0 is unreachable.

Answer: 6

Question 2 · Context-Free Grammars and Pushdown Automata · 2026_Set2 MSQ

Which of the following grammars is/are ambiguous?

A.
$S \to a S b ∣ ϵ$
B.
$E \to E + E ∣ E * E ∣ i d$
C.
$S \to a S ∣ S a ∣ ϵ$
D.
$S \to a S ∣ ϵ$

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a grammar ambiguity identification question. We need to check each grammar to see if any string has multiple distinct derivations.

Step 1: Check Grammar A: S → aSb | ε

This generates {a^n b^n | n ≥ 0}.

For any string a^n b^n, there's only ONE way to derive it:

Must apply S → aSb exactly n times
Then apply S → ε once
Order is forced (always leftmost or always rightmost)

Grammar A is UNAMBIGUOUS.

Step 2: Check Grammar B: E → E+E | E*E | id

This is the classic expression grammar.

For string "id+id*id":

Derivation 1: E ⇒ E+E ⇒ id+E ⇒ id+EE ⇒ id+idE ⇒ id+idid (groups as id + (id id))

Derivation 2: E ⇒ EE ⇒ E+EE ⇒ id+EE ⇒ id+idE ⇒ id+idid (groups as (id + id) id)

Two different parse trees ⇒ Grammar B is AMBIGUOUS.

Step 3: Check Grammar C: S → aS | Sa | ε

For string "aa":

Derivation 1: S ⇒ aS ⇒ aaS ⇒ aa (using S → aS twice, then S → ε)

Derivation 2: S ⇒ Sa ⇒ aSa ⇒ aa (using S → Sa, then S → aS for the first S, then S → ε)

These are two distinct leftmost derivations for "aa".

Grammar C is AMBIGUOUS.

Step 4: Check Grammar D: S → aS | ε

This generates a* (any number of a's).

For string "aaa", there is only one leftmost derivation:

S ⇒ aS ⇒ aaS ⇒ aaaS ⇒ aaa

Grammar D is UNAMBIGUOUS.

Answer: Grammars B and C are ambiguous.

Question 3 · Closure Properties and Language Classification · 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 4 · Turing Machines, Decidability and Undecidability · 2026_Set2 MCQ

Which one of the following statements is equivalent to the following assertion?

Turing machine M decides the language L \subseteq {0, 1}^{*}

A.
Turing machine $M$ halts on all input strings in ${0, 1}^{*}$
B.
Turing machine $M$ accepts all input strings in $L$
C.
Turing machine $M$ rejects all input strings in ${0, 1}^{*} - L$
D.
Turing machine $M$ accepts all input strings in $L$ and rejects all input strings in ${0, 1}^{*} - L$

A question from this chapter

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

Theory of Computation PYQs for GATE CS

About Theory of Computation Previous Year Questions (PYQs)

Theory of Computation Weightage in GATE CS

Theory of Computation Chapter Matrix

More from Theory of Computation

One Solved Question from Each Theory of Computation Chapter

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution