Theory of Computation Notes
— 22 min read
Table of Contents
Introduction
These are my notes on theory of computation.
Mathematical Notions and Terminology
This section covers the fundamental building blocks.
Sets
A set is a group of objects. It can contain any type of object like numbers, symbols, and other sets. The objects in a set are called elements or members. In a set, the ordering of elements and repetition doesn't matter.
For example:
$S = \{7, 21, 57\}$Definitions
 $\in$ and $\notin$ means membership and nonmembership
 $7 \in \{7, 21, 57\}$ and $8 \notin \{7, 21, 57\}$
 $A \subseteq B$ is read as $A$ is a subset of $B$. It means that all elements of $A$ is also in $B$.
 $A \subsetneq B$ is read as $A$ is a proper subset of $B$. It means that all elements of $A$ is also in $B$, BUT $A$ is not exactly the same as $B$, that is, $A$ has fewer elements.
 $\{n \mid \text{rule about }n\}$ describes a set containing elements according to a rule.
 $A \cup B$ describes the union of two sets $A$ and $B$, combining all elements from both into a single set.
 $A \cap B$ describes the intersection of two sets $A$ and $B$, containing only the elements common to both.
 $\overline{A}$ is the complement of A, containing all elements not in $A$.
 $\mathcal{P}(A)$ is the power set of $A$, containing all possible subsets of $A$, including the empty set and $A$ itself.
 $A \times B$ is the Cartesian product or cross product of $A$ and $B$, is the set containing all ordered pairs $(a, b)$ where the first element $a \in A$ and the second element $b \in B$. Read as $A$ cross $B$.
 Cartesian products can involve more than just pairs: $A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \dots, a_n) \mid a_i \in A_i \text{ for each } i \in \{1, 2, \dots, n\}\}$
 $\underbrace{A \times A \times \cdots \times A}_{k} = A^k$ is a Cartesian product of a set with itself.
Examples
 Natural numbers: $\mathbb{N}$ = {1, 2, 3, ...}
 Integers: $\mathbb{Z}$ = {..., 2, 1, 0, 1, 2, ...}
 Empty set: $\varnothing$
 Singleton set: a set with one element, e.g., $\{a\}$
 Unordered pair: a set with two elements, e.g., $\{a, b\}$
 $\{n \mid n=m^2 \text{ for some } m\in\mathbb{N}\}$: the set of perfect squares
 If $A = \{0, 1\}$, then $\mathcal{P}(A) = \{\varnothing, \{0\}, \{1\}, \{0, 1\}\}$.
 $\{(0, 0), (0, 1), (1, 0), (1, 1)\}$ is the set of all ordered pairs whose elements are 0s and 1s.
 Let $A = \{1, 2\}$ and $B = \{x, y\}$
 $A \times B = \{(1, x), (1, y), (2, x), (2, y)\}$
 $\mathbb{N}^2 = \mathbb{N} \times \mathbb{N} = \{(i,j) \mid i,j \geq 1\}$
Sequences and Tuples
A sequence is a list of objects in some order designated with parentheses. In sequences, order and repetition matters.
For example:
$(7, 21, 57) \neq (57, 7, 21) \\ (7, 7, 21, 57) \neq (7, 21, 57)$However:
$\{7, 21, 57\} = \{7, 21, 7, 57\}$ Finite sequences are called tuples.
 A $k$tuple is a sequence with $k$ elements. $(7, 21, 57)$ is a 3tuple.
 A 2tuple is called an ordered pair.
Functions and Relations
A function is a thing that takes an input and produces and output. Similarly, given $f(a) = b$, $f$ is a mapping, that is, $f$ maps $a$ to $b$. The same input always yields the same output.
 Domain: the set of all possible inputs of a function
 Range: the set of all possible outputs of a function, also called the codomain
 Given a domain $D$ and a range $R$, $f : D \to R$, is read as $f$ maps $D$ to $R$. This is called a function notation or mapping notation. Writing this function notation is also said to be "defining the codomain".
 A function is onto or surjective if all elements in the output set $R$ is matched or mapped by at least one element from the input set $D$. This means the function reaches every possible output. The codomain must be defined in order to determine if a function is onto or not.
 A binary relation R is reflexive if for every $x$, $xRx$
 A binary relation R is symmetric if for every $x$ and $y$, $xRy$ implies $yRx$
 A binary relation R is transitive if for every $x$, $y$, and $z$, $xRy$ and $yRz$ implies $xRz$
 A binary relation R is an equivalence relation if $R$ is reflexive, symmetric, AND transitive.
Examples
 $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x$ is onto.
 $f : \mathbb{R} \to [0, \infty)$ defined by $f(x) = x$ is NOT onto.
Graphs
 An undirected graph or graph is a set of points with lines connecting (or not) the points.
 The points are referred to as vertices or nodes.
 The lines are called edges.
 The degree of a node refers to the number of edges at that node.
 A selfloop is an edge from a node to itself.
 Given a graph $G$ containing nodes $i$ and $j$, the pair $(i,j)$ represents the edge connecting $i$ and $j$. The order of the pair doesn't matter in an undirected graph, i.e., $(i,j)$ and $(j,i)$ is the same edge. Another way to describe these undirected edges with unordered pairs is with set notation: $\{i,j\}$
 Given a graph $G$, $V$ being the set of nodes of $G$, and $E$ being the set of edges of $G$, $G = (V, E)$. This can be used to formally describe graphs.
 A labeled graph is a graph with labels on nodes and/or edges.
 Given a graph $G$, a graph $H$ is considered to be a subgraph of $G$ if $H$ is formed by a subset of the vertices and edges of $G$.
 A path is a sequence of nodes connected by edges in a graph.
 A simple path is a path that doesn't repeat any nodes.
 A graph is connected if every two nodes in that graph have a path between them.
 A cycle is a path that starts and ends at the same vertex.
 A simple cycle is one that contains at least three nodes and repeats only the first and last nodes.
 A tree is a graph that is connected and has no simple cycles.
 The leaves of a tree are nodes with a degree 1.
 A directed graph uses arrows instead of lines. This set of edges in directed graphs have ordered pairs.
 Outdegree refers to the number of arrows pointing out from a node.
 Indegree refers to the number of arrows pointing into a node.
 A directed path refers to a path in which all the arrows point in the same direction as it steps.
 A directed graph is strongly connected if a directed path connects every two nodes.
Strings and Languages
An alphabet is a nonempty finite set whose members are called symbols.
Examples of alphabets:
$\begin{align*} \Sigma_1 &= \{0, 1\} \\ \Sigma_2 &= \{\text{a}, \text{b}, \text{c}, \ldots, \text{z}\} \\ \Gamma &= \{0, 1, \text{x}, \text{y}, \text{z}\} \end{align*}$A string over an alphabet is a finite sequence of symbols from that alphabet. For example, given $\Sigma_1$ from above, then "01001" is a string over $\Sigma_1$. Another example, given $\Sigma_2$ from above, "abracadabra" is a string over $\Sigma_2$.
 $w$ is the length or number of symbols in the string $w$ over $\Sigma$.
 A string of length zero is called the empty string denoted by $\epsilon$. It plays the role of a 0 in a number system. For example: if $w="\text{hello}"$, then $w \cdot \epsilon = \epsilon \cdot w = "\text{hello}"$. The $\cdot$ here indicates string concatenation.
 If string $w$ has length $n$, then $w = w_1w_2\cdots w_n$ where each $w_i\in \Sigma$. For example: $w = "\text{cat}"$ then $w_1 = "\text{c}"$, $w_2 = "\text{a}"$, and $w_3 = "\text{t}"$.
 $w^\mathcal{R}$ is the reverse of $w$, i.e., $w_nw_{n1}\cdots w_1$
 $w^k$ concatenates a string with itself $k$ times, e.g., $\underbrace{xx\cdots x}_k$
 Lexicographic order is a way of ordering strings, e.g., a dictionary.
 Shortlex order or string order orders strings with shorter strings always coming first. E.g., the string ordering of all strings over the alphabet $\{0, 1\}$ is $(\epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots)$.
 A string $x$ is considered to be a prefix of string $y$ if a string $z$ exists where $xz = y$. In other words, string $x$ is a prefix of another string $y$ if you can append some string $z$ to $x$ to get $y$. E.g., let $x = "\text{pre}"$ and $y = "\text{prefix}"$, then $z = "\text{fix}"$.
 A string $x$ is a proper prefix of string $y$ if $x$ is a prefix of $y$ and $x \neq y$. This means $z$ must be nonempty.
 A language is a set of strings formed from an alphabet.
 A prefixfree language is a language where no strings in the language is a proper prefix of any other string in the language. E.g., $L = \{"\text{a}", "\text{ab}", "\text{abc}"\}$ is NOT prefixfree because "a" is a proper prefix of both "ab" and "abc". But, $L' = \{"\text{a}", "\text{bb}", "\text{cba}"\}$ is considered to be prefixfree.
Boolean Logic
Boolean logic is a mathematical system based on the values TRUE and FALSE represented as 1 and 0.
Boolean Operations

Negation (NOT): The operation that inverts a Boolean value.
 $\neg 0 = 1$
 $\neg 1 = 0$

Conjunction (AND): The operation that results in 1 if both operands are 1.
 $0 \land 0 = 0$
 $0 \land 1 = 0$
 $1 \land 0 = 0$
 $1 \land 1 = 1$

Disjunction (OR): The operation that results in 1 if at least one operand is 1.
 $0 \lor 0 = 0$
 $0 \lor 1 = 1$
 $1 \lor 0 = 1$
 $1 \lor 1 = 1$

Exclusive OR (XOR): The operation that results in 1 if one operand is 1 and the other is 0.
 $0 \oplus 0 = 0$
 $0 \oplus 1 = 1$
 $1 \oplus 0 = 1$
 $1 \oplus 1 = 0$

Equality (XNOR): The operation that results in 1 if both operands are the same.
 $0 \leftrightarrow 0 = 1$
 $0 \leftrightarrow 1 = 0$
 $1 \leftrightarrow 0 = 0$
 $1 \leftrightarrow 1 = 1$

Implication: The operation that results in 0 only if the first operand is 1 and the second is 0.
 $0 \rightarrow 0 = 1$
 $0 \rightarrow 1 = 1$
 $1 \rightarrow 0 = 0$
 $1 \rightarrow 1 = 1$
Boolean Identities
Boolean operations can be expressed in terms of AND and NOT:
 $P \lor Q = \neg(\neg P \land \neg Q)$
 $P \rightarrow Q = \neg P \lor Q$
 $P \leftrightarrow Q = (P \rightarrow Q) \land (Q \rightarrow P)$
 $P \oplus Q = \neg(P \leftrightarrow Q)$
Distributive Law
Boolean logic follows distributive laws similar to arithmetic:
 $P \land (Q \lor R) = (P \land Q) \lor (P \land R)$
 $P \lor (Q \land R) = (P \lor Q) \land (P \lor R)$
Theory of Computation
There three are central areas of the theory of computation:
 Automata theory
 Computability theory
 Complexity theory
This question connects all three areas:
What are the fundamental capabilities and limitations of computers?
Automata Theory
Automata theory is about the definitions and properties of mathematical properties of computation.
DFA
DFA (deterministic finite automata) is a state machine with states (nodes) and transitions (edges) labeled with symbols.
DFA Formal Definition
A finite automata is a 5tuple $(Q, \Sigma, \delta, q_0, F)$ where:
 $Q$ is a finite set of states
 $\Sigma$ is a finite 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 states
If $A$ is the set of all strings that machine $M$ accepts, we say that $A$ is the language of machine $M$ and write $L(M) = A$. We say that $M$ recognizes $A$ or that $M$ accepts $A$.
Formal Definition of Computation
A language is called a regular language if some finite automaton recognizes it.
Regular Operations
Let $A$ and $B$ be languages. We define regular operations union, concatenation, and star:
 Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$
 Concatenation: $A \circ B = \{ xy \mid x \in A \text{ and } y \in B \}$
 Star: $A^* = \{ x_1 x_2 \ldots x_k \mid k \geq 0 \text{ and each } x_i \in A \}$, the empty string $\epsilon$ is always a member of $A^*$ no matter what $A$ is
NFA
NFA (nondeterministic finite automata) is a type of state machine where the machine may transition into multiple possible states from a given state and input symbol. It can also have transitions that occur without consuming any input called $\epsilon$transitions.
Differences Between DFA and NFA
 Every state of a DFA always has exactly one exiting transition arrow for each symbol in the alphabet.
 In an NFA, a state may have zero, one, or many exiting arrows for each alphabet symbol.
 NFAs can have $\epsilon$transitions. In particular, a state with only one transition, that being an $\epsilon$transition, can split into two copies, one that follows the exiting $\epsilon$transition and one staying at the current state.
NFA Formal Definition
Similar to DFA except the transition function takes a state and an input symbol or the empty string and produces the set of possible next states.
 $Q$ is a finite set of states
 $\Sigma$ is a finite alphabet
 $\delta : Q \times \Sigma_\epsilon \to \mathcal{P}(Q)$ is the transition function
 $q_0 \in Q$ is the start state
 $F \subseteq Q$ is the set of accepting states
Union Operation Proof
There are two versions of this proof, one that doesn't use nondeterminism and one that does.
Deterministic Version
Let DFA $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ recognize $A_1$.
Let DFA $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$ recognize $A_2$.
Construct DFA $M = (Q, \Sigma, \delta, q_0, F)$ to recognize $A_1 \cup A_2$.
 $Q = \{(r_1, r_2) \mid r_1 \in Q_1 \land r_2 \in Q_2\}$. This set is the Cartesian product of sets $Q_1$ and $Q_2$ and is written $Q_1 \times Q_2$. It is the set of all pairs of states, the first from $Q_1$ and the second from $Q_2$.
 $\Sigma$, the alphabet, is the same as in $M_1$ and $M_2$.
 For each $(r_1, r_2) \in Q$ and $a \in \Sigma$, let $\delta((r_1,r_2), a) = (\delta_1(r_1, a), \delta_2(r_2, a))$.
 $q_0$ is the pair $(q_1, q_2)$.
 $F$ is the set of pairs in which either member is an accept state of $M_1$ or $M2$: $F = \{(r_1, r_2) \mid r_1 \in F_1 \lor r_2 \in F_2\}$. This can be also written as $F = (F_1 \times Q_2) \cup (Q_1 \times F_2)$.
Nondeterministic Version
Let $N_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ recognize $A_1$.
Let $N_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$ recognize $A_2$.
Construct NFA $N = (Q, \Sigma, \delta, q_0, F)$ to recognize $A_1 \cup A_2$.
 $Q = \{q_0\} \cup Q_1 \cup Q_2$
 $q_0$ is the new start state of $N$
 $F = F_1 \cup F_2$
 Define $\delta$ so that for any $q \in Q$ and any $a \in \Sigma_\epsilon$:
Concatenation Operation Proof
Let $N_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ recognize $A_1$.
Let $N_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$ recognize $A_2$.
Construct NFA $N = (Q, \Sigma, \delta, q_0, F)$ to recognize $A_1 \circ A_2$.
 $Q = Q_1 \cup Q_2$
 $\Sigma = \Sigma_1 \cup \Sigma_2$
 $q_0 = q_1$
 $F = F_2$
 Define $\delta$ so that for any $q \in Q$ and any $a \in \Sigma_\epsilon$:
Kleene Star Operation Proof
Let $N_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ recognize $A_1$.
Construct NFA $N = (Q, \Sigma, \delta, q_0, F)$ to recognize $A_1^*$.
 $Q = \{q_0\} \cup Q_1$. The states of $N$ are also the states of $N_1$ plus a newly added state.
 The state $q_0$ (the newly added state) is the new start state.
 $F = \{q_0\} \cup F_1$. The newly added state is then added to the set of old accept states.
 Define $\delta$ so that for any $q \in Q$ and any $a \in \Sigma_\epsilon$:
Reverse Operation Proof
Let $N_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ that recognizes $A_1$.
Construct NFA $N = (Q, \Sigma, \delta, q_0, F)$ to recognize $A_1^R$.
 $Q = Q_1 \cup \{q_0\}$
 $q_0$ is the new start state
 $F = \{q_1\}$
 For any $a \in \Sigma_\epsilon$, $\delta(r, a) \to q$ if $\delta_1(q, a) \to r$ and $\delta(q_0, \epsilon) \to F_1$
Perfect Shuffle Proof
Let $D_A = (Q_A, \Sigma, \delta_A, q_{0,A}, F_A)$ recognize $A$.
Let $D_B = (Q_B, \Sigma, \delta_B, q_{0,B}, F_B)$ recognize $B$.
Let $S = \{w \mid w = a_1b_1a_2b_2 \cdots a_kb_k \text{ where } a_1a_2\cdots a_k \in A \text{ and } b_1b_2\cdots b_k \in B\}$
Construct DFA $N = (Q, \Sigma, \delta, q_0, F)$ to recognize $S$.
 $Q = Q_A \times Q_B \times \{A, B\}$
 $q_0 = (q_{0,A},q_{0,B}, A)$
 $F = F_A \times F_B \times \{A, B\}$
 Define $\delta$ so that for any $q \in Q_A$, any $r \in Q_B$, and any $a \in \Sigma$:
NFA to DFA
Given an NFA, there is an equivalent DFA.
Let NFA $N = (Q, \Sigma, \delta, q_0, F)$ recognize $A$.
Construct DFA $M = (Q', \Sigma, \delta', q_0', F')$ to recognize $A$.
Assuming No Epsilon Transitions
 $Q' = \mathcal{P}(Q)$, note that $\mathcal{P}(Q) = 2^{Q}$ where $Q$ is the size of $Q$
 For $R \in Q'$ and $a \in \Sigma$,
 $q_0' = \{q_0\}$
 $F' = \{R \in Q' \mid R \text{ contains an accept state of } N\}$
Assuming Epsilon Transitions
i am lost, this proof omg
NFA to DFA Example
Given the above example NFA $N = ((q_0, q_1, q_2), \{a, b\}, \delta, q_0, \{q_0\})$ ($\epsilon$ is implicitly in the language), we construct a DFA $M = (Q' = \mathcal{P}(Q), \{a, b\}, \delta', q_0', F')$ in the following:
 Build NFA $\delta$ table.
$a$  $b$  $\epsilon$  

$q_0$  $\{q_0, q_1\}$  $\varnothing$  $\{q_1\}$ 
$q_1$  $\{q_2\}$  $\{q_0\}$  $\varnothing$ 
$q_2$  $\varnothing$  $\{q_0, q_2\}$  $\{q_0\}$ 
 Define initial state to be the states reachable from $q_0$ on epsilon transitions: $q_0' = (q_0, q_1)$.
 Draw $M$ with initial state $q_0' = (q_0, q_1)$. And, the state $\varnothing$ self loops when reading any symbol in the alphabet.
 Draw transitions whereafter the first transition, look to the epsilon column and, if it's not an empty set (epsilon column entry), include it in the tuple.
 Define accepting states to be the states containing $q_0$.
Regular Expressions
$R$ is a regular expression if $R$ is
 $a$ for some $a$ in the alphabet $\Sigma$
 $\epsilon$, representing the language containing a single string—the empty string
 $\varnothing$, representing the language containing no strings
 $(R_1 \cup R_2)$ where $R_1$ and $R_2$ are regular expressions
 $(R_1 \circ R_2)$ where $R_1$ and $R_2$ are regular expressions
 $(R_1^*)$ where $R_1$ is a regular expression
Regex Examples
Given $\Sigma = \{0, 1\}$, in the format $\{w \mid w \; \text{<condition>}\}$:
 $w$ contains a single 1: $0^*10^*$, star means zero or more
 $w$ has at least one 1: $\Sigma^*1\Sigma^*$, $\Sigma$ means any symbol in the alphabet
 $w$ contains the substring 001: $\Sigma^*001\Sigma^*$
 every 0 in $w$ is followed by at least one 1: $1^*(01+)^*$, plus means one or more
 $w$ is a string of even length: $(\Sigma\Sigma)^*$, a string of 0 length is even
 the length of $w$ is a multiple of 3: $(\Sigma\Sigma\Sigma)^*$
 the language $\{01, 10\}$: $01 \cup 10$
 $w$ starts and ends with the same symbol: $0\Sigma^*0 \cup 1\Sigma^*1 \cup 0 \cup 1$
 $(0 \cup \epsilon)1^* = 01^* \cup 1^*$, $0 \cup \epsilon$ describes $\{0, \epsilon\}$, and the concatenation adds either 0 or $\epsilon$ before every string in $1^*$
 $(0 \cup \epsilon)(1 \cup \epsilon) = \{\epsilon, 0, 1, 01\}$, it's kind of like the FOIL method
 $1^*\varnothing = \varnothing$, concatenating the empty set to any set yields the empty set
 $\varnothing^* = \{\epsilon\}$
Let $R$ be any expression, we have the following identities:
 $R \cup \varnothing = R$, adding the empty language to any other language will not change it
 $R \circ \epsilon = R$, joining any string to the empty string will not change it
 $R \cup \epsilon$ may not equal $R$, e.g., if $R = 0$, then $L(R) = \{0\}$ but $L(R \cup \epsilon) = \{0, \epsilon\}$
 $R \circ \varnothing$ may not equal $R$, e.g., if $R = 0$, then $L(R) = \{0\}$ but $L(R \circ \varnothing) = \varnothing$
Regex to NFA
Let regular expression $R$ describe some language $A$.
Convert $R$ into an NFA recognizing $A$.
There are six cases:
 $R = a, a \in \Sigma, L(R) = \{a\}$
 $R = \epsilon, L(R) = \{\epsilon\}$
 $R = \varnothing, L(R) = \varnothing$
 $R = R_1 \cup R_2$, see nondeterministic version of the union operation proof
 $R = R_1 \circ R_2$, see concatenation operation proof
 $R = R_1^*$, see kleene star operation proof
DFA to Regex
Let a DFA recognize a language $A$.
Convert the DFA into equivalent regular expressions in following steps:
Step 1. Convert DFA into a GNFA (generalized nondeterministic finite automaton)
Let DFA $D_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ recognize $A$.
We construct GNFA $G = (Q', \Sigma, \delta', q_s', F')$:
 $Q' = Q \cup \{q_s', q_f'\}$
 $\Sigma$ remains the same
 $q_s'$ is the new start state
 $F = \{q_f'\}$
 Define $\delta'$ so that for any $q \in Q'$ and any $a \in \Sigma_\epsilon$:
This construction does not explicitly redefine the transitions into regular expressions over $\Sigma$. We just do that in our heads.
Step 2. Convert GNFA into regular expressions
There are two rules when collapsing a GNFA into a 2state:
DFA to Regex Example
Computability Theory
The main objective of computability theory is to classify problems as solvable or unsolvable
Complexity Theory
The main objective of complexity theory is to classify problems as easy or hard.
An important question capturing this idea:
What makes some problems computationally hard and others easy?