《形式语言与自动机理论（第4版）》笔记（二）

文章目录

@[toc]
前导
《形式语言与自动机理论（第4版）》笔记（一）

第三章：有穷状态自动机
3.1|语言的识别
3.2|有穷状态自动机
即时描述
$se t ()$
例题
问题 $1$
解答
问题 $2$
解答

3.3|不确定的有穷状态自动机
构造 $NF A$ 的等价 $D F A$
$NF A$
构造方式
状态转移函数

$3.4$ |带空移动的有穷状态自动机
带空移动的不确定有穷状态自动机 $\varepsilon-NFA$
$\varepsilon-NFA$ 与 $NF A$ 等价
构造与 $M_{1}$ 等价的 $NFA \ M_{2}$
证明：对 $\forall x \in \Sigma^{+}$ ，有 $\delta_{2}(q_{0} , x) = \hat{\delta}_{1}(q_{0} , x)$
证明：对 $\forall x \in \Sigma^{+} , \delta_{2}(q_{0} , x) \cap F_{2} \neq \emptyset \Leftrightarrow \hat{\delta}_{1}(q_{0} , x) \cap F \neq \emptyset$
证明： $\varepsilon \in L(M_{1}) \Leftrightarrow \varepsilon \in L(M_{2})$

例题
问题
解答

$3.5$ | $F A$ 是正则语言的识别器
$F A$ 接受的语言是正则语言
构造正则文法 $G$ ，使得 $\set{\varepsilon}$
证明： $\set{\varepsilon}$
关于 $\varepsilon$ 句子

正则语言可以由 $F A$ 接受
构造等价的 $F A$
证明 $L (M) = L (G)$
关于 $\varepsilon \in L(G)$

$F A$ 与左线性文法
根据左线性文法构造等价的 $F A$
构造 $D F A$ 等价的左线性文法

3.6| $F A$ 的一些变形
双向有穷状态自动机
确定的双向有穷状态自动机 $2 D F A$
不确定的双向有穷状态自动机 $2 NF A$

带输出的 $F A$
$M oore$ 机
$M e a l y$ 机
$M oore$ 机与 $M e a l y$ 机等价

前导

《形式语言与自动机理论（第4版）》笔记（一）

第三章：有穷状态自动机

3.1|语言的识别

3.2|有穷状态自动机

即时描述

设 $\Sigma , \delta , q_{0} , F)$ 为一个 $F A$ ， $x$ ， $\in \Sigma^{*}$ ， $\delta(q_{0} , x) = q$ ， $x q y$ 称为 $M$ 的一个即时描述，表示 $x y$ 是 $M$ 正在处理的一个字符串， $x$ 引导 $M$ 从 $q_{0}$ 启动并到达状态 $q$ ， $M$ 的读头当前正指向 $y$ 的首字符
如果 $x q a y$ 是 $M$ 的一个即时描述，且 $\delta(q , a) = p$ ，则 $\vdash xapy$

$se t ()$

设 $\Sigma , \delta , q_{0} , F)$ 为一个 $F A$ ，对 $\forall q \in Q$ ，能引导 $F A$ 从开始状态到达 $q$ 的字符串的集合为 $\set{x \mid x \in \Sigma^{*} , \delta(q_{0} , x) = q}$

例题

问题 $1$

构造一个 $D F A$ ，它接受的语言为 $\set{x \mid x \in \set{0 , 1}^{*} , 且当把 x 看成二进制数时 , x 模 3 与 0 同余}$

解答

状态说明	状态	$0$	$1$
开始状态	$q_{s}$	$q_{0}$	$q_{1}$
终止状态（模 $3$ 余 $0$ ）	$q_{0}$	$q_{0}$	$q_{1}$
（模 $3$ 余 $1$ ）	$q_{1}$	$q_{2}$	$q_{0}$
（模 $3$ 余 $2$ ）	$q_{2}$	$q_{1}$	$q_{2}$

问题 $2$

构造一个 $D F A$ ，它接受的语言 $\set{x \mid x \in \set{0 , 1}^{*} , 且对 x 中任意一个长度不大于 5 的子串 a_{1} a_{2} \cdots a_{n} , a_{1} + a_{2} + \cdots + a_{n} \leq 3 (n \leq 5)}$

解答

$\set{q[\varepsilon]} \cup \set{q[a_{1} a_{2} \cdots a_{i}] \mid a_{1} , a_{2} , \cdots , a_{i} \in \set{0 , 1} 且 1 \leq i \leq 5 且 a_{1} + a_{2} + \cdots + a_{i} \leq 3}$
$\set{q_{t}} \cup F$

$\delta(q[\varepsilon] , a_{1}) = q[a_{1}] \\ \delta(q[a_{1}] , a_{2}) = q[a_{1} a_{2}] \\ \delta(q[a_{1} a_{2}] , a_{3}) = q[a_{1} a_{2} a_{3}] \\ \delta(q[a_{1} a_{2} a_{3}] , a) = \begin{cases} q[a_{1} a_{2} a_{3} a] , & a_{1} + a_{2} + a_{3} + a \leq 3 \\ q_{t} , & a_{1} + a_{2} + a_{3} + a > 3 \end{cases} \\ \delta(q[a_{1} a_{2} a_{3} a_{4}] , a) = \begin{cases} q[a_{1} a_{2} a_{3} a_{4} a] , & a_{1} + a_{2} + a_{3} + a_{4} + a \leq 3 \\ q_{t} , & a_{1} + a_{2} + a_{3} + a_{4} + a > 3 \end{cases} \\ \delta(q[a_{1} a_{2} a_{3} a_{4} a_{5}] , a) = \begin{cases} q[a_{2} a_{3} a_{4} a_{5} a] , & a_{2} + a_{3} + a_{4} + a_{5} + a \leq 3 \\ q_{t} , & a_{2} + a_{3} + a_{4} + a_{5} + a > 3 \end{cases} \\ \delta(q_{t} , a) = q_{t}$

3.3|不确定的有穷状态自动机

构造 $NF A$ 的等价 $D F A$

$NF A$

构造方式

先只把开始状态 $q_{0}]$ 填入表的状态列中
如果表中的状态列中有未处理的状态，则任选一个未处理的状态 $[q_{1} , q_{2} , \cdots , q_{n}]$ ，对 $\Sigma$ 中的每个字符 $a$ ，计算 $\delta([q_{1} , q_{2} , \cdots , q_{n}] , a)$ ，并将结果填入相应的表项中
如果 $\delta([q_{1} , q_{2} , \cdots , q_{n}] , a)$ 在表的状态列中未出现过，则同时将它填入表的状态列
如此重复下去，直到表的状态列中不存在未处理的状态

状态转移函数

状态说明	状态	$0$	$1$
开始状态	$q_{0}]$	$q_{0} , q_{1}]$	$q_{0} , q_{2}]$
	$q_{0} , q_{1}]$	$q_{0} , q_{1} , q_{3}]$	$q_{0} , q_{2}]$
	$q_{0} , q_{2}]$	$q_{0} , q_{1}]$	$q_{0} , q_{2} , q_{3}]$
终止状态	$q_{0} , q_{1} , q_{3}]$	$q_{0} , q_{1} , q_{3}]$	$q_{0} , q_{2} , q_{3}]$
终止状态	$q_{0} , q_{2} , q_{3}]$	$q_{0} , q_{1} , q_{3}]$	$q_{0} , q_{2} , q_{3}]$

$3.4$ |带空移动的有穷状态自动机

带空移动的不确定有穷状态自动机 $\varepsilon-NFA$

对任意 $\in Q$
- $\varepsilon-CLOSURE(q) = \set{p \mid 从 q 到 p 有一条标记为 \varepsilon 的路}$
- $\hat{\delta}(q , \varepsilon) = \varepsilon-CLOSURE(q)$

$\varepsilon-NFA$ 与 $NF A$ 等价

显然只需证明对于任给的 $\varepsilon-NFA$ ，存在与之等价的 $NF A$
设 $\varepsilon-NFA \ M_{1} = (Q , \Sigma , \delta_{1} , q_{0} , F)$

构造与 $M_{1}$ 等价的 $NFA \ M_{2}$

取 $\ M_{2} = (Q , \Sigma , \delta_{2} , q_{0} , F_{2})$
- $F_{2} = \begin{cases} F \cup \set{q_{0}} , & 如果 F \cap \varepsilon-CLOSURE(q_{0}) \neq \emptyset \\ F , & 如果 F \cap \varepsilon-CLOSURE(q_{0}) = \emptyset \end{cases}$
- 对 $\forall (q , a) \in Q \times \Sigma$ ，使 $\delta_{2}(q , a) = \hat{\delta}_{1}(q , a)$

证明：对 $\forall x \in \Sigma^{+}$ ，有 $\delta_{2}(q_{0} , x) = \hat{\delta}_{1}(q_{0} , x)$

施归纳于 $∣ x ∣$
当 $∣ x ∣ = 1$ 时，由 $\delta_{2}$ 的定义，结论成立
设当 $∣ x ∣ = n$ 时结论成立，下面证明当 $∣ x ∣ = n + 1$ 时结论也成立
- 设 $x = w a$ ， $∣ w ∣ = n$ ， $\in \Sigma$
- $\begin{aligned} \delta_{2}(q_{0} , x) &= \delta_{2}(q_{0} , wa) \\ &= \delta_{2}(\delta_{2}(q_{0} , w) , a) \\ &= \delta_{2}(\hat{\delta}_{1}(q_{0} , w) , a) \\ &= \displaystyle\bigcup\limits_{q \in \hat{\delta}_{1}(q_{0} , w)}{\delta_{2}(q , a)} \\ &= \displaystyle\bigcup\limits_{q \in \hat{\delta}_{1}(q_{0} , w)}{\hat{\delta}_{1}(q , a)} \\ &= \varepsilon-CLOSURE(\displaystyle\bigcup\limits_{q \in \hat{\delta}_{1}(q_{0} , w)}{\delta_{1}(q , a)}) \\ &= \varepsilon-CLOSURE(\set{p \mid \exist q \in \hat{\delta}_{1}(q_{0} , w) , 使得 p \in \delta_{1}(q , a)}) \\ &= \hat{\delta}_{1}(q_{0} , wa) \\ &= \hat{\delta}_{1}(q_{0} , x) \end{aligned}$
- 结论对 $∣ x ∣ = n + 1$ 也成立，由归纳法原理，结论对 $\forall x \in \Sigma^{+}$ 成立

证明：对 $\forall x \in \Sigma^{+} , \delta_{2}(q_{0} , x) \cap F_{2} \neq \emptyset \Leftrightarrow \hat{\delta}_{1}(q_{0} , x) \cap F \neq \emptyset$

充分性
- 设 $\hat{\delta}_{1}(q_{0} , x) \cap F \neq \emptyset$ ， $\delta_{2}(q_{0} , x) \cap F \neq \emptyset$ ，而 $\subseteq F_{2}$ ，所以 $\delta_{2}(q_{0} , x) \cap F_{2} \neq \emptyset$
必要性
- 设 $\delta_{2}(q_{0} , x) \cap F_{2} \neq \emptyset$ ，则有以下两种情况
  - 第一种情况： $\delta_{2}(q_{0} , x) \cap F_{2} \neq \set{q_{0}}$ ，此时， $\delta_{2}(q_{0} , x) \cap F \neq \emptyset$ ，而 $\hat{\delta}_{1}(q_{0} , x) = \delta_{2}(q_{0} , x)$ ，所以 $\hat{\delta}_{1}(q_{0} , x) \cap F \neq \emptyset$
  - 第二种情况： $\delta_{2}(q_{0} , x) \cap F_{2} = \set{q_{0}}$ ，如果 $q_{0} \in F$ ，则 $\hat{\delta}_{1}(q_{0} , x) \cap F \neq \emptyset$ ，事实上，此时不可能有 $q_{0} \notin F$ ，如果 $q_{0} \notin F$ ，则由于 $q_{0} \in F_{2}$ ，所以 $\cap \varepsilon-CLOSURE(q_{0}) \neq \emptyset$ ，即 $\exist q_{f} \in \varepsilon-CLOSURE(q_{0}) \cap F$ ，但 $q_{f} \neq q_{0}$ ，由于 $\hat{\delta}_{1}(q_{0} , x) = \delta_{2}(q_{0} , x)$ ，所以，由 $q_{0} \in \hat{\delta}_{1}(q_{0} , x)$ 可得 $\varepsilon-CLOSURE(q_{0}) \subseteq \hat{\delta}_{1}(q_{0} , x)$ ， $q_{f} \in \hat{\delta}_{1}(q_{0} , x) \cap F$ ，而 $\subseteq F_{2}$ ，所以 $q_{f} \in F_{2}$ ，从而 $q_{f} \in \delta_{2}(q_{0} , x) \cap F_{2}$ ，由于 $q_{f} \neq q_{0}$ ，这与 $\delta_{2}(q_{0} , x) \cap F_{2} = \set{q_{0}}$ 矛盾
- 综上所述，如果 $\delta_{2}(q_{0} , x) \cap F_{2} \neq \emptyset$ ，则必有 $\hat{\delta}_{1}(q_{0} , x) \cap F \neq \emptyset$

证明： $\varepsilon \in L(M_{1}) \Leftrightarrow \varepsilon \in L(M_{2})$

必要性
- 设 $\varepsilon \in L(M_{1})$ ，则 $\exist q_{f} \in \varepsilon-CLOSURE(q_{0}) \cap F$ ，由 $F_{2}$ 的定义， $q_{0} \in F_{2}$ ，所以 $\delta_{2}(q_{0} , \varepsilon) = q_{0} \in F_{2}$ ，表明 $\varepsilon \in L(M_{2})$
充分性
- 设 $\varepsilon \in L(M_{2})$ ，从而有 $\delta_{2}(q_{0} , \varepsilon) = q_{0} \in F_{2}$ ，只能有以下两种情况
  - 第一种情况： $q_{0} \in F$ ，此时 $\varepsilon \in L(M_{1})$
  - 第二种情况： $q_{0} \notin F$ ，此时必有 $\varepsilon-CLOSURE(q_{0}) \cap F \neq \emptyset$ ，即 $\hat{\delta}_{1}(q_{0} , \varepsilon) \cap F \neq \emptyset$ ，所以 $\varepsilon \in L(M_{1})$
故 $\varepsilon \in L(M_{1}) \Leftrightarrow \varepsilon \in L(M_{2})$

例题

问题

构造与图示 $\varepsilon-NFA$ 等价的 $NF A$

解答

$3.5$ | $F A$ 是正则语言的识别器

$F A$ 接受的语言是正则语言

设 $\ M = (Q , \Sigma , \delta , q_{0} , F)$

构造正则文法 $G$ ，使得 $\set{\varepsilon}$

取 $\Sigma , P , q_{0})$ ，其中 $\set{q \rightarrow ap \mid \delta(q , a) = p} \cup \set{q \rightarrow a \mid \delta(q , a) = p \in F}$

证明： $\set{\varepsilon}$

对于 $a_{1} a_{2} \cdots a_{n} \in \Sigma^{+}$ ， $\begin{aligned} q_{0} \xRightarrow{+} a_{1} a_{2} \cdots a_{n} &\Leftrightarrow q_{0} \rightarrow a_{1} q_{1} , q_{1} \rightarrow a_{2} q_{2} , \cdots , q_{n - 1} \rightarrow a_{n} \in P \\ &\Leftrightarrow \delta(q_{0} , a_{1}) = q_{1} , \delta(q_{1} , a_{2}) = q_{2} , \cdots , \delta(q_{n - 1} , a_{n}) = q_{n} \in F \\ &\Leftrightarrow \delta(q_{0} , a_{1} a_{2} \cdots a_{n}) = q_{n} \in F \end{aligned}$
所以 $a_{1} a_{2} \cdots a_{n} \in L(G) \Leftrightarrow a_{1} a_{2} \cdots a_{n} \in L(M)$

关于 $\varepsilon$ 句子

如果 $q_{0} \notin F$ ，则 $\varepsilon \notin L(M)$ ， $\varepsilon$
如果 $q_{0} \in F$ ，存在正则文法 $G^{'}$ ，使得 $L(G^{'}) = L(G) \cup \set{\varepsilon} = L(M)$

正则语言可以由 $F A$ 接受

由于正则语言被定义为是由正则文法产生的语言，所以只需证明，对于任给的正则文法，存在一个与之等价的 $F A$
设有正则文法 $G = (V, T, P, S)$ ，假设 $G$ 是右线性文法，且 $\varepsilon \notin L(G)$

构造等价的 $F A$

对应于正则文法 $G = (V, T, P, S)$ ，取 $\ M = (V \cup \set{Z} , T , \delta , S , \set{Z})$ ，其中对 $\forall (A , a) \in V \times T$ ， $\delta(A , a) = \begin{cases} \set{B \mid A \rightarrow aB \in P} \cup \set{Z} , & 如果 A \rightarrow a \in P \\ \set{B \mid A \rightarrow aB \in P} , & 如果 A \rightarrow a \notin P \end{cases}$

证明 $L (M) = L (G)$

对于 $a_{1} a_{2} \cdots a_{n} \in T^{+}$ ， $\begin{aligned} a_{1} a_{2} \cdots a_{n} \in T^{+} &\Leftrightarrow S \xRightarrow{+} a_{1} a_{2} \cdots a_{n} \\ &\Leftrightarrow S \Rightarrow a_{1} A_{1} \Rightarrow a_{1} a_{2} A_{2} \Rightarrow \cdots \Rightarrow a_{1} a_{2} \cdots a_{n} \\ &\Leftrightarrow S \rightarrow a_{1} A_{1} , A_{1} \rightarrow a_{2} A_{2} , \cdots , A_{n - 1} \rightarrow a_{n} \in P \\ &\Leftrightarrow A_{1} \in \delta(S , a_{1}) , A_{2} \in \delta(A_{1} , a_{2}) , \cdots , Z \in \delta(A_{n - 1} , a_{n}) \\ &\Leftrightarrow Z \in \delta(S , a_{1} a_{2} \cdots a_{n}) \Leftrightarrow a_{1} a_{2} \cdots a_{n} \in L(M) \end{aligned}$
即对于 $\forall x \in T^{+}$ ， $\in L(G) \Leftrightarrow x \in L(M)$

关于 $\varepsilon \in L(G)$

不妨假设 $S$ 不出现在 $G$ 的任何产生式的右部，设 $G$ 中只有唯一的一个空产生式 $\rightarrow \varepsilon$
只需将状态 $S$ 取为 $M$ 的第二个终止状态
按此方法构造出的 $\ M$ 与所给的正则文法 $G$ 是等价的

$F A$ 与左线性文法

根据左线性文法构造等价的 $F A$

引入一个开始状态 $Z$ ，形如 $\rightarrow a$ 的产生式， $\in \delta(Z , a)$
形如 $\rightarrow Ba$ 的产生式， $\delta(B , a) = A$
$G$ 的开始符号对应的状态是相应 $F A$ 的终止状态

构造 $D F A$ 等价的左线性文法

对 $D F A$ 做处理
- 删除 $D F A$ 的陷阱状态（包括与之相关的弧）
- 在图中加一个识别状态 $z$ ，“复制”一条原来到达终止状态的弧，使它从原来的起点出发，到达新添加的识别状态
- 如果开始状态也是终止状态，则增加产生式 $\rightarrow \varepsilon$
构造规则
- 如果 $\delta(A , a) = B$ ，则有产生式 $\rightarrow Aa$
- 如果 $\delta(A , a) = B$ ，且 $A$ 是开始状态，则有产生式 $\rightarrow a$

3.6| $F A$ 的一些变形

双向有穷状态自动机

确定的双向有穷状态自动机 $2 D F A$

$\Sigma , \delta , q_{0} , F)$
$\delta : Q \times \Sigma \rightarrow Q \times \set{L , R , S}$ ，对 $\forall (q , a) \in Q \times \Sigma$
- 如果 $\delta(q , a) = (p , L)$ ，表示 $M$ 在状态 $q$ 读入字符 $a$ ，将状态变成 $p$ ，并将读头向左移动一个带方格而指向输入字符串中的前一个字符
- 如果 $\delta(q , a) = (p , R)$ ，表示 $M$ 在状态 $q$ 读入字符 $a$ ，将状态变成 $p$ ，并将读头向右移动一个带方格而指向输入字符串中的下一个字符
- 如果 $\delta(q , a) = (p , S)$ ，表示 $M$ 在状态 $q$ 读入字符 $a$ ，将状态变成 $p$ ，读头保持在原位不动

不确定的双向有穷状态自动机 $2 NF A$

$\Sigma , \delta , q_{0} , F)$
$\delta : Q \times \Sigma \rightarrow 2^{Q \times \set{L , R , S}}$ ，对 $\forall (q , a) \in Q \times \Sigma$ ， $\delta(q , a) = \set{(p_{1} , D_{1}) , (p_{2} , D_{2}) , \cdots , (p_{m} , D_{m})}$ 表示 $M$ 在状态 $q$ 读入字符 $a$ ，可以选择地将状态变成 $p_{m}$ ，同时按 $D_{m} \in \set{L , R , S}$ 实现对读头的移动

带输出的 $F A$

$M oore$ 机

$\Sigma , \Delta , \delta , \lambda , q_{0})$
- $\Delta$ ——输出字母表
- $\lambda$ —— $\lambda : Q \rightarrow \Delta$ 为输出函数，对 $\forall q \in Q$ ， $\lambda(q) = a$ 表示 $M$ 在状态 $q$ 时输出 $a$
对于 $\forall a_{1} a_{2} \cdots a_{n} \in \Sigma^{*}$ ， $M$ 的输出串为 $\lambda(q_{0}) \lambda(\delta(q_{0} , a_{1})) \lambda(\delta(\delta(q_{0} , a_{1}) , a_{2})) \cdots \lambda(\delta((\cdots \delta(\delta(q_{0} , a_{1}) , a_{2}) \cdots) , a_{n}))$ ，设 $\delta(q_{0} , a_{1}) = q_{1}$ ， $\delta(q_{1} , a_{2}) = q_{2}$ ， $\cdots$ ， $\delta(q_{n - 1} , a_{n}) = q_{n}$ ，则 $M$ 的输出可以表示成 $\lambda(q_{0}) \lambda(q_{1}) \cdots \lambda(q_{n})$ ，这是一个长度为 $n + 1$ 的串

$M e a l y$ 机

$\Sigma , \Delta , \delta , \lambda , q_{0})$
- $\lambda$ —— $\lambda : Q \times \Sigma \rightarrow \Delta$ 为输出函数，对 $\forall (q , a) \in Q \times \Sigma$ ， $\lambda(q , a) = d$ 表示 $M$ 在状态 $q$ 读入字符 $a$ 时输出 $d$
对于 $\forall a_{1} a_{2} \cdots a_{n} \in \Sigma^{*}$ ， $M$ 的输出串为 $\lambda(q_{0} , a_{1}) \lambda(\delta(q_{0} , a_{1}) , a_{2}) \cdots \lambda(\delta(\cdots \delta(\delta(q_{0} , a_{1}) , a_{2}) \cdots) , a_{n})$ ，设 $\delta(q_{0} , a_{1}) = q_{1}$ ， $\delta(q_{1} , a_{2}) = q_{2}$ ， $\cdots$ ， $\delta(q_{n - 1} , a_{n}) = q_{n}$ ，则 $M$ 的输出可以表示成 $\lambda(q_{0} , a_{1}) \lambda(q_{1} , a_{2}) \cdots \lambda(q_{n - 1} , a_{n})$ ，这是一个长度为 $n$ 的串

$M oore$ 机与 $M e a l y$ 机等价

设 $M oore$ 机 $M_{1} = (Q_{1} , \Sigma , \Delta , \delta_{1} , \lambda_{1} , q_{01})$ ， $M e a l y$ 机 $M_{2} = (Q_{2} , \Sigma , \Delta , \delta_{2} , \lambda_{2} , q_{02})$
对于 $\forall x \in \Sigma^{*}$ ，当 $T_{1}(x) = \lambda_{1}(q_{0}) T_{2}(x)$ 成立时，称它们是等价的，其中 $T_{1}(x)$ 和 $T_{2}(x)$ 分别表示 $M_{1}$ 和 $M_{2}$ 关于 $x$ 的输出