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

Myhill-Nerode Theorem 迈希尔尼罗德定理:L 是正则语言,当且仅当 RL 有有限的等价类。

是一个证明语言是正则语言的必要充分条件。

正则语言的封闭性

  • RL 对于并、乘积、闭包运算封闭
  • RL 对于补、交运算封闭

自动机的转换

通常的转换顺序: RE -> $\varepsilon$-NFA -> NFA -> DFA

NFA -> DFA 及等价性

如果能用 NFA 来表示的语言,同样可以使用 DFA 来表示:

image-20200902163650146

接下来移除不可到达的状态集合得到:

image-20200902163714895

FA -> RE 的转换

  • 使用状态消去 State Elimination:
  • image-20200902183523252
  • 状态消去的方法:
  • image-20200902183712933

RE -> FA

image-20200902183953737
  • Eg.image-20200902184009512