Theory of Computation Notes

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 3-tuple.
• A 2-tuple 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 self-loop 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_{n-1}\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 non-empty.
• A language is a set of strings formed from an alphabet.
• A prefix-free 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 prefix-free because "a" is a proper prefix of both "ab" and "abc". But, $L' = \{"\text{a}", "\text{bb}", "\text{cba}"\}$ is considered to be prefix-free.

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 5-tuple $(Q, \Sigma, \delta, q_0, F)$ where:

1. $Q$ is a finite set of states
2. $\Sigma$ is a finite alphabet
3. $\delta : Q \times \Sigma \to Q$ is the transition function
4. $q_0 \in Q$ is the start state
5. $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 (non-deterministic 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.

1. $Q$ is a finite set of states
2. $\Sigma$ is a finite alphabet
3. $\delta : Q \times \Sigma_\epsilon \to \mathcal{P}(Q)$ is the transition function
4. $q_0 \in Q$ is the start state
5. $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$.

1. $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$.
2. $\Sigma$, the alphabet, is the same as in $M_1$ and $M_2$.
3. 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))$.
4. $q_0$ is the pair $(q_1, q_2)$.
5. $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$.

1. $Q = \{q_0\} \cup Q_1 \cup Q_2$
2. $q_0$ is the new start state of $N$
3. $F = F_1 \cup F_2$
4. Define $\delta$ so that for any $q \in Q$ and any $a \in \Sigma_\epsilon$:

$$\delta(q, a) = \begin{cases} \delta_1(q, a) & q \in Q_1 \\ \delta_2(q, a) & q \in Q_2 \\ \{q_1, q_2\} & q = q_0 \land a = \epsilon \\ \varnothing & q = q_0 \land a \neq \epsilon \end{cases}$$

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$.

1. $Q = Q_1 \cup Q_2$
2. $\Sigma = \Sigma_1 \cup \Sigma_2$
3. $q_0 = q_1$
4. $F = F_2$
5. Define $\delta$ so that for any $q \in Q$ and any $a \in \Sigma_\epsilon$:

$$\delta(q, a) = \begin{cases} \delta_1(q, a) & q \in Q_1 \land q \notin F_1 \\ \delta_1(q, a) & q \in F_1 \land a \neq \epsilon \\ \delta_1(q, a) \cup \{q_2\} & q \in F_1 \land a = \epsilon \\ \delta_2(q, a) & q \in Q_2 \end{cases}$$

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^*$.

1. $Q = \{q_0\} \cup Q_1$. The states of $N$ are also the states of $N_1$ plus a newly added state.
2. The state $q_0$ (the newly added state) is the new start state.
3. $F = \{q_0\} \cup F_1$. The newly added state is then added to the set of old accept states.
4. Define $\delta$ so that for any $q \in Q$ and any $a \in \Sigma_\epsilon$:

$$\delta(q,a) = \begin{cases} \delta_1(q,a) & q \in Q_1 \land q \notin F_1 \\ \delta_1(q,a) & q \in F_1 \land a \neq \epsilon \\ \delta_1(q,a) \cup \{q_1\} & q \in F_1 \land a = \epsilon \\ \{q_1\} & q = q_0 \land a = \epsilon \\ \varnothing & q = q_0 \land a \neq \epsilon \end{cases}$$

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$.

1. $Q = Q_1 \cup \{q_0\}$
2. $q_0$ is the new start state
3. $F = \{q_1\}$
4. 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$.

1. $Q = Q_A \times Q_B \times \{A, B\}$
2. $q_0 = (q_{0,A},q_{0,B}, A)$
3. $F = F_A \times F_B \times \{A, B\}$
4. Define $\delta$ so that for any $q \in Q_A$, any $r \in Q_B$, and any $a \in \Sigma$:

$$\delta((q, r, A), a) = (\delta_A(q, a), r, B) \\ \delta((q, r, B), a) = (q, \delta_B(r, a), A)$$

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

1. $Q' = \mathcal{P}(Q)$, note that $|\mathcal{P}(Q)| = 2^{|Q|}$ where $|Q|$ is the size of $Q$
2. For $R \in Q'$ and $a \in \Sigma$,

$$\delta'(R, a) = \bigcup_{r \in R}\delta(r, a)$$

3. $q_0' = \{q_0\}$
4. $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:

1. Build NFA $\delta$ table.

2. Define initial state to be the states reachable from $q_0$ on epsilon transitions: $q_0' = (q_0, q_1)$.
3. Draw $M$ with initial state $q_0' = (q_0, q_1)$. And, the state $\varnothing$ self loops when reading any symbol in the alphabet.
4. 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.
5. Define accepting states to be the states containing $q_0$.

Regular Expressions

$R$ is a regular expression if $R$ is

1. $a$ for some $a$ in the alphabet $\Sigma$
2. $\epsilon$, representing the language containing a single string—the empty string
3. $\varnothing$, representing the language containing no strings
4. $(R_1 \cup R_2)$ where $R_1$ and $R_2$ are regular expressions
5. $(R_1 \circ R_2)$ where $R_1$ and $R_2$ are regular expressions
6. $(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:

1. $R = a, a \in \Sigma, L(R) = \{a\}$
2. $R = \epsilon, L(R) = \{\epsilon\}$
3. $R = \varnothing, L(R) = \varnothing$
4. $R = R_1 \cup R_2$, see nondeterministic version of the union operation proof
5. $R = R_1 \circ R_2$, see concatenation operation proof
6. $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')$:

1. $Q' = Q \cup \{q_s', q_f'\}$
2. $\Sigma$ remains the same
3. $q_s'$ is the new start state
4. $F = \{q_f'\}$
5. Define $\delta'$ so that for any $q \in Q'$ and any $a \in \Sigma_\epsilon$:

$$\delta'(q,a) = \begin{cases} \{q1\} & q = q_s' \land a = \epsilon \\ \{q_f'\} & q \in F_1 \land a = \epsilon \\ \delta_1(q, a) & q \in Q_1 \land a \in \Sigma \\ \varnothing & \text{otherwise} \end{cases}$$

Step 2. Convert GNFA into regular expressions

There are two rules when collapsing a GNFA into a 2-state:

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?