有穷自动机 Finite Automation
动机：语言的识别：
- 为了证明 $w \subset L$，需推导 G，或规约 w，缺乏目的性和方向性
- 设计一套系统，提高识别效率，简介抽象、直观描述
定义
五元组：$M = (Q, \Sigma, \delta, q_0, F)$
Q 非空集合；$\Sigma$ 输入字母表， $\delta$ 状态转移函数， $q_0$ 开始状态，$F$ 终止 / 接收状态
$\delta (q,a) = p$ 表示在 q 状态下读入 a 转移到 p。
FA 的表达方式：函数或转换表（更直观）
字符串集合：$set (q) = {x | x \in \Sigma^*, \delta (q_0, x) = q}$
Instant Description 瞬时描述
表示自动机识别一个输入串的过程。形式：$xqy$，x 为已处理的字符，y 为未处理的字符
有：$xqay \vdash_M xapy$，，其中 $\vdash_m$ 与文法中的转换 $\Rightarrow$ 有类似的表达方式（+: 至少一次，*: 若干次，n: n 次 等）
- 如 $\alpha \vdash_M^n \beta$ 表示 M 经过 n 次移动。从状态 $\alpha$ 转换成了状态 $\beta$。
确定有穷状态自动机 Deterministic Finite Automaton, DFA
对于任意 $q \in Q, a \in Sigma, \delta (q,a) 均有确定值 $
关于 $\hat {\delta}$ 与 $\delta$：前者为后者的扩充，有 $\hat {\delta}: Q \times \Sigma^* \rightarrow Q$，用于识别语言
注意到后者定义域 $Q\times \Sigma$ 为前者定义域 $Q \times \Sigma ^*$ 的真子集，所以二者如果有相同的值，不用区别符号，故常用 $\delta$ 代替 $\hat {\delta}$。
非确定有穷状态自动机 Nondeterministic Finite Automaton, NFA
定义类似 DFA 的五元组：$M = (Q, \Sigma, \delta, q_0, F)$
其中 $\delta$ 允许选择多个状态。即 $\forall (q,a) \in Q \times \Sigma, \delta (q,a) = {p_1, p_2, \dots, p_m}$
FA 的 ID 与描述方式对 DFA 同样有效
空迁移
定义五元组：$M = (Q, \Sigma, \delta, q_0, F)$
在 NFA 的基础上，进一步允许 $delta$ 满足：$\forall (q,a) \in Q \times \Sigma, \delta (q,a) = {p_0, p_1, \dots,p_m}, \delta (q,\varepsilon) = {p_0, p_1, \dots,p_m}$。
即允许 M 在状态 q 下不输入任何字符而选择改变状态，做空移动，称为 $\varepsilon-NFA$。
空迁移 NFA 同样和 NFA 具有等价性。
注意在 $\varepsilon$-NFA 中，$\delta$ 与 $\hat {\delta}$ 不等价，需要根据上下文区分。
正则语言 / 表达式
正则表达式 Regular Expression - 使用适当的约定用更简洁的方式来表达文法 FA 所表达的语言
FA 是正则语言的识别器（有限自动机和正则表达式等价）
定义：$\emptyset 和 \varepsilon$ 是正则表达式，表示语言 $\emptyset 和 \varepsilon$
若 $\forall a \in \Sigma$ 是正则表达式，表示语言 {a}；
若 r 和 s 是 RE，则 $r + s, r\cdot s$ 是正则表达式，$ r^* $ 是正则表达式。
- 正则语言 L (RE)：有 $L (r_1 + r_2) = L (r_2) \cup L (r_2)$
⭐️ 正则语言的证明：泵引理 Pumping Lemma
- 泵引理：L 为一个正则语言，则存在一个常数 N，使得 $\forall z \in L, $ 若 $|z| \ge N$，能把 z 分为三个部分 xyz 满足有：$y \ne \varepsilon, |xy| \le N, \forall k \ge 0, xy^kz \in L$。
利用反证法可以证明 L 不为正则语言。(找到恰当的拆分，并得到一个反例即可)
泵引理只是一个 RG 的必要条件，不可用于证明一个而语言是 RG。
Eg.
Myhill-Nerode Theorem 迈希尔尼罗德定理：L 是正则语言，当且仅当 RL 有有限的等价类。
是一个证明语言是正则语言的必要充分条件。
正则语言的封闭性
- RL 对于并、乘积、闭包运算封闭
- RL 对于补、交运算封闭
自动机的转换
通常的转换顺序： RE -> $\varepsilon$-NFA -> NFA -> DFA
NFA -> DFA 及等价性
如果能用 NFA 来表示的语言，同样可以使用 DFA 来表示：
接下来移除不可到达的状态集合得到：
FA -> RE 的转换
- 使用状态消去 State Elimination:
- 状态消去的方法：
RE -> FA
- Eg.
