Theory of Computation

| Jump Ahead

• 001 | Automata Theory
• 002 | Computability Theory
• 003 | Complexity Theory
• 004 | Sets
• 005 | Sequences and Tuples
• 006 | Functions
• 007 | Relations
• 008 | Graphs
• 009 | Strings
• 010 | Proofs
• 011 | Languages
• 012 | Grammars
• 013 | Finite Automata

001 | Automata Theory

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

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.

004 | Sets

A SET is an unordered collection of objects called elements or members of the set.

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.

---

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

---

A SET OPERATION is a rule used to combine, compare, or modify sets in order to form a new set.

These are the most common 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)$)

---

The UNION ($\cup$) of sets is ...

For example,

---

The INTERSECTION ($\cap$) of sets is ...

For example,

---

The DIFFERENCE ($-$ or $\setminus$) of sets is ...

For example,

---

The COMPLEMENT (of a set $A$; $\overline{A}$) of sets is ...

For example,

---

The CARTESIAN/CROSS PRODUCT ($\times$) of sets is ...

For example,

---

The POWER SET ($\mathcal{P}(I)$) of a set $I$ is the set of all subsets of $I$.

For example,

$I = \{0, 1\}$

$\mathcal{P}(I) = \{ \{\}, \{0\}, \{1\}, \{0, 1\}\}$

005 | Sequences and Tuples

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

For example,

...

006 | Functions

...

007 | Relations

...

008 | Graphs

...

009 | Strings

...

010 | Proofs

...

011 | Languages

...

012 | Grammars

...

013 | Finite Automata

...