Theory of Computation

Sheet 1

Finite Automata & Regular Languages

4 formulas

Core concepts

• Regular languages closed under: union, intersection, complement, concatenation, star, reversal

Key formulas

DFA (5-tuple) ☆

\[ (Q,\Sigma,\delta,q_0,F) \]

δ: Q×Σ→Q, total

NFA ☆

\[ \delta: Q\times\Sigma\to 2^{Q} \]

partial, multiple/ε-moves

Subset Construction Bound ☆

\[ 2^n \text{ states} \]

for an n-state NFA

Pumping Lemma (Regular) ☆

\[ \exists p,\ \forall w{:}\ |w|\ge p,\ w{=}xyz,\ |xy|\le p,\ |y|\ge 1,\ xy^iz\in L \]

Test your recall

Can you recall the dfa (5-tuple) formula?

Reveal formula

\[ (Q,\Sigma,\delta,q_0,F) \]

GATE traps 4 traps

NFA→DFA can blow up exponentially

Every NFA has an equivalent DFA (same language), but the DFA can need exponentially more states -- 2^n in the worst case. GATE often asks for exactly this worst-case blow-up.

Pumping lemma only proves non-regularity

The pumping lemma can only be used to PROVE a language is NOT regular (by contradiction) -- it can never be used to prove a language IS regular. A very common proof-technique misuse.

Closure doesn't carry over to CFLs

Regular languages are closed under complement and intersection, but this does NOT extend to context-free languages (which are not closed under either in general) -- don't assume closure properties carry over between language classes.

DFA, NFA, ε-NFA are equally powerful

DFA, NFA, and epsilon-NFA all recognize exactly the same class (regular languages) -- equal power, different succinctness. GATE tests whether you know they're equally expressive despite looking structurally different.

Sheet 2

Context-Free Languages & Pushdown Automata

4 formulas

Core concepts

• PDA accepts by final state or by empty stack -- both define exactly the CFLs

Key formulas

CFG (4-tuple) ☆

\[ (V,\Sigma,R,S) \]

Chomsky Normal Form ☆

\[ A\to BC \text{ or } A\to a \]

CYK Membership ☆

\[ O(n^3) \]

needs CNF

Pumping Lemma (CFL) ☆

\[ \exists p,\ \forall z{:}\ |z|\ge p,\ z{=}uvwxy,\ |vwx|\le p,\ |vx|\ge 1,\ uv^iwx^iy\in L \]

Test your recall

Can you recall the cfg (4-tuple) formula?

Reveal formula

\[ (V,\Sigma,R,S) \]

GATE traps 4 traps

a^n b^n is CF but not regular

Regular subset-of context-free (regular is a strict subset) -- {a^n b^n} is the textbook language that's context-free but NOT regular, and GATE loves variations of it.

CFLs aren't closed under intersection

CFLs are closed under union, concatenation, and star, but NOT closed under intersection or complement in general -- the intersection of two CFLs can be non-context-free, a frequently tested closure-property trap.

Prove ambiguity with two derivations

An ambiguous grammar has at least one string with two different parse trees (or leftmost derivations) -- GATE often expects you to actually construct both derivations to prove ambiguity, not just assert it.

DPDAs are strictly weaker than PDAs

Deterministic PDAs are strictly weaker than general PDAs (DCFLs is a strict subset of CFLs) -- unlike the DFA=NFA equivalence for regular languages, this is a commonly confused parallel.

Sheet 3

Turing Machines & Decidability

2 formulas

Core concepts

• Recursive (decidable): some TM always halts and correctly accepts/rejects
• Recursively enumerable (Turing-recognizable): some TM accepts, may loop forever on reject
• Halting problem: undecidable, but recursively enumerable
• Rice's theorem: any non-trivial property of the language a TM recognizes is undecidable

Key formulas

Recursive vs. RE ☆

\[ \text{Recursive} \subset \text{Recursively Enumerable} \]

Recursive iff Both RE ☆

\[ L \text{ is recursive} \iff L \text{ and } \overline{L} \text{ are both RE} \]

Test your recall

Can you recall the recursive vs. re formula?

Reveal formula

\[ \text{Recursive} \subset \text{Recursively Enumerable} \]

GATE traps 4 traps

Undecidable ≠ not RE

'Undecidable' does NOT mean 'not recursively enumerable' -- the halting problem IS recursively enumerable (simulate and accept if it halts), it's just not recursive/decidable since non-halting can't always be detected. One of the most heavily tested TOC concepts.

Rice's theorem is about semantics

Rice's theorem applies only to semantic properties (about the LANGUAGE a TM recognizes), not syntactic properties of the TM's own description -- e.g. 'does this TM have exactly 5 states' is decidable, since it's about structure, not behavior.

Undecidable ≠ unsolvable for every instance

A problem being undecidable doesn't mean no instance can ever be solved -- it means no single algorithm decides ALL instances correctly, a common conceptual misreading.

Reduce FROM a known undecidable problem

To prove a new problem is undecidable, reduce a KNOWN undecidable problem TO it, not the other way around -- reducing in the wrong direction is a frequent proof error.

Closure Properties of Language Classes

Core concepts

• A language class is "closed" under an operation if applying that operation to language(s) from the class always produces a language still in that class.

Key formulas

Reading the table: \(L, L_1, L_2\) all belong to the column's class unless stated otherwise.

Reference table

Operation	Regular	DCFL	CFL	CSL	Rec	RE
\(L_1 \cup L_2\)	✓	✗	✓	✓	✓	✓
\(L_1 \cap L_2\)	✓	✗	✗	✓	✓	✓
\(L_1 \cdot L_2\)	✓	✗	✓	✓	✓	✓
\(L_1 - L_2\)	✓	✗	✗	✓	✓	✗
\(L^*\)	✓	✗	✓	✓	✓	✓
\(L^+\)	✓	✗	✓	✓	✓	✓
\(L^R\)	✓	✗	✓	✓	✓	✓
\(\overline{L}\) (complement)	✓	✓	✗	✓	✓	✗
\(h(L)\) (homomorphism)	✓	✗	✓	✗	✗	✓
\(h^{-1}(L)\) (inverse hom.)	✓	✓	✓	✓	✓	✓

GATE traps

1The four facts that get tested the most: DCFL is closed under complement but NOT union or intersection -- the opposite of what most people guess.

2CFL is closed under union, concatenation and star, but NOT under intersection or complement -- CFL \(\cap\) CFL need not be CFL.

3RE is NOT closed under complement -- that's exactly why Rec = RE \(\cap\) co-RE, and why "complement of RE" questions are a favorite trap.

4CSL IS closed under complement (Immerman-Szelepcsenyi theorem) -- easy to assume otherwise since it feels like the "hard" class.

Decidability & Undecidability of Problems

Core concepts

• D = decidable (an algorithm exists that always halts with the right yes/no answer). UD = undecidable (no such algorithm exists).
• Read a column as the whole triple it stands for: Type-3/Regular/FA, DCFG/DCFL/DPDA, CFG/CFL/PDA, CSG/CSL/LBA, Rec/HTM, Type-0/RE/TM.

Reference table

Problem	Regular	DCFL	CFL	CSL	Rec	RE
Membership	D	D	D	D	D	UD
Emptiness	D	D	D	UD	UD	UD
Finiteness	D	D	D	UD	UD	UD
Completeness (\(L = \Sigma^*\))	D	D	UD	UD	UD	UD
Regularity	D	D	UD	UD	UD	UD
Ambiguity	D	D	UD	UD	UD	UD
Equivalence	D	D	UD	UD	UD	UD
Disjointness	D	UD	UD	UD	UD	UD
Subset	D	UD	UD	UD	UD	UD

GATE traps

1Must-read before the exam -- this table alone accounts for a disproportionate share of TOC marks, and the pattern is consistent: everything is decidable up through DCFL, and from CFL onward almost everything except Membership, Emptiness and Finiteness flips to undecidable.

2The single most-missed cell: Equivalence is DECIDABLE for DCFL (Senizergues' theorem, 1997) -- students assume undecidable because it's such a hard result, but Subset/containment for DCFL, unlike Equivalence, really is undecidable. Don't mix the two up.

3Completeness, Regularity, Ambiguity and Equivalence all follow the exact same D-D-UD-UD-UD-UD pattern across the six classes -- memorize the pattern once, not four separate rows.

4Recursive (Rec) languages have decidable Membership only -- Emptiness/Finiteness/etc. are undecidable even for a language you already know is decidable, since deciding a *property* of an arbitrary decider is a different (and generally undecidable, by Rice's theorem) question from running that decider.