Theory of Computation

1. Introduction

1.1 Why Theory Matters

The theory of computation provides the mathematical foundations for computer science. It answers Fundamental questions: What can be computed? What cannot? How efficiently? These answers guide the Design of algorithms, programming languages, compilers, and hardware.

1.2 Alphabets, Strings, and Languages

An alphabet $\Sigma$ is a finite, non-empty set of symbols (e.g., $\Sigma = \{0, 1\}$).

A string (or word) over $\Sigma$ is a finite sequence of symbols from $\Sigma$. The empty string Is denoted $\varepsilon$.

Notation:

• $\Sigma^*$: The set of all strings over $\Sigma$ (including $\varepsilon$).
• $\Sigma^+$: The set of all non-empty strings over $\Sigma$.
• $|w|$: The length of string $w$. $|\varepsilon| = 0$.
• $w^R$: The reversal of $w$.
• $\Sigma^n$: Strings of length $n$ over $\Sigma$.

A language $L$ over $\Sigma$ is any subset of $\Sigma^*$. The empty language is $\emptyset$ (distinct from $\{\varepsilon\}$Which contains one string).

Operations on languages:

• Union: $L_1 \cup L_2 = \{w : w \in L_1 \mathrm{ or} w \in L_2\}$.
• Intersection: $L_1 \cap L_2 = \{w : w \in L_1 \mathrm{ and} w \in L_2\}$.
• Concatenation: $L_1 \cdot L_2 = \{w_1 w_2 : w_1 \in L_1, w_2 \in L_2\}$.
• Kleene star: $L^* = \{\varepsilon\} \cup L \cup L^2 \cup \cdots$.
• Complement: $\overline{L} = \Sigma^* \setminus L$.

1.3 Examples of Formal Languages

Formal languages arise throughout computer science. Here are representative examples Organised by complexity class.

Finite languages (always regular):

• $L_1 = \{\mathrm{true}, \mathrm{false}\}$ — the set of Boolean literals.
• $L_2 = \{w \in \{0,1\}^* : |w| \leq 3\}$ — all binary strings of length at most 3.

Regular languages (decidable by finite automata):

• $L_3 = \{w \in \{0,1\}^* : w \mathrm{ contains} the substring 101\}$.
• $L_4 = \{w \in \{0,1\}^* : w \mathrm{ has} an even number of 1\mathrm{s}\}$.
• $L_5 = \{w \in \{0,1\}^* : w \mathrm{ interpreted} in binary is divisible by 3\}$.

Context-free but not regular:

• $L_6 = \{a^n b^n : n \geq 0\}$ — matching counts of two symbols.
• $L_7 = \{w w^R : w \in \{0,1\}^*\}$ — even-length palindromes.
• $L_8 = \{w \in \{a,b,c\}^* : n_a(w) = n_b(w)\}$ — equal numbers of aS and bS.

Decidable but not context-free:

• $L_9 = \{a^n b^n c^n : n \geq 0\}$.
• $L_{10} = \{\langle G \rangle : G \mathrm{ is} a connected undirected graph\}$.

Undecidable (Turing-recognisable):

• $A_{\mathrm{TM} = \{\langle M, w \rangle : M \mathrm{ accepts} w\}}$ — the acceptance problem.
• \mathrm{HALT_}{\mathrm{TM} = \{\langle M, w \rangle : M \mathrm{ halts} on w\}}.

Not even Turing-recognisable:

• $\overline{A_{\mathrm{TM}}}$ — the complement of the acceptance problem.

This hierarchy illustrates the central theme of the course: as we move to more expressive language Classes, the corresponding machines become more powerful, but certain properties (decidability, Closure under complement) may be lost.

1.4 Countability and Cardinality

An important foundational observation is that the set of all languages over $\Sigma$ is uncountable, while the set of all Turing machines (and hence the set of all decidable Languages) is countable.

Theorem 1.1. The set of all languages over a non-empty alphabet $\Sigma$ is uncountable.

Proof. The set $\Sigma^*$ is countable (enumerate strings by length, then lexicographically). The set of all languages is $\mathcal{P}(\Sigma^*)$Which is uncountable by Cantor”s theorem (since $|\mathcal{P}(S)| \gt |S|$ for any set $S$). $\blacksquare$

Theorem 1.2. The set of all Turing machines is countable.

Proof. Each TM has a finite description (its states, alphabet, and transition function). Encode This as a string over a finite alphabet. The set of all finite strings is countable. $\blacksquare$

Corollary 1.3. There exist languages that are not Turing-recognisable (in fact, uncountably Many such languages).

This follows because there are uncountably many languages but only countably many TMs. The set Of Turing-recognisable languages is a countable subset of the uncountable set of all languages.

Cantor’s diagonalisation. The classic proof of Theorem 1.1 uses diagonalisation: assume the Set of all languages is countable, list them as $L_1, L_2, L_3, \ldots$And construct a language $D$ that differs from each $L_i$ on the $i$-th string. Then $D$ is not in the list — contradiction. This technique reappears in the proof of undecidability of $A_{\mathrm{TM}}$ (Section 5.2).

2. Regular Languages

2.1 Finite Automata

A deterministic finite automaton (DFA) is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where:

• $Q$ is a finite set of states.
• $\Sigma$ is the input alphabet.
• $\delta : Q \times \Sigma \to Q$ is the transition function.
• $q_0 \in Q$ is the start state.
• $F \subseteq Q$ is the set of accepting (final) states.

$M$ accepts a string $w = w_1 w_2 \cdots w_n$ if the sequence of states $q_0, \delta(q_0, w_1), \delta(\delta(q_0, w_1), w_2), \ldots$ ends in a state in $F$.

Example. DFA for strings over $\{0, 1\}$ containing the substring 01:

$M = (\{q_0, q_1, q_2\}, \{0, 1\}, \delta, q_0, \{q_2\})$

A nondeterministic finite automaton (NFA) allows multiple transitions from a state on the same Symbol, and $\varepsilon$-transitions (transitions without consuming input). Formally, $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$.

$M$ accepts $w$ if there exists some path of transitions consuming $w$ that ends in a state in $F$.

2.2 Equivalence of DFA and NFA

Theorem 2.1. For every NFA $N$There exists a DFA $D$ such that $L(N) = L(D)$.

Proof (subset construction). Given NFA $N = (Q, \Sigma, \delta, q_0, F)$Construct DFA $D = (Q', \Sigma, \delta', q_0', F')$ where:

• $Q' = \mathcal{P}(Q)$ (each state of $D$ is a subset of states of $N$).
• $q_0' = \varepsilon\mathrm{-closure(\{q_0\})}$.
• $\delta'(S, a) = \varepsilon\mathrm{-closure(\bigcup_{q \in S} \delta(q, a))}$ for $S \subseteq Q$ $a \in \Sigma$.
• $F' = \{S \subseteq Q : S \cap F \neq \emptyset\}$.

Every string accepted by $N$ has some path through $N$‘s states. The subset construction tracks all Possible states $N$ could be in after reading each symbol. $D$ accepts exactly when at least one Possibility in $N$ leads to acceptance. $\blacksquare$

Corollary 2.2. NFA, DFA, and NFA with $\varepsilon$-transitions all recognise exactly the class of Regular languages.

2.3 Regular Expressions

Definition. Regular expressions over $\Sigma$ are defined inductively:

1. $\emptyset$ (empty set), $\varepsilon$ (empty string), and $a$ for each $a \in \Sigma$ are regex.
2. If $R_1$ and $R_2$ are regex, then $(R_1 \cup R_2)$, $(R_1 \cdot R_2)$And $(R_1^*)$ are regex.
3. Nothing else is a regex.

Shorthand: $R^+$ means $R \cdot R^*$. $R?$ means $(R \cup \varepsilon)$.

Examples:

• $(0 \cup 1)^* 00 (0 \cup 1)^*$: strings containing 00.
• $1^* 01^* 01^*$: strings with exactly two 0S.
• $(0 \cup 1)^*$: all strings over $\{0, 1\}$.
• $\emptyset$: the empty language.

Regex identities. The following algebraic laws hold for regular expressions and can be used To simplify or reason about them:

These identities can be used to prove that two regex describe the same language, analogous to Simplifying algebraic expressions. Two regex $R_1$ and $R_2$ are equivalent (written $R_1 \equiv R_2$) If $L(R_1) = L(R_2)$.

2.4 Equivalence of Regular Expressions and Finite Automata

Theorem 2.3 (Kleene). A language is regular if and only if it is described by some regular Expression.

Proof (sketch).

Regex to NFA: Induction on the structure of the regex.

• Base cases: $\emptyset$, $\varepsilon$, $a$ each have trivial NFAs.
• Union: Combine two NFAs with a new start state and $\varepsilon$-transitions to each.
• Concatenation: Connect the accept states of the first NFA to the start state of the second via $\varepsilon$-transitions.
• Kleene star: Add $\varepsilon$-transitions from a new start state to the NFA’s start and from the NFA’s accept states back to the start state.

NFA to regex: State elimination. Systematically eliminate states of the NFA one at a time, Updating the transition labels (which are regex) between remaining states. The final label from start To accept is the equivalent regex. $\blacksquare$

Thompson’s construction. The regex-to-NFA translation can be made fully explicit. For each Sub-expression of the regex, we build a small NFA fragment with exactly one entry and one exit State, connected by $\varepsilon$-transitions. The construction guarantees that the NFA has at most One accept state, no transitions into the start state, and no transitions out of the accept state.

Theorem 2.3a (Thompson’s construction correctness). For every regular expression $R$ over $\Sigma$Thompson’s construction produces an NFA $N_R$ with $L(N_R) = L(R)$And $N_R$ has $O(|R|)$ States and transitions.

Proof. By structural induction on $R$.

• Base cases:

• $R = \emptyset$: $N_R$ has a start state and an accept state with no transitions. $L(N_R) = \emptyset = L(\emptyset)$.

• $R = \varepsilon$: $N_R$ has a start state, an accept state, and an $\varepsilon$-transition between them. $L(N_R) = \{\varepsilon\} = L(\varepsilon)$.

• $R = a$ for $a \in \Sigma$: $N_R$ has a start state, an accept state, and a transition on $a$. $L(N_R) = \{a\} = L(a)$.

• Inductive cases:

• $R = R_1 \cup R_2$: By IH, $L(N_{R_1}) = L(R_1)$ and $L(N_{R_2}) = L(R_2)$. Thompson adds a new start $s$ and accept $f$ with $\varepsilon$-transitions to the start states of $N_{R_1}$ and $N_{R_2}$And $\varepsilon$-transitions from their accept states to $f$. Any accepting path goes through exactly one sub-NFA, so $L(N_R) = L(R_1) \cup L(R_2) = L(R)$.

• $R = R_1 \cdot R_2$: Thompson connects the accept state of $N_{R_1}$ to the start state of $N_{R_2}$ via $\varepsilon$-transitions. A string $w \in L(N_R)$ iff $w = w_1 w_2$ where $w_1 \in L(N_{R_1})$ and $w_2 \in L(N_{R_2})$I.e., $w \in L(R_1) \cdot L(R_2) = L(R)$.

• $R = R_1^*$: Thompson adds a new start $s$ and accept $f$With $\varepsilon$-transitions from $s$ to $f$ (allowing zero repetitions) and from $s$ to the start of $N_{R_1}$And from the accept of $N_{R_1}$ back to $s$. Any accepting path corresponds to zero or more traversals of $N_{R_1}$So $L(N_R) = L(R_1)^* = L(R)$.

In all cases, the number of states added is a constant per operator, so $|N_R| = O(|R|)$. $\blacksquare$

2.5 DFA Minimisation and the Myhill-Nerode Theorem

Theorem 2.4 (Myhill-Nerode). The following are equivalent for a language $L$:

1. $L$ is regular.
2. The Myhill-Nerode equivalence relation has finitely many equivalence classes.
3. $L$ is the union of some of the equivalence classes.

Definition. Two strings $x, y$ are distinguishable with respect to $L$ if there exists $z$ Such that exactly one of $xz, yz$ is in $L$. The Myhill-Nerode equivalence $\equiv_L$ is: $x \equiv_L y$ iff $x$ and $y$ are not distinguishable.

Proof of Theorem 2.4.

(1) $\Rightarrow$ (2): Let $D = (Q, \Sigma, \delta, q_0, F)$ be a DFA for $L$. Define $x \sim y$ iff $\delta^*(q_0, x) = \delta^*(q_0, y)$ (i.e., $D$ reaches the same state on $x$ and $y$). Then $\sim$ has at most $|Q|$ equivalence classes. We show $\sim = \equiv_L$. If $x \sim y$Then for All $z$, $\delta^*(q_0, xz) = \delta^*(q_0, yz)$So $xz \in L$ iff $yz \in L$Meaning $x \equiv_L y$. Conversely, if $x \not\equiv_L y$There exists $z$ with $xz \in L$ and $yz \notin L$ (or vice versa), so $\delta^*(q_0, xz) \neq \delta^*(q_0, yz)$Hence $x \not\sim y$.

(2) $\Rightarrow$ (3): Trivial, since $L$ consists of all strings whose equivalence class is one That contains at least one string in $L$.

(3) $\Rightarrow$ (1): Suppose $\equiv_L$ has finitely many equivalence classes $C_1, \ldots, C_k$. Construct a DFA with one state per equivalence class, start state $[x]_{\equiv_L}$ for $x = \varepsilon$ Transition $\delta'([x], a) = [xa]$And accept states = those classes contained in $L$. This DFA is Well-defined because $\equiv_L$ is a right congruence: if $x \equiv_L y$Then $xa \equiv_L ya$ for all $a \in \Sigma$. $\blacksquare$

Corollary 2.5. The minimum-state DFA for $L$ has exactly as many states as there are Equivalence classes of $\equiv_L$.

Minimisation algorithm:

1. Start with two partitions: F (accepting states) and Q \ F (non-accepting).
2. Repeatedly refine: for each pair (p, q) in the same partition,
   if delta(p, a) and delta(q, a) are in different partitions for some a,
   split p and q into different partitions.
3. Repeat until no further splitting occurs.
4. Each partition becomes a state in the minimised DFA.

This algorithm runs in $O(n^2 k)$ time where $n$ is the number of states and $k = |\Sigma|$.

2.6 Pumping Lemma for Regular Languages

Theorem 2.6 (Pumping Lemma). If $L$ is regular, then there exists a constant $p$ (the pumping Length) such that for every string $w \in L$ with $|w| \geq p$, $w$ can be decomposed as $w = xyz$ satisfying:

1. $|y| \gt 0$ (the pumped part is non-empty).
2. $|xy| \leq p$ (the pumpable part is within the first $p$ symbols).
3. $xy^iz \in L$ for all $i \geq 0$.

Proof. Let $D$ be a DFA for $L$ with $n$ states. Set $p = n$. For any string $w$ of length $\geq n$ The path through $D$ visits at least $n + 1$ states, so by the pigeonhole principle, some state is Visited twice within the first $p$ symbols. The substring $y$ between the two visits can be repeated Or removed ($xy^iz$) without affecting acceptance. $\blacksquare$

Using the pumping lemma to prove non-regularity. To show $L$ is not regular, assume it is, let $p$ Be the pumping length, and exhibit a string $w \in L$ with $|w| \geq p$ such that every Decomposition $w = xyz$ satisfying (1) and (2) has some $i$ with $xy^iz \notin L$.

Example. $L = \{0^n 1^n : n \geq 0\}$ is not regular.

Proof. Assume $L$ is regular with pumping length $p$. Let $w = 0^p 1^p \in L$. By (2), $|xy| \leq p$So $y$ consists only of 0S. Let $|y| = k \gt 0$. Then $xy^0 z = 0^{p-k} 1^p \notin L$ (since $p - k \neq p$). Contradiction. $\blacksquare$

Example. $L = \{ww : w \in \{0,1\}^*\}$ is not regular.

Proof. Assume pumping length $p$. Let $w = 0^p 1 0^p 1 \in L$. Since $|xy| \leq p$, $y = 0^k$ for Some $k \gt 0$. Then $xy^0 z = 0^{p-k} 1 0^p 1 \notin L$ (the two halves have different lengths). $\blacksquare$

Example. $L = \{0^n 1^m : n \neq m\}$ is not regular.

Proof. Assume $L$ is regular with pumping length $p$. Since regular languages are closed under Complement, $\overline{L} = \{0^n 1^m : n = m\} \cup \{w : w \notin 0^* 1^*\}$ would also be regular. Then $\overline{L} \cap 0^* 1^* = \{0^n 1^n : n \geq 0\}$ would be regular (since $0^* 1^*$ is regular And regular languages are closed under intersection). But $\{0^n 1^n : n \geq 0\}$ is not regular — Contradiction. $\blacksquare$

:::caution Common Pitfall The pumping lemma says that for every decomposition satisfying (1) and (2), there exists a Pumping that fails. To prove non-regularity, you must show that all valid decompositions lead To a contradiction. A single decomposition that works is insufficient to disprove the lemma. The converse of the pumping lemma is false: if a language satisfies the pumping condition, it is Not necessarily regular. :::

2.7 Closure Properties of Regular Languages

Regular languages are closed under:

Theorem 2.7 (Intersection via product construction). If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ is regular.

Proof. Let $D_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ and $D_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$. Construct $D = (Q_1 \times Q_2, \Sigma, \delta, (q_1, q_2), F_1 \times F_2)$ where $\delta((r_1, r_2), a) = (\delta_1(r_1, a), \delta_2(r_2, a))$. Then $D$ accepts $w$ iff both $D_1$ and $D_2$ accept $w$I.e., $w \in L_1 \cap L_2$. $\blacksquare$

Theorem 2.7. If $L_1$ is regular and $L_2$ is not regular, then $L_1 \cap L_2$ may or may not be Regular. Closure properties do not apply when one operand is non-regular.

3. Context-Free Languages

3.1 Context-Free Grammars

A context-free grammar (CFG) is a 4-tuple $G = (V, \Sigma, R, S)$ where:

• $V$ is a finite set of variables (non-terminals).
• $\Sigma$ is a finite set of terminals.
• $R \subseteq V \times (V \cup \Sigma)^*$ is a finite set of production rules.
• $S \in V$ is the start variable.

A production $A \to \alpha$ means variable $A$ can be replaced by string $\alpha$.

Example. CFG for $L = \{a^n b^n : n \geq 0\}$:

$S \to aSb \mid \varepsilon$

Example. CFG for balanced parentheses:

$S \to (S) \mid SS \mid \varepsilon$

Example. CFG for $\{w \in \{0,1\}^* : w = w^R\}$ (palindromes):

$S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \varepsilon$

Example. CFG for $L = \{a^i b^j c^k : i = j + k\}$:

$S \to aSb \mid T, \quad T \to aTc \mid \varepsilon$

The variable $S$ generates the $a^i b^i$ part, and $T$ generates the $a^k c^k$ part. Since $S \Rightarrow^* a^i S b^i \Rightarrow a^i T b^i \Rightarrow^* a^{i+k} c^k b^i$The total number Of bS and cS equals the total number of aS.

Example. CFG for strings with equal numbers of 0S and 1S:

$S \to 0S1 \mid 1S0 \mid SS \mid \varepsilon$

The first two rules add a matched pair (in either order); the third concatenates two balanced Strings; the fourth handles the empty string.

Example. CFG for the language of all strings over $\{a, b\}$ that are not palindromes:

$S \to aAb \mid bAa \mid aSa \mid bSb \mid a \mid b, \quad A \to aAa \mid aAb \mid bAa \mid bAb \mid a \mid b$

Here $S$ generates non-palindromes and $A$ generates arbitrary strings of length $\geq 1$.

3.2 Parse Trees and Ambiguity

A parse tree (derivation tree) for a string $w$ according to grammar $G$ is a tree where:

• The root is labelled $S$.
• Internal nodes are labelled with variables.
• Leaves are labelled with terminals (or $\varepsilon$).
• Children of a node labelled $A$ are the symbols of the right-hand side of a production $A \to \alpha$ in left-to-right order.

A CFG is ambiguous if some string in its language has two or more distinct parse trees (equivalently, Two or more leftmost derivations or two or more rightmost derivations).

Example (ambiguous). $S \to S + S \mid S \times S \mid \mathrm{id}$. The string $\mathrm{id} + \mathrm{id} \times \mathrm{id}$ has two parse trees: $S + (S \times S)$ and $(S + S) \times S$.

Removing ambiguity. Some ambiguous grammars can be made unambiguous by rewriting the productions To enforce a particular evaluation order. For the arithmetic expression grammar:

$E \to E + T \mid T, \quad T \to T \times F \mid F, \quad F \to (E) \mid \mathrm{id}$

This grammar is unambiguous and enforces the standard precedence ($\times$ before $+$) and left Associativity.

Example. $L = \{a^i b^j c^k : i = j \mathrm{ or} j = k\}$ is inherently ambiguous. (Proof omitted; Any grammar must have two competing mechanisms for the two conditions, and these Interfere.)

3.3 Chomsky Normal Form

A CFG is in Chomsky Normal Form (CNF) if every production is of the form:

• $A \to BC$ (two variables), or
• $A \to a$ (single terminal), or
• $S \to \varepsilon$ (only the start variable, and $S$ does not appear on the right of any rule).

Theorem 3.1. Every CFG has an equivalent CFG in Chomsky Normal Form.

Proof (conversion algorithm).

1. Add a new start variable $S_0$ with rule $S_0 \to S$ (ensures $S$ does not appear on any right side if it generates $\varepsilon$).
2. Remove all $\varepsilon$-productions $A \to \varepsilon$ (except possibly $S_0 \to \varepsilon$). For each occurrence of $A$ in a right-hand side, add a variant without $A$.
3. Remove all unit productions $A \to B$. For each chain $A \Rightarrow^* B$Add $A \to \alpha$ for each $B \to \alpha$.
4. Convert remaining rules: replace terminals $a$ in right-hand sides of length $\geq 2$ with new variables $T_a$ and rules $T_a \to a$. Replace right-hand sides of length $\geq 3$ by introducing intermediate variables. $\blacksquare$

3.4 Pushdown Automata

A pushdown automaton (PDA) is a 6-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$ where:

• $Q$ is a finite set of states.
• $\Sigma$ is the input alphabet.
• $\Gamma$ is the stack alphabet.
• $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times (\Gamma \cup \{\varepsilon\}) \to \mathcal{P}(Q \times (\Gamma \cup \{\varepsilon\}))$ is the transition function.
• $q_0 \in Q$ is the start state.
• $F \subseteq Q$ is the set of accepting states.

A PDA can read input, push symbols onto the stack, pop symbols from the stack, and make $\varepsilon$-moves (without consuming input or changing the stack).

Example. PDA for $L = \{a^n b^n : n \geq 0\}$:

1. Push a marker \text{\}$ onto the stack.
2. For each aPush X onto the stack.
3. For each bPop X from the stack.
4. Accept if the stack is empty (just the marker) and all input is consumed.

Formally: states $q_0$ (start), $q_1$ (pushing), $q_2$ (popping), $q_3$ (accept).