有穷自动机 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.