Theory of Computation (TOC): Complete Guide with Worked Examples

You may be able to solve an isolated DFA trace or grammar derivation yet still wonder how the pieces of Theory of Computation fit together. The thing that connects them is memory. A finite automaton remembers only which of finitely many states it is in, a pushdown automaton adds one stack, and a Turing machine adds an unbounded read-write tape. Give a language the weakest model whose memory is enough for it, and most TOC questions turn mechanical.

Theory of Computation: the question behind every model

Theory of Computation (TOC) studies abstract computational models, the languages they recognise or decide, and the limits of what algorithms can do. Its recurring question is simple: for an input string w and a language L, is w in L?

A Turing machine that halts on every input is a decider, and the language it decides is recursive. This hierarchy compares expressive power, not physical speed. TOC is one of the core subjects on the GATE CS Exam syllabus, and it is examined largely through construction and tracing rather than recall.

Alphabets, strings and languages: the notation TOC uses

Let Sigma = {0,1}, x = 010 and y = 11. Then |x| = 3, concatenation gives xy = 01011, and reversing that string gives (xy)^R = 11010. The symbol epsilon is a string of length 0; the empty language contains no strings at all.

The first powers of the alphabet are:

• Sigma^0 = {epsilon}

• Sigma^1 = {0,1}

• Sigma^2 = {00,01,10,11}

Sigma* is the union of every Sigma^i for i >= 0. Sigma+ = Sigma* minus {epsilon}.

Now define L_even = {w in {0,1}* | w contains an even number of 1s}. The string 0101 belongs to L_even because it has two 1s. The string 0111 does not because it has three. Union, intersection, complement, concatenation and Kleene star are the language operations that later appear in closure questions.

Finite automata and regular languages: trace a DFA completely

Consider L_end01 = {w in {0,1}* | w ends in 01}. A three-state DFA can recognise it:

• q0 is the start state and means there is no useful trailing 0.

• q1 means the current string ends in 0.

• q2 is accepting and means the current string ends in 01.

Its complete transition function is delta(q0,0)=q1, delta(q0,1)=q0, delta(q1,0)=q1, delta(q1,1)=q2, delta(q2,0)=q1, and delta(q2,1)=q0.

Trace 1101 one symbol at a time: q0 -> q0 -> q0 -> q1 -> q2. The machine finishes in accepting state q2, so it accepts. For 1010, the trace is q0 -> q0 -> q1 -> q2 -> q1. It finishes in non-final state q1, so it rejects.

The regular expression (0|1)*01 describes the same language. A DFA, NFA, regular expression and right-linear grammar are equivalent ways to describe regular languages.

Use Finite Automata MCQs: 10 Solved DFA and NFA (GATE) for more practice with the same DFA and NFA reasoning.

Context-free grammars and pushdown automata: when one stack matters

Take the grammar G = ({S},{a,b},P,S) with the production S -> aSb | epsilon. It generates exactly L = {a^n b^n | n >= 0}.

For n = 3, derive the string without skipping a step:

S => aSb => aaSbb => aaaSbbb => aaabbb

The corresponding PDA pushes one marker A for each a, pops one A for each b, and accepts only when the input is finished and the stack has returned to its bottom marker Z0. Trace aabb, writing the stack top first:

• start: Z0

• read a: A Z0

• read a: A A Z0

• read b: A Z0

• read b: Z0, and the input is finished, so the PDA accepts

A finite automaton cannot retain an unbounded count of as, but one stack can hold exactly the count that matching needs. Continue with Context-Free Grammar MCQs: 11 Solved GATE Questions for construction and stack-trace practice.

Turing machines, decidability and the language hierarchy

A Turing machine has state control, a read-write head and an extendable tape. For a tiny computation, begin with 111 blank, where 111 represents unary 3. The machine moves right over all three 1s, writes 1 on the first blank, and halts with 1111 blank, which represents unary 4.

A recogniser accepts every member of its language but may loop on a non-member. A decider halts with accept or reject on every input. Recursive languages are therefore decidable, while recursively enumerable languages are recognisable. The language A_TM = {<M,w> | M accepts w} is recognisable but undecidable.

Each inner family is contained in the outer family, and the labelled examples climb with the memory they require: ends in 01 needs finite state only, a^n b^n needs a stack, and a^n b^n c^n needs a tape bounded by the input. Sitting in an outer class does not by itself force the most powerful model, so always ask which is the weakest one that suffices.

Equivalence, closure and proof tools: choose the right route

Conversions change the representation, not the language. DFA, NFA, regular expression and right-linear grammar describe regular languages. CFG and PDA describe context-free languages. Unrestricted grammar and Turing machine describe recursively enumerable languages.

One important exception is that intersecting a context-free language with a regular language always gives a context-free language.

Two context-free languages can nevertheless intersect to a language that is not context-free. Let L1 = {a^i b^i c^j | i,j >= 0} and L2 = {a^i b^j c^j | i,j >= 0}. Both are context-free. A string in both must have equal counts of a and b from L1, and equal counts of b and c from L2. Therefore L1 intersection L2 = {a^n b^n c^n | n >= 0}, which is not context-free.

Use the regular and context-free pumping lemmas to disprove membership in those families. For undecidability, reductions are the central proof tool.

TOC traps and the way GATE and interviews test them

GATE-style work commonly asks for transition traces, minimum states, regex or automata conversions, CFG derivations, PDA behaviour, closure statements and decidability classifications. Interviews often ask you to construct a small automaton, explain why stack memory is needed, or separate decidable problems from recognisable ones. After learning the concepts, use the GATE Test Series for timed practice.

Theory of Computation: the short version and next step

Use this five-step checklist:

1. Define the language precisely.

2. Identify the memory the task requires.

3. Choose the weakest sufficient model.

4. Simulate it on a concrete string.

5. Use equivalence, closure or a proof tool to justify the answer.

Three examples mark the three kinds of memory: 1101 reaches accepting state q2 in the DFA, aaabbb follows from S -> aSb | epsilon in four derivation steps, and unary 111 becomes 1111 on the Turing-machine tape. Finite state, one stack, and a general tape, in that order.

For a structured route through TOC alongside the other GATE CS subjects, continue with GATE Guidance by Sanchit Sir. Keep asking the same question: what must this machine remember to recognise the language?