chapter

Theory of Computation PYQs for GATE CS

GATE CS Theory of Computation: 1 units and 4 chapters, weightage from 47 previous year questions across 10 papers, a study order by exam weight and 0 practice

A question from this chapter

Question 1

2026 Slot Set2 PYQ

Consider the following two finite automata D_{1} and D_{2} . 001001101 D_{1} 01111001 D_{2} Which of the following statements is/are true?

Question 2

2026 Slot Set2 PYQ

Level 3: Exam Standard

Which of the following grammars is/are ambiguous?

Question 3

2026 Slot Set2 PYQ

Level 3: Exam Standard

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?

Question 4

2026 Slot Set2 PYQ

Which one of the following statements is equivalent to the following assertion? Turing machine M decides the language L \subseteq {0, 1}^{*}

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Theory of Computation PYQs for GATE CS

GATE CS Theory of Computation: 1 units and 4 chapters, weightage from 47 previous year questions across 10 papers, a study order by exam weight and 0 practice questions.

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.

GATE CS Theory of Computation Unit-wise Weightage from Past Papers

We counted every GATE CS Theory of Computation previous year question in our bank (47 questions from 10 papers) and grouped them by unit.

Unit	Chapters	PYQs	Share of section	Avg per paper
Theory of Computation	4	47	100%	4.7

Suggested Theory of Computation Study Order for GATE CS

Theory of Computation: 100% of past Theory of Computation questions, about 4.7 per paper.

Start where the marks are. Units at the top of this list have appeared most often in past GATE CS papers.

Units in GATE CS Theory of Computation

Theory of Computation Previous Year Questions (PYQs) (4 chapters)

All Theory of Computation chapters

One Solved Question from Each Theory of Computation Chapter

Question 1 · Finite Automata and Regular Expressions · 2026_Set2 MSQ

Consider the following two finite automata

D_{1}

and

D_{2}

D_{1}

0 1 1 1 1 0 0 1

D_{2}

Which of the following statements is/are true?

A.
$L (D_{1}) = L (D_{2})$
B.
$L (D_{1})$ is a proper subset of $L (D_{2})$
C.
$L (D_{1}) \cap L (D_{2}) = {ϵ}$
D.
$(L (D_{1}) \cup L (D_{2}))^{*}$ consists of all strings in ${0, 1}^{*}$ whose length is divisible by 3

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$