Theory of Computation

| Jump Ahead

• 000 | Math Terms
• 001 | Automata Theory
• 002 | Computability Theory
• 003 | Complexity Theory

000 | Math Terms

| Sets

| Set Basics

A SET is an unordered collection of objects that are called elements or members. For example, $A = \{0, 1, 3, 4, 5, 6\}$ is a set. The elements/members of $A$ are $1, 2, 3, 4, 5,$ and $6$.

| Common Sets

— $\mathbb{N}$ Natural Numbers: The set of all positive integers sometimes includes 0).
— $\mathbb{Z}$ Integers: The set of all whole numbers, both positive and negative.
— $\mathbb{Q}$ Rational Numbers: Numbers that can be expressed as a fraction where .
— $\mathbb{R}$ Real Numbers: All rational and irrational numbers.
— $\{\}$ or $\empty$ Empty Set: A set that contains no elements.

| Set Relations

A SUBSET ($\subseteq$) of a set is a set whose elements are all contained within a greater/equal set.

For example,

$A = \{0, 1, 3, 4, 5, 6\}$
$B = \{0, 1, 3\}$
$C = \{0, 1, 3, 4, 5, 6\}$

The sets $B$ and $C$ are both subsets of $A$, because every element in $B$ and every element in $C$ is also an element of $A$.

We write this as $B, C \subseteq A$.

---

A PROPER SUBSET ($\subset$) of a set is a set whose elements are all contained within a greater set.

For example,

$A = \{0, 1, 3, 4, 5, 6\}$
$B = \{0, 1, 3\}$
$C = \{0, 1, 3, 4, 5, 6\}$

The sets $B$ and $C$ are both subsets of $A$, but only $B$ is a proper subset of $A$ because it is not equal to $A$.

We write this as $B \subset A$.

| Set Operations

— UNION ($\cup$)
— INTERSECTION ($\cap$)
— DIFFERENCE ($-$ or $\setminus$)
— COMPLEMENT (of a set $A$; $\overline{A}$)
— CARTESIAN/CROSS PRODUCT ($\times$)
— POWER SET (of a set $I$; $\mathcal{P}(I)$)

| Sequences and Tuples

A SEQUENCE is a list of objects, finite or infinite, in some order, and a TUPLE is a finite sequence.

001 | Automata Theory

| Automata Basics

Automata theory is the study of mathematical models of computation: how they are defined and what their properties are.

Alphabet

An alphabet ($\Sigma$) is a set of elements that are called symbols.

For example, the following sets are alphabets:

$\Sigma_0 = \{0,1\}$
$\Sigma_1 = \{a, b, c, d, e, f, g\}$

String

A string is a finite sequence of symbols from a given alphabet.

For example,

If $\Sigma_{abc} = \{a, b, c\}$,
and $w = aabbccb$,
then $w$ is a string over the alphabet $\Sigma_{abc}$.

Language

A language is nothing more than a set of strings.

Finite State Machine/Finite Automaton

A finite state machine/finite automaton is a computational model.

These models can be expressed as diagrams, where states are represented as nodes and transitions between states are represented as labeled directed edges.

They can also be expressed formally as a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where the first element is finite set called the states $(Q)$, second is a finite set called the alphabet $(\Sigma)$, third is the transition function $(\delta)$, fourth is the start state $(q_0$ or $q_{start})$, and fifth is the finite set of accept states $(F)$.

State

A state represents a finite state machine/finite automaton's current position in its process and what it is prepared to do next.

Transition

A transition describes how finite state machine/finite automaton's changes from one state to another as it reads input.

Start State

A start state is the state where a finite state machine/finite automaton begins its computation before reading any input.

Accept State

An accept state, also called a final state, is a state that indicates a successful computation.

Language of a Machine

The language of a machine is the set of all strings that the machine accepts.

For example,
Let $M = (Q, \Sigma, \delta: Q \times \Sigma \rarr Q, q_0, F)$ be a "machine".
And, let $A$ be the set of all strings that machine $M$ accepts.
We would say $A$ is the language of $M$ and write $L(M) = A$.

| Finite Automata

Deterministic Finite Automata (DFA)

A deterministic finite automata (DFA) can be expressed as a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where:

$Q$ is a finite set called the STATES.
$\Sigma$ is a finite set called the ALPHABET.
$\delta: Q \times \Sigma \rarr Q$ is the TRANSITION FUNCTION.
$q_0$ or $q_{start} \isin Q$ is the START STATE.
$F \subseteq Q$ is the finite set of ACCEPT STATES.

For example, let $M_1 = (Q, \Sigma, \delta: Q \times \Sigma \rarr Q, q_0, F)$, where:

$Q = \{q_1, q_2, q_3\}$
$\Sigma = \{0, 1\}$
$\delta = \begin{array}{c|cc} & 0 & 1 \\ \hline q_1 & q_1 & q_2 \\ q_2 & q_3 & q_2 \\ q_3 & q_2 & q_2 \end{array}$
$q_{start} = q_1$
$F = \{q_2\}$

Nondeterministic Finite Automata (NFA)

A nondeterministic finite automata (NFA) can be expressed as a 5-tuple ($Q, \Sigma_\varepsilon, \delta, q_{start}, F$), where:

$Q$ is a finite set called STATES.
$\Sigma_\varepsilon$ or $\Sigma_\lambda$ is a finite set called the ALPHABET that includes the empty string ($\varepsilon$ or $\lambda$).
$\delta: Q \times \Sigma_\varepsilon \rarr \mathcal{P}(Q)$ is the TRANSITION FUNCTION.
$q_{start} \isin Q$ is the START STATE.
$F \subseteq Q$ is the set of ACCEPT STATES.

The Difference Between DFA's and NFA's

First, every state of a DFA always has exactly one exiting transition for each symbol in the alphabet. That is not the case for NFA's, in which case states can have zero, one, or many exiting transition for each symbol in the alphabet. Thus, a DFA’s transition function maps each pair in $Q \times \Sigma$ to a single element of $Q$, while an NFA’s transition function maps each pair in $Q \times \Sigma_\lambda$ to an element of $\mathcal{P}(Q)$, the power set of $Q$, where each element represents a set of the next possible states.

Second, the alphabet of a DFA does not contain the empty string $(\varepsilon$ or $\lambda)$ symbol. That is not the case for NFA's, in which case the alphabet does include the empty string symbol.

| Regular Languages

Let $A$ and $B$ be languages. We define the REGULAR OPERATIONS as follows:

UNION: $A \cup B = \{x | x \isin A$ or $x \isin B\}$.

CONCATENATION: $A \circ B = \{ xy | x \isin A$ and $y \isin B\}$.

STAR: $A^* = \{x_1 x_2 ... x_k | k \ge 0$ and each $x_i \isin A\}$.

| Regular Expressions

| Non-Regular Expressions

| Regular Language Operations

002 | Computability Theory

Computability theory is the study of what can and cannot be computed by mathematical models of computation.

003 | Complexity Theory

Complexity theory is the study of how much time, memory, or other resources mathematical models of computation need to solve problems.