Theory of Computation – Automata & Computability Comprehensive Notes

Computation and Computability

Computation (in Theory of Computation – TOC) is any task that can be executed by a calculator or computer. In TOC we build an abstract machine and ask three meta-questions:

1. Can the machine perform the task?

2. For which problems does the machine succeed?

3. Where are its limitations?

Why Study Computability Theory?

• Limits of computation – some problems are inherently unsolvable by any algorithm.
• Classifying problems – we distinguish:
– Decidable (algorithm exists).
– Undecidable (no algorithm can ever exist).
• Programming-language foundations – grammars, compilers, interpreters rely on formal models from computability.
• Algorithmic guidance – we only optimise after we confirm a problem is solvable.
• Comparing computational models – finite automata, pushdown automata, Turing machines.
• Bridge to complexity theory – once we know a problem is computable we ask how much time/space it costs.
• Ethical & practical implication – prevents wasting resources on the impossible and underpins reliability proofs in safety-critical systems.

Mathematical Modelling and Automata

Natural language is ambiguous; mathematics gives precision, abstraction and formal reasoning.
Automata are the simplest such models. Each automaton is a triple of:

1. States – finite memory.

2. Alphabet $\Sigma$ – finite set of input symbols.

3. Transitions $\delta$ – rules mapping (state,input) → state.
   They model sequential devices (switches, vending machines), software (lexers, parsers) and hardware (sequential circuits).

Basics of Automata Theory

• Study of abstract machines (automata) and the languages they recognise.
• Central notions:

1. Symbol – single character, digit, icon, etc.

2. Alphabet $\Sigma$ – finite, non-empty set of symbols, e.g. $\Sigma = {0,1}$ or ASCII.

3. String / word – finite sequence of symbols from $\Sigma$. Example: $01110$.

4. Empty string $\epsilon$ – length $0$.

5. Length $|w|$ – number of symbols in string $w$.

6. Powers of an alphabet:
   $\Sigma^k$ = set of strings of length $k$.
   $\Sigma^0 = {\epsilon}$, $\Sigma^1 = \Sigma$.

7. Kleene star $\Sigma^* = \bigcup_{k\ge0} \Sigma^k$ – all finite strings.
   $\Sigma^+ = \Sigma^* \setminus {\epsilon}$.

8. Concatenation: if $x=a<em>1\dots a</em>m$ and $y=b<em>1\dots b</em>n$ then $xy=a<em>1\dots a</em>m b<em>1\dots b</em>n$.

Languages and Problems

A language $L$ over $\Sigma$ is any subset $L \subseteq \Sigma^*$. Examples:

1. ${\epsilon,01,0011,000111,\dots}$ – $n$ zeros followed by $n$ ones.

2. Equal numbers of $0$’s and $1$’s.

3. Binary representations of prime numbers.
   Languages can be finite (e.g., all binary strings of length $2$) or infinite (e.g., all strings starting with $a$).

Problem-view: Given $w \in \Sigma^*$, decide whether $w \in L$. A machine that solves this decision problem *recognises* $L$.

Illustrative Finite State Machines

ON/OFF Switch

States ${ON,OFF}$, alphabet ${push}$, start $OFF$, toggling transition. Demonstrates the minimal concept of state memory.

Coffee Vending Machine

States: $S<em>0$ (idle), $S</em>1$ (coin), $S_2$ (dispense). Alphabet ${insert_coin, select_coffee}$. Transition table included in transcript. Shows how automata encode interaction order.

Finite Automata (FA)

Formal 5-tuple ${Q,\Sigma,q<em>0,F,\delta}$ • $Q$ – finite state set. • $\Sigma$ – input alphabet. • $q</em>0 \in Q$ – start state.
• $F \subseteq Q$ – accepting states.
• $\delta : Q \times \Sigma \to Q$ – transition function.

Types:

1. With output – Moore & Mealy machines.

2. Without output – DFA, NFA, $\epsilon$-NFA.

Deterministic Finite Automata (DFA)

• Exactly one next state for every $q$ and $a \in \Sigma$; no $\epsilon$ moves.

Processing a String

Given $w = a<em>1a</em>2\dots a<em>n$, start in $q</em>0$. Recursively compute $q<em>i = \delta(q</em>{i-1},a<em>i)$. If $q</em>n \in F$ → accept, else reject. Language of the DFA = all accepted strings.

Example: Substring $01$

Language $L = {x01y \mid x,y \in {0,1}^*}$. DFA states represent "how close" we are to having seen 01:
• $q<em>0$ – none seen. • $q</em>2$ – last symbol was 0.
• $q<em>1$ – have already seen 01 (accepting). Transitions built accordingly; full tuple $A = ({q</em>0,q<em>1,q</em>2},{0,1},q<em>0,{q</em>1},\delta)$.

Common DFA Exercises

1. Strings ending with $a$ (2 states).

2. $|w| \ge 2$ over ${a,b}$ (accept all of length ≥2).

3. $|w| \le 2$.

4. $|w| = 2$.

5. Minimal DFA for even-length binary strings (two-state modulo-2 counter).

Nondeterministic Finite Automata (NFA)

• $\delta : Q \times \Sigma \to 2^Q$ – may return set of states (incl. empty set).
• Machine branches; conceptually explores all paths in parallel.

Guess & Verify Paradigm

– Guess (branch) at nondeterministic choice points.
– Verify deterministically along each branch.
Input is accepted if any branch ends in $F$ after whole input.

Formal Definition

Tuple ${Q,\Sigma,q_0,F,\delta}$ with set-valued $\delta$.

Example NFA for Strings Ending in $01$

Adds nondeterministic "try now" arc so machine can jump into a two-state checker when it guesses the final 01 has started. Threads that get stuck simply die; acceptance needs one live accepting thread.

$\epsilon$-NFA (NFA with Free Moves)

Special transitions labelled $\epsilon$ allow state changes without consuming input.

Acceptance: There exists a path consisting of input symbols plus any number of $\epsilon$ moves from $q_0$ to some $f \in F$.

Processing Example “ba”

Start $q<em>0 \xrightarrow{\epsilon} q</em>1$, read $b$ to stay in $q<em>1$, read $a$ to reach ${q</em>1,q<em>2}$ → $q</em>2$ is final → accept.

Eliminating $\epsilon$ Moves

1. Compute $\epsilon$-closure($q$) – all states reachable from $q$ via only $\epsilon$.

2. For each state $q$ and symbol $a$:
   – take $\epsilon$-closure($q$);
   – follow $a$ transitions;
   – take $\epsilon$-closure$ again → new transition.

3. A state becomes final in the new NFA if its \epsilon$-closure contains an old final.<br>Worked example with states${q0,q1,q_2}$and alphabet${a}$given in transcript.</p></li></ol><h3 id="be5b703e-e4e8-419b-a4d5-32388f928f11" data-toc-id="be5b703e-e4e8-419b-a4d5-32388f928f11" collapsed="false" seolevelmigrated="true">Converting NFA to DFA – Subset (Powerset) Construction</h3><p>Every NFA has an <strong>equivalent</strong> DFA (same language) even though NFA may appear more powerful.<br>Algorithm:</p><ol><li><p><strong>DFA states</strong> = subsets of NFA states ($2^{|Q|}$possible).</p></li><li><p><strong>Start state</strong> =$\epsilon$-closure($q_0^{NFA}$).</p></li><li><p>For each DFA state$S$and input$a$: <br>$\delta{DFA}(S,a) = \epsilon$-closure$\Big(\bigcup{q\in S} \delta_{NFA}(q,a)\Big)$.</p></li><li><p>DFA accepting states = those subsets containing at least one NFA final state.</p></li></ol><p>Tiny sample: NFA with$q0 \xrightarrow{a} q0, q1; $q1$ accepting. DFA has two states A={q0}$(non-final) and$B={q0,q_1}$(final) with transition$A\xrightarrow{a}B, \; B\xrightarrow{a}B$.</p><h3 id="a6f906e9-f84b-4131-a1e8-c500f76bffb8" data-toc-id="a6f906e9-f84b-4131-a1e8-c500f76bffb8" collapsed="false" seolevelmigrated="true">DFA Minimization</h3><p>Goal: smallest DFA recognising a language.</p><ol><li><p><strong>Remove unreachable</strong> states (graph reachability from$q_0$).</p></li><li><p><strong>Table-filling method</strong>: mark distinguishable pairs (final vs non-final). Iteratively mark pairs whose transitions lead to already-distinguished pairs.</p></li><li><p><strong>Merge</strong> unmarked (equivalent) states.</p></li><li><p>Rebuild DFA.<br>Example in transcript shows 4-state DFA already minimal because every pair became distinguishable.</p></li></ol><h3 id="577e008d-281f-4d8c-8a27-294fa56faa41" data-toc-id="577e008d-281f-4d8c-8a27-294fa56faa41" collapsed="false" seolevelmigrated="true">Practical Applications</h3><p>• <strong>Text search / pattern matching</strong> – NFAs encode the pattern, DFAs perform fast linear scanning (e.g., grep). <br>• <strong>Keyword recognition</strong> in lexical analysis – compiler’s lexer uses a DFA whose states represent longest-prefix matches. Example keyword set${if,int,while}$produced states$q0\dots q9$with deterministic edges; accepting states$q2,q4,q_9$. <br>• <strong>Hardware control</strong> (on/off, vending machine). <br>• <strong>Network protocol validation</strong>, <strong>UI workflows</strong>, <strong>regular expression engines</strong>.</p><h3 id="dcdb2583-8460-4522-9dba-766b14ee9afc" data-toc-id="dcdb2583-8460-4522-9dba-766b14ee9afc" collapsed="false" seolevelmigrated="true">Connections to Further Topics</h3><p>• Once a language is beyond DFA power (e.g., balanced parentheses) we move to <strong>pushdown automata</strong>. <br>• Undecidable properties appear at the Turing-machine level (e.g., Halting Problem). <br>• Complexity classes ($P$,$NP$,$PSPACE$$) build on computability: first ensure solvability, then measure resources.