---

前言：

• 感觉习题册里的题都没有涉及几个概念之间的转换；
• 遂拿出教材里的例题。

---

0 概念汇总

定义的汇总

对象	定义
文法	$G=(\Sigma ,V,S,P)$
有限自动机	$FA=(Q,\Sigma ,\delta ,q_0,F)$
下推自动机	$PDA=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$
图灵机	$TM=(Q,\Sigma ,q_0,q_{\alpha },\delta )$

规则的汇总

对象	规则的定义
有限自动机	$\delta (q,x)=q^{\prime }$
下推自动机	$<q,x,A,q^{\prime },A_1{A}_2\cdots A_i>$
图灵机	< q , x , q ′ , x ′ , { L , R , N } > <q,x,q',x',\{L,R,N\}> <q,x,q′,x′,{L,R,N}> 或者 δ ( q , x ) = ( q ′ , x ′ , { L , R , N } ) \delta(q,x)=(q',x',\{L,R,N\}) δ(q,x)=(q′,x′,{L,R,N})

格局的汇总

格局的定义：

对象	格局的定义
有限自动机	$qw$，其中 $w$ 是剩余未被扫描的串
下推自动机	$(q,w,\sigma )$，其中 $w$ 是剩余未被扫描的串，$\sigma$ 是当前栈内的符号
图灵机	$w_{1}q{w}_2$，其中 $w_1$ 是读写头左边的串，$w_2$ 是读写头右边的串

格局的转换：

对象	格局的转换
有限自动机	$\delta (q,x)=q^{\prime }$ 将导致：$qxw\Rightarrow q^{\prime }w$
下推自动机	$<q,x,A,q^{\prime },A_1{A}_2\cdots A_i>$ 将导致：$(q,xw,A\sigma )\Rightarrow (q^{\prime },w,A_1{A}_2\cdots A_i\sigma )$
图灵机	$<q,x,q^{\prime },x^{\prime },L>$ 将导致：$s_{1}yqx{s}_2\Rightarrow s_1{q}^{\prime }y{x}^{\prime }{s}_2$

1 文法与有限自动机之间的转换

DFA 转换为 RLG

例： 已知形式语言 L = { { 0 , 1 } 1 ∗ 0 } ∗ L=\{\{0,1\}1^*0\}^* L={{0,1}1∗0}∗，请构造右线性文法接收该语言。

思路：

• Step1：构造 DFA 接收 FSL，由此得到 $\delta$ 转换函数。
• Step2：把 $\delta$ 转换函数转换为文法 $G$ 的产生式。

解答：

• 分析：该语言对应的正则表达式为 $((0+1)1^{\ast }0{)}^{\ast }$ 。
• 由此构造 DFA 接收该语言：

• 从而得到 $\delta$ 转换函数，将其转换为文法 $G$ 的产生式：

DFA 的状态转换函数	RLG 的产生式
$\delta (q_0,0)=q_1$	$q_0\to 0q_1$
$\delta (q_0,1)=q_1$	$q_0\to 1q_1$
$\delta (q_1,1)=q_1$	$q_1\to 1q_1$
$\delta (q_1,0)=q_0\in F$	$q_1\to 0q_0\mid 0$
$\delta (q_0,\epsilon )=q_0\in F$	$q_0\to \epsilon$

特别注意：状态函数 $\delta (q,x)=q^{\prime },q^{\prime }\in F$ 对应的产生式是 $q\to x{q}^{\prime }$ 和 $q\to x$ 。

• 整理得到文法 $G$ 的产生式如下：
  • $q_0\to 0q_1\mid 1q_1\mid \epsilon$
  • $q_1\to 1q_1\mid 0q_0\mid 0$

RLG 转换为 NFA

例： 已知形式语言 L = { a b , a a } L=\{ab,aa\} L={ab,aa}，请构造 NFA 接收该语言。

思路：

• Step1：构造 RLG 接收该语言，由此得到文法 $G$ 的产生式。
• Step2：把文法 $G$ 的产生式转换为 NFA 的 $\delta$ 转换函数。
• Step3：根据 NFA 的 $\delta$ 转换函数绘制状态图。

解答：

• 构造 RLG 如下：
  • $S\to aA$
  • $A\to a\mid b$
• 将上述产生式转换为 NFA 的 $\delta$ 转换函数：

RLG 的产生式	NFA 的状态转换函数
$S\to aA$	$\delta (S,a)=A$
$A\to a$	$\delta (A,a)=q\in F$
$A\to b$	$\delta (A,b)=q\in F$

• 根据 NFA 的 $\delta$ 转换函数绘制状态图：

2 有限自动机之间的转换

NFA 转换为 DFA

例 1： 构造 DFA 接收 { 0 , 1 } \{0,1\} {0,1} 上的语言，该语言中每个字符串在被当成二进制数时，能够被 2 整除。

思路：

• Step1：构造 NFA 接收该语言。
• Step2：将 NFA 转换为 DFA 。

解答：

• 分析：该语言对应的正则表达式为 $(0+1{)}^{\ast }0$ 。
• 由此构造 NFA 接收该语言：

• 通过表格法，将 NFA 转换为 DFA：

状态集合 P	0	1
{ q 0 } \{q_0\} {q0​}	{ q 0 , q 1 } \{q_0,q_1\} {q0​,q1​}	{ q 0 } \{q_0\} {q0​}
{ q 0 , q 1 } , q 1 ∈ F \{q_0,q_1\}, q_1 \in F {q0​,q1​},q1​∈F	{ q 0 , q 1 } \{q_0,q_1\} {q0​,q1​}	{ q 0 } \{q_0\} {q0​}

注意：DFA 的开始状态 $q_0^{\prime }$ 等于 NFA 的开始状态集合 $Q_0$ 。

• 根据表格绘制 DFA 的状态图：

例 2： 构造 DFA 接收语言
L = { w ∣ w ∈ { a , b , c } + , ∣ w ∣ > 1 , w  中最后的字母与第一个字母相同 } L=\{w\mid w\in \{a,b,c\}^+,|w|>1,w\ 中最后的字母与第一个字母相同\} L={w∣w∈{a,b,c}+,∣w∣>1,w 中最后的字母与第一个字母相同}

思路：

• Step1：构造 NFA 接收该语言。
• Step2：将 NFA 转换为 DFA 。

解答：

• 分析：该语言对应的正则表达式为 $a{R}^{\ast }a+b{R}^{\ast }b+c{R}^{\ast }c$，其中 $R=(a+b+c)$ 。
• 由此构造 NFA 接收该语言：

• 通过表格法，将 NFA 转换为 DFA：

状态集合 P	a	b	c
{ q 0 } \{q_0\} {q0​}	{ q 1 } \{q_1\} {q1​}	{ q 2 } \{q_2\} {q2​}	{ q 3 } \{q_3\} {q3​}
{ q 1 } \{q_1\} {q1​}	{ q 1 , q 4 } \{q_1,q_4\} {q1​,q4​}	{ q 1 } \{q_1\} {q1​}	{ q 1 } \{q_1\} {q1​}
{ q 2 } \{q_2\} {q2​}	{ q 2 } \{q_2\} {q2​}	{ q 2 , q 4 } \{q_2,q_4\} {q2​,q4​}	{ q 2 } \{q_2\} {q2​}
{ q 3 } \{q_3\} {q3​}	{ q 3 } \{q_3\} {q3​}	{ q 3 } \{q_3\} {q3​}	{ q 3 , q 4 } \{q_3,q_4\} {q3​,q4​}
{ q 1 , q 4 } \{q_1,q_4\} {q1​,q4​}	{ q 1 , q 4 } \{q_1,q_4\} {q1​,q4​}	{ q 1 } \{q_1\} {q1​}	{ q 1 } \{q_1\} {q1​}
{ q 2 , q 4 } \{q_2,q_4\} {q2​,q4​}	{ q 2 } \{q_2\} {q2​}	{ q 2 , q 4 } \{q_2,q_4\} {q2​,q4​}	{ q 2 } \{q_2\} {q2​}
{ q 3 , q 4 } \{q_3,q_4\} {q3​,q4​}	{ q 3 } \{q_3\} {q3​}	{ q 3 } \{q_3\} {q3​}	{ q 3 , q 4 } \{q_3,q_4\} {q3​,q4​}

• 根据表格绘制 DFA 的状态图：

ε-NFA 转换为 NFA

转换方法如下：

• 计算 NFA 的状态转换函数 ${\delta }^{\prime }$： δ ′ ( q , x ) = δ ∗ ( { q } , x ) \delta'(q,x)=\delta^*(\{q\},x) δ′(q,x)=δ∗({q},x)
• 确定 NFA 的接收状态 $F^{\prime }$：
  • 若 $F\cap \epsilon \text{-CLOSURE}(q_0)\ne \varphi$，则 F ′ = F ∩ { q 0 } F'=F \cap \{q_0\} F′=F∩{q0​}。
  • 若 $F\cap \epsilon \text{-CLOSURE}(q_0)=\varphi$，则 $F^{\prime }=F$。

例： 请将下述 ε-NFA 转换为 NFA 。

解答：

• 计算状态转换函数：
  • δ ′ ( q 0 , 0 ) = δ ∗ ( { q 0 } , 0 ) = { q 0 , q 1 , q 2 } \delta'(q_0,0)=\delta^*(\{q_0\},0)=\{q_0,q_1,q_2\} δ′(q0​,0)=δ∗({q0​},0)={q0​,q1​,q2​}
  • δ ′ ( q 0 , 1 ) = δ ∗ ( { q 0 } , 1 ) = { q 1 , q 2 } \delta'(q_0,1)=\delta^*(\{q_0\},1)=\{q_1,q_2\} δ′(q0​,1)=δ∗({q0​},1)={q1​,q2​}
  • δ ′ ( q 0 , 2 ) = δ ∗ ( { q 0 } , 2 ) = { q 2 } \delta'(q_0,2)=\delta^*(\{q_0\},2)=\{q_2\} δ′(q0​,2)=δ∗({q0​},2)={q2​}
  • δ ′ ( q 1 , 0 ) = δ ∗ ( { q 1 } , 0 ) = 无定义 \delta'(q_1,0)=\delta^*(\{q_1\},0)=无定义 δ′(q1​,0)=δ∗({q1​},0)=无定义
  • δ ′ ( q 1 , 1 ) = δ ∗ ( { q 1 } , 1 ) = { q 1 , q 2 } \delta'(q_1,1)=\delta^*(\{q_1\},1)=\{q_1,q_2\} δ′(q1​,1)=δ∗({q1​},1)={q1​,q2​}
  • δ ′ ( q 1 , 2 ) = δ ∗ ( { q 1 } , 2 ) = { q 2 } \delta'(q_1,2)=\delta^*(\{q_1\},2)=\{q_2\} δ′(q1​,2)=δ∗({q1​},2)={q2​}
  • δ ′ ( q 2 , 0 ) = δ ∗ ( { q 2 } , 0 ) = 无定义 \delta'(q_2,0)=\delta^*(\{q_2\},0)=无定义 δ′(q2​,0)=δ∗({q2​},0)=无定义
  • δ ′ ( q 2 , 1 ) = δ ∗ ( { q 2 } , 1 ) = 无定义 \delta'(q_2,1)=\delta^*(\{q_2\},1)=无定义 δ′(q2​,1)=δ∗({q2​},1)=无定义
  • δ ′ ( q 2 , 2 ) = δ ∗ ( { q 2 } , 2 ) = { q 2 } \delta'(q_2,2)=\delta^*(\{q_2\},2)=\{q_2\} δ′(q2​,2)=δ∗({q2​},2)={q2​}
• 确定接收状态：
  • F ∩ ε -CLOSURE ( q 0 ) = q 2 ∩ { q 0 , q 1 , q 2 } ≠ ϕ F \cap \varepsilon \text{-CLOSURE}(q_0) = {q_2} \cap \{q_0,q_1,q_2\} \ne \phi F∩ε-CLOSURE(q0​)=q2​∩{q0​,q1​,q2​}=ϕ，故 F ′ = F ∩ { q 0 } = { q 0 , q 2 } F'=F \cap \{q_0\}=\{q_0,q_2\} F′=F∩{q0​}={q0​,q2​}。
• 根据 NFA 的 $\delta$ 转换函数绘制状态图：

3 文法与下推自动机之间的转换

CFG 转换为单态 PDA

例： 已知形式语言 L = { a n b n ∣ n ≥ 1 } L=\{a^nb^n \mid n \ge 1\} L={anbn∣n≥1}，请构造 PDA 接收该语言。

思路：

• Step1：构造 CFG 接收该语言，由此得到文法 $G$ 的产生式。
• Step2：把文法 $G$ 的产生式转换为单态 PDA 的规则。

解答：

• 构造 CFG 如下：
  • $S\to aSB\mid aB$
  • $B\to b$
• 把文法 $G$ 的产生式转换为单态 PDA 的规则：

CFG 的产生式	单态 PDA 的规则
$S\to aSB$	$<a,S,SB>$
$S\to aB$	$<a,S,B>$
$B\to b$	$<b,B,\epsilon >$

Q：为啥教材里讲完 RLG 到单态 PDA 的转换要出这个例题？这也不是右线性文法啊？

单态 PDA 转换为 CFG

例： 请将下述单态 PDA 转换为 CFG 。

解答：

单态 PDA 的规则	CFG 的产生式
$<a,Z_0,A{Z}_0>$	$S\to aAS$
$<b,Z_0,B{Z}_0>$	$S\to bBS$
$<a,A,AA>$	$A\to aAA$
$<b,B,BB>$	$B\to bBB$
$<a,B,\epsilon >$	$B\to a$
$<b,A,\epsilon >$	$A\to b$
$<\epsilon ,Z_0,\epsilon >$	$S\to \epsilon$

• 整理得到文法 $G$ 的产生式如下：
  • $S\to aAS\mid bBS\mid \epsilon$
  • $A\to aAA\mid b$
  • $B\to bBB\mid a$

4 有限自动机与下推自动机之间的转换

NFA 转换为单态 PDA

转换方法如下：

NFA 的状态转换函数	单态 PDA 的规则
δ ( q , x ) = { q 1 , q 2 , ⋯   , q n } \delta(q,x)=\{q_1,q_2,\cdots,q_n\} δ(q,x)={q1​,q2​,⋯,qn​}	$<x,q,q_1>,<x,q,q_2>,\cdots ,<x,q,q_n>$

说明：没有例题。