«自动机理论、语言和计算导论»笔记：第一章 方法与癫狂
自动机设计工具：
[Graph / Finite State Machine Designer (markusfeng.com)](https://www.cs.unc.edu/~otternes/comp455/fsm_designer/)
模拟器：
FSM Simulator (ivanzuzak.info)
1.1 为何学习自动机理论
1.2 形式证明介绍
1.2.1 演绎证明
介绍演绎推理的规则。
例如，证明：如果 $x$ 是四个正整数各自平方后求和，那么 $2^x > x^2$。
我们需要这样的命题序列：
-
已知：
$x = a^2 + b^2 +c^2+d^2$ -
已知：
$a, b, c,d \geq 1$ -
根据 2 和算数法则：
$a^2, b^2,c^2,d^2\geq 1$ -
根据 3 和算数法则：
$x \geq 1+1+1+1 = 4$ -
根据 命题
$x \geq 4 \to 2^x \geq x^2$和 4：$2^x > x^2$成立
1.2.2 还原定义
介绍一种证明的技巧，就是把描述还原为其定义
例如，证明：若 $S$ 是无穷集合 $U$ 的有穷子集，$T$ 是 $S$ 关于 $U$ 的补集，则 $T$ 是无穷的。
转换：
| 原 | 新 |
|---|---|
| S 有穷 | $\exists n, s.t.\ |
| U 无穷 | $\not \exists p, s.t.\ |
| T 是 S 的补集 | $S\cup T = U \wedge S \cap T = \varnothing$ |
证明：
假定 $T$ 是有穷的，即 $\exists q, s.t.\ ||T|| = q$
而 $||T|| = q = ||S|| + ||U|| = n + ||U||$，即 $||U|| = q - n$，即 $U$ 有穷，矛盾。
因此 $T$ 是无穷的。
1.3 证明的其它形式
由于离散数学学得差不多了，这里掠过。
1.4 归纳证明
1.5 自动机的中心概念
1.5.1 字母表
字母表（Alphabet）：符号的有限、非空的集合。记作 $\Sigma$，或者 $T$。
1.5.2 字符串
字符串（String）：一个有限符号序列。符号选自某个字母表。
空串：不包含序列元素的符号序列。记作 $\epsilon$。
串长：字符串的序列元素数量。
字母表的幂：$T^k$ 表示长度为 $k$ 的所有串的构成的集合。这些串的元素来自字母表 $T$。
下面的
$T$都默认代表某字母表。
约定 $T^*$ 表示 $\cup_{i=0}^\infty T^i$。
约定 $T^+$ 表示 $\cup_{i=1}^\infty T^i$。
语言：语言是串的集合。每个串都来自 $T^*$。