Theory of Computation Semester Guide: Learn Automata to Decidability in Dependency Order
Study Theory of Computation as one dependency chain, from finite-state memory to the limits of algorithms, with worked machine traces and proof patterns.
KnowledgeGate Team
Exam prep & CS education

Treat Theory of Computation as a dependency chain rather than isolated semester units. The broader Theory of Computation (TOC): Complete Guide with Worked Examples explains the model hierarchy; this semester route orders the constructions, traces and proofs so each step supplies the memory or invariant needed by the next. Use your university syllabus to decide which topics belong in the final revision list.
Theory of Computation: build the language, machine and proof map first
Start with a map of model, language and task:
Model or formalism | Language or idea | Core work |
|---|---|---|
Regular expressions, regular grammars, DFA and NFA | Regular languages | State tracing, conversion, minimisation, closure, regular pumping lemma |
CFG and PDA | Context-free languages | Derivations, parse trees, ambiguity, normal forms, CFL pumping lemma |
Turing machines | Recognisable and decidable languages | Machine traces, halting arguments, reductions |
Complexity classes | Resource-bounded computation | Classification, polynomial reductions |
If complexity appears in your syllabus, place it after decidability; otherwise stop at decidability. The sequence is strings and languages, finite automata, regular expressions and regular grammars, CFG, PDA, Turing machines, then decidability. Skipping the language represented by a model makes later constructions look unrelated.
Ask the same questions in every unit: What memory does this model have? What language can it recognise? What would prove that the model is insufficient?
Finite automata: make state invariants do the work
Let the alphabet be Sigma = {0,1}. The empty string is epsilon, and a language is a set of strings. A DFA has exactly one defined move for each state-symbol pair. An NFA may have several active states. Their representations differ, but DFA and NFA have equal expressive power.
Consider L_even = {w in {0,1}* : w contains an even number of 1s}. Use qE as the start and accepting state, and qO as non-accepting. On 0, each state loops to itself. On 1, the machine changes between qE and qO.
For 10110, the trace is qE -> qO -> qO -> qE -> qO -> qO. The string has three 1s, so it finishes in qO and is rejected. For 10100, the trace is qE -> qO -> qO -> qE -> qE -> qE. It has two 1s, so it finishes in qE and is accepted. The invariant is simple: the current state records the parity of the number of 1s read so far.

For full subset-construction mechanics, work a dedicated DFA/NFA conversion set after the parity trace.
Grammars: move from recognising strings to generating them
The containment ladder is strict: regular languages are a proper subset of context-free languages, followed by the more powerful context-sensitive and recursively enumerable classes. Regular grammars correspond to finite automata. A CFG is the first model here that naturally expresses nested structure.
For a palindrome language with a centre marker, use L_pal = {w c w^R : w in {0,1}*} and the grammar S -> 0S0 | 1S1 | c. A leftmost derivation of 01c10 is S => 0S0 => 01S10 => 01c10. Its parse-tree leaves are 0, 1, c, 1, 0; the matching terminals on both sides encode the reversal.
Learn the operations in order: derive a string, draw its parse tree, test whether the same string has two parse trees, then transform the grammar into CNF or GNF only if your syllabus requires it.
Pushdown automata: let the stack explain the extra power
A finite state cannot remember an unbounded count of 0s. A PDA for L_pair can push one marker per 0, then pop one marker per 1. Write the stack top on the left and use bottom marker Z0. The states are q_push (start), q_pop and q_accept.
Its moves are delta(q_push,0,Z0)=(q_push,0Z0), delta(q_push,0,0)=(q_push,00), delta(q_push,1,0)=(q_pop,epsilon), delta(q_pop,1,0)=(q_pop,epsilon), delta(q_push,epsilon,Z0)=(q_accept,Z0) for the empty string, and delta(q_pop,epsilon,Z0)=(q_accept,Z0) after a non-empty match.
Trace 0011:
(q_push,0011,Z0) -> (q_push,011,0Z0) -> (q_push,11,00Z0) -> (q_pop,1,0Z0) -> (q_pop,epsilon,Z0) -> (q_accept,epsilon,Z0)
Acceptance happens only after all input is consumed and the stack returns to Z0. Use the grammar-conversion exercises in your syllabus to extend this trace to CNF, GNF and pumping-lemma questions.

Turing machines and decidability: separate power from halting
A Turing machine reads, writes and moves both ways on an unbounded tape. A recogniser may loop on a non-member. A decider halts on every input with accept or reject. The earlier Turing Machines in Theory of Computation: Design, Worked Trace and Decidability owns the full 0^n1^n state design and 0011 tape trace; this route keeps the reusable halting test.
For any proposed decider, validate the input form, record progress with a marker or state invariant, reject when a required partner is missing, and prove that each pass reduces the unprocessed work. A recogniser only needs to accept every member; a decider must also halt on every non-member.
In the accompanying tape trace, each marking pass consumes one 0 and one 1 before the final blank transition reaches accept. That finite-progress argument, rather than the picture alone, is what upgrades a recogniser claim to a decider claim.
Keep the boundaries clear: DFA acceptance A_DFA is decidable by simulation. Turing-machine acceptance A_TM and the halting problem HALT_TM are undecidable.
Proof skills: choose the proof from the claim
Use a construction for recognisability or closure, an invariant for a machine trace, contradiction or a pumping lemma to exclude a language from a class, and a mapping reduction to transfer undecidability. The pumping lemma can disprove regularity; it cannot prove regularity.
To show L_pair is not regular, assume pumping length p and choose w = 0^p1^p. The conditions |xy| <= p and |y| > 0 force y = 0^k for some 1 <= k <= p. Pumping with i = 0 gives 0^(p-k)1^p, which is not in L_pair. For a concrete illustration, take p = 4, w = 00001111 and y = 00. Pumping down gives 001111, containing two 0s and four 1s. The formal argument covers every legal split, not only this illustration.
For reduction direction, begin with known-undecidable A_TM. To prove a new problem B undecidable, construct A_TM <=m B. Reducing B to A_TM does not establish that B is hard.
Theory of Computation preparation for your semester paper
University syllabi differ, so take paper-specific details only from your current syllabus, official scheme and past papers. For GATE scope and completed-paper weightage, see the Theory of Computation for GATE: Syllabus Map, Weightage Audit and Preparation Order; that post owns the exam audit while this one stays with semester sequencing. Audit the last three available official papers. Label each question as trace, conversion, construction, proof or classification.
Turn the audit into six outputs: one correct DFA trace, one NFA-to-DFA conversion, one CFG derivation with parse tree, one PDA stack trace, one Turing-machine tape trace, and one complete pumping or reduction proof. A unit is not finished until you can produce its output without notes.
KnowledgeGate's Theory of Computation question bank contains more than 1,100 questions. Start topic-wise practice only after learning the concept and completing one construction by hand. The count covers the wider subject, not any single university paper.
The short version and your next study action
The dependency chain is DFA and NFA for regular languages, CFG and PDA for context-free structure, Turing machines for general computation, and decidability proofs for the boundary of what algorithms can guarantee. Reproduce the DFA and PDA traces above before moving ahead.
Use the Theory of Computation course for a focused route. The CS Fundamentals category is the simpler browse path if you are still choosing subjects.
Keep learning
Operating Systems Semester Guide: Learn Theory, Solve Numericals and Practise Labs
Connect OS concepts to semester calculations and programs through scheduling, Banker's Algorithm, paging, storage, and five lab checks.
Turing Machines in Theory of Computation: Design, Worked Trace and Decidability
A six-state Turing machine for L = {0^n1^n}: built from the seven-tuple, traced move by move on 0011 to XXYY and q_accept, then proved a decider rather than only a recogniser.
Non-Deterministic Finite Automata (NFA): Design, Epsilon Closures and NFA-to-DFA Conversion
Learn to follow every branch of an NFA without guesswork. Two worked machines connect active-state sets, epsilon closure and a complete eight-state DFA conversion.
Deterministic Finite Automata (DFA): Design, Tracing and Minimisation with Worked Examples
Learn a repeatable way to design DFA states, trace binary inputs, build complements and products, and minimise a complete machine. Every transition is checked through exact tables and worked traces.





