Theory of Computation

The formal limits of machines: automata and the languages they recognise, the Chomsky hierarchy, undecidability, and what P versus NP actually claims.

If you remember nothing else

A DFA and an NFA recognise exactly the same class of languages — non-determinism adds convenience, never power.
The Chomsky hierarchy in order: regular ⊂ context-free ⊂ context-sensitive ⊂ recursively enumerable, each strictly contained in the next.
Finite automata have no memory beyond their state, which is why they cannot recognise aⁿbⁿ — counting is unbounded.
The halting problem is undecidable: no algorithm can decide, for every program and input, whether that program halts.
NP-complete means in NP and NP-hard; NP-hard alone means at least as hard as everything in NP but possibly not in NP itself.
P vs NP asks whether every problem whose solution is quickly verifiable is also quickly solvable. It is open.

6 chapters

1Languages and the Chomsky hierarchy
2Finite automata
3Regular expressions and the pumping lemma
4Context-free grammars and pushdown automata
5Turing machines and decidability
6P, NP and NP-completeness

Languages and the Chomsky hierarchy

An alphabet $Σ$ is a finite non-empty set of symbols.
A string is a finite sequence of symbols from $Σ$ ; $ϵ$ denotes the empty string, of length 0.
$Σ^{*}$ is the set of all strings over $Σ$ , including $ϵ$ ; $Σ^{+}$ excludes $ϵ$ .
A language is any subset of $Σ^{*}$ — possibly empty, possibly infinite.

Type	Grammar	Language class	Recognised by	Production form
Type 3	Regular	Regular	Finite automaton	$A \to a B$ or $A \to a$
Type 2	Context-free	Context-free	Pushdown automaton	$A \to γ$ — a single non-terminal on the left
Type 1	Context-sensitive	Context-sensitive	Linear bounded automaton	$α A β \to α γ β$ , never shortening
Type 0	Unrestricted	Recursively enumerable	Turing machine	Any $α \to β$

Each class is strictly contained in the one above it: regular ⊂ context-free ⊂ context-sensitive ⊂ recursively enumerable.

Finite automata

	DFA	NFA
Transitions per symbol	Exactly one	Zero, one or many
ε-transitions	Not allowed	Allowed
Acceptance	The single run ends in an accepting state	Some run ends in an accepting state
States needed	Can be exponentially more	Often far fewer
Ease of construction	Harder	Easier
Expressive power	Identical	Identical

Moore machine — output depends on the state alone. Mealy machine — output depends on the state and the current input, so it can react one step sooner. They are interconvertible; a Moore machine may need one extra state.
DFA minimisation (Myhill-Nerode / table-filling) removes unreachable states and merges equivalent ones. The minimal DFA for a regular language is unique up to renaming, which is why minimisation can prove two DFAs equivalent.

Regular expressions and the pumping lemma

Operation	Notation	Meaning
Union	$r + s$ or $r ∣ s$	Either
Concatenation	$rs$	One then the other
Kleene star	$r^{*}$	Zero or more repetitions — includes $ϵ$
Kleene plus	$r^{+}$	One or more repetitions

Kleene's theorem ties the pieces together: a language is regular iff it is described by a regular expression, iff it is accepted by a finite automaton. The three formulations are interchangeable.

Plain textProving L = {aⁿbⁿ | n >= 0} is not regular

Assume L is regular with pumping length p.
Choose w = a^p b^p, which is in L and has length 2p >= p.

By condition (2), |xy| <= p, so xy lies entirely inside the a's.
Therefore y consists only of a's, and by (1) y has at least one a.

Pump with i = 2:  xy^2 z  has MORE a's than b's.
That string is not in L, contradicting condition (3).

Therefore L is not regular.

Intuition: a finite automaton has finitely many states, so it cannot
count an unbounded number of a's in order to match them against b's.

Regular languages are closed under	Yes/No
Union, concatenation, Kleene star	Yes
Intersection, complement, difference	Yes
Reversal, homomorphism	Yes

Regular languages are closed under every common operation — a useful proof technique: if closure would produce a known non-regular language, the original cannot be regular.

Context-free grammars and pushdown automata

Plain textA grammar and the language it generates

S -> aSb | ε        generates  { a^n b^n | n >= 0 }

Derivation of aaabbb:
  S => aSb => aaSbb => aaaSbbb => aaabbb

This is the canonical context-free but NOT regular language - the
stack of a PDA does the counting that a finite automaton cannot.

S -> aSb | bSa | SS | ε   generates strings with equal a's and b's.

Plain textThe classic ambiguous expression grammar

E -> E + E | E * E | id

The string  id + id * id  has two parse trees:
   (id + id) * id     and     id + (id * id)

Fix by encoding precedence and associativity into the grammar:
   E -> E + T | T          (+ is lower precedence, left associative)
   T -> T * F | F          (* binds tighter)
   F -> id | ( E )

This is exactly what a compiler's parser needs, which is why the
same grammar reappears in compiler design.

Normal form	Production shape	Used for
Chomsky Normal Form (CNF)	$A \to BC$ or $A \to a$	The CYK parsing algorithm; every derivation of a length-n string takes exactly $2 n - 1$ steps
Greibach Normal Form (GNF)	$A \to a α$ — a terminal first	Guarantees a terminal is consumed at every step, so no left recursion

Context-free languages are closed under	Yes/No
Union, concatenation, Kleene star	Yes
Intersection	No
Complement	No
Intersection with a regular language	Yes

The standard counterexample: {aⁿbⁿcᵐ} and {aⁿbᵐcᵐ} are both context-free, but their intersection {aⁿbⁿcⁿ} is not.

Turing machines and decidability

	Recursive (decidable)	Recursively enumerable
The machine	Always halts, accepting or rejecting	Halts and accepts on strings in the language; may loop forever on strings not in it
Also called	Turing-decidable	Turing-recognisable, semi-decidable
Closed under complement	Yes	No
Example	Is this string a palindrome?	Does this program halt on this input?

The halting problem

Plain textThe diagonalisation argument

Suppose HALTS(P, I) exists and decides whether program P halts on input I.

Construct:
    function TROUBLE(P):
        if HALTS(P, P):
            loop forever
        else:
            halt

Now ask: does TROUBLE(TROUBLE) halt?

  If it halts  -> then HALTS(TROUBLE, TROUBLE) returned true
               -> so TROUBLE took the "loop forever" branch
               -> it does NOT halt.  Contradiction.

  If it loops  -> then HALTS(TROUBLE, TROUBLE) returned false
               -> so TROUBLE took the "halt" branch
               -> it DOES halt.  Contradiction.

Both cases are impossible, so HALTS cannot exist.

P, NP and NP-completeness

Class	Definition	Examples
P	Decidable by a deterministic Turing machine in polynomial time	Sorting, shortest path, primality testing, linear programming
NP	A proposed solution can be verified in polynomial time	SAT, Hamiltonian cycle, subset sum, graph colouring
NP-hard	Every problem in NP reduces to it in polynomial time. Need not be in NP — need not even be decidable	Halting problem, TSP optimisation version
NP-complete	In NP and NP-hard — the hardest problems that are still in NP	SAT, 3-SAT, clique, vertex cover, Hamiltonian cycle, subset sum

Theory of Computation

If you remember nothing else

1Languages and the Chomsky hierarchy

2Finite automata

3Regular expressions and the pumping lemma

4Context-free grammars and pushdown automata

5Turing machines and decidability