自动机设计工具:

[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$。

我们需要这样的命题序列:

  1. 已知:$x = a^2 + b^2 +c^2+d^2$
  2. 已知:$a, b, c,d \geq 1$
  3. 根据 2 和算数法则:$a^2, b^2,c^2,d^2\geq 1$
  4. 根据 3 和算数法则:$x \geq 1+1+1+1 = 4$
  5. 根据 命题 $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^*$。