参考书目：Peter Linz, An Introduction to Formal Languages and Automata (6th Editon) 2016

• Introduce to The Theory of Computation
  • Set
    • Powerset | 幂集
    • Cartesian Product | 笛卡尔积
    • Partition | 分隔
  • Relation
    • Equivalence Relation

Introduce to The Theory of Computation

Set

Powerset | 幂集

Example 1.1
If $S$ is the set $\{a, b, c \}$, then its powerset is

$2^S=\{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$

Here $|S|=3$ and $|2^S|=8$. This is an instance of a general result; if $S$ is finite, then

$|2^S|=2^{|S|}$

Cartesian Product | 笛卡尔积

For the Cartesian product of two sets, which itself is a set of ordered pairs, we write

$S=S_1 \times S_2 = \{(x,y):x \in S_1, y\in S_2\}$

Partition | 分隔

A set can be divided by separating it into a number of subsets. Suppose that $S_1, S_2, \dotsc , S_n$ are subsets of a given set $S$ and that the following holds:

1. The subsets $S_1, S_2, \dotsc , S_n$ are mutually disjoint;
2. $S_1 \cup S_2 \cup \dotsc \cup S_n = S$;
3. none of the $S_i$ is empty.

Then $S_1, S_2, \dotsc , S_n$ is called a partition of $S$.

Relation

Equivalence Relation

A relation denoted by $R$ is considered an equivalence if it satisfies three rules

1. the reflexivity rule｜反身性
   $xRx$ for all $x$;
2. the symmetry rule ｜对称性
   if $xRy$, then $yRx$;
3. the transitivity rule｜传递性
   if $xRy$ and $yRz$, then $xRz$