60 solved GATE CS questions on Theory of Computation, drawn from 8 exam years and grouped by year. Every question shows the official answer and a step-by-step solution.
Want to practise this topic and ask follow-up questions? Explore Success Tracker.
Revision companion
Specify the set of strings a language contains before attempting to recognize or generate them. These selected foundations connect regular languages, context-free grammars, Turing machines, and undecidability. Formal proofs of non-regularity and undecidability follow structured techniques, not intuition.
Our study notes and original examples support the PYQs below; they are not official exam questions or a replacement for the current syllabus.
A DFA has exactly one transition per state per symbol; an NFA may have multiple or none. Both recognize the same class of languages: regular languages. Regular expressions, DFAs, and NFAs are equivalent in power. Closure properties: regular languages are closed under union, intersection, complement, and concatenation.
Check yourself: Does your DFA have a transition for every symbol in every state?
To prove a language L is not regular: assume L is regular, then for any pumping length p chosen by the adversary, find a string w in L with |w| ≥ p such that every valid decomposition xyz (with |xy| ≤ p, |y| ≥ 1) produces some xy^i z not in L. The string choice is yours; the decomposition is the adversary's.
Check yourself: Have you shown the failure for every valid decomposition, not just one?
A CFG generates strings through productions from a start symbol. A language is context-free if and only if some PDA recognizes it. CFLs are closed under union, concatenation, and Kleene star, but not under intersection or complement. Ambiguity means more than one parse tree for some string.
Check yourself: Can you derive the same string via two distinct leftmost derivations?
A Turing machine can read, write, and move on an unbounded tape. A language is decidable if some TM halts on every input and correctly accepts or rejects. A language is recognizable (recursively enumerable) if some TM accepts every member, but may loop on non-members. Decidable languages are closed under complement.
Check yourself: Does the machine halt on every input, or only on members of the language?
The halting problem is undecidable: no TM can decide whether an arbitrary TM halts on a given input. Reductions prove undecidability: if deciding L would let you decide a known undecidable problem, then L is also undecidable. The reduction must transform instances correctly in both directions.
Check yourself: Does your reduction map yes-instances to yes-instances and no-instances to no-instances?
Original teaching example · not a PYQ
Original mini-example: prove that L = {a^n b^n | n ≥ 0} is not regular using the pumping lemma.
L = {a^n b^n | n ≥ 0} is not regular.
Construct a DFA over alphabet {0, 1} that accepts exactly those strings ending in 01.
Three states: q0 (start), q1, q2 (accept). Transitions: q0→q0 on 1, q0→q1 on 0, q1→q1 on 0, q1→q2 on 1, q2→q0 on 1, q2→q1 on 0.
q0 represents 'last symbol was 1 or no input yet'. q1 represents 'last symbol was 0'. q2 represents 'last two symbols were 01'. Only q2 accepts. Every state has exactly one transition per symbol.
Supplemental reading, not an official GATE reading list or an endorsement of these notes.
Free supplemental lectures, problem sets, and solutions covering regular languages, context-free languages, Turing machines, and computability by Michael Sipser.
This page shows 60 recent questions from the released archive, newest first. For older questions and complete papers, browse all GATE CS papers. Questions can carry more than one subject tag; counts are not marks weightage.
L(G) denote the language generated by . Which ONE…MCQ · +1 marks · EasyContinue learning with Success Tracker
Reading a solution is a useful start. In Success Tracker, you can attempt questions yourself, review mistakes and return to the topics that need another pass.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.