集合

set $A$

无穷集合：可数集（自然数集合一一对应），不可数集合

幂集$2^A$ 元素数为 0 1 2的子集构成的集合

笛卡尔积 $AB=A\times B=\{(a,b)\mid a\in A,b\in B\}$ 形成有序偶对

<aside>

集合的递归定义

</aside>

关系

$A\times B$ 的任意一个子集称$A$到$B$的一个二元关系，单个集合，$A\times A$

等价关系：自反的（$(a,a)$）对称的（$(a,b) (b,a)$） 传递的二元关系⇒ 集合A上的等价关系将集合分成多个互不相交的子集，成 等价类

语言

字母表⇒ 字符串（顺序，可重复）$\epsilon$代表空串，乘法定义为字符串连接，$\alpha^0=\epsilon$；集合的连接↔笛卡尔乘积，字符串连接替代有序偶对 $A\empty=\empty S=\empty,A\{\epsilon\}=\{\epsilon\}A=A$

克林闭包 $A^=\cup_0^\infty A^i$ 集合$A$上所有字符串（串的任意次连接）构成的集合。闭包的闭包结果不变$(A^)^=A^$；正闭包$A^+=\cup_1^\infty A^i$

$$ \empty^+=\empty,\{\epsilon\}^+=\{\epsilon\} \\ \empty^=\{\epsilon\},\{\epsilon\}^=\{\epsilon\} $$

<aside> 🥰

语言$L$是字母表$\Sigma$上的集合。$L\subset\Sigma^*$

语言由句子构成，最短的句子称基本句子。

集合的运算可以运用在语言上。

</aside>

$$ \{0,1\},\{0,1\}^*,\{0,1\} $$

$$ \{01,1\}^*\{10,1\} $$

没有连续零的所有零一串