形式语言与自动机第三章课后题答案

**在这里插入图片描述**
考点：语言⇒DFA（设计DFA，记录关键信息）

解：（1） $M=(\{q_0,q_1,q_2,q_3\},\{a,b\},δ,q_0,\{q_3\})$ ，其中 δ 如下：
在这里插入图片描述
（2） $M=(\{q_0,q_1,q_2\},\{a,b\},δ,q_0,\{q_2\})$ ，其中 δ 如下：

（3） $M=(\{q_0,q_1,q_2\},\{a,b\},δ,q_0,\{q_2\})$ ，其中 δ 如下：

（4） $M=(\{q_0,q_1,q_2\},\{a,b\},δ,q_0,\{q_0,q_1,q_2\})$ ，其中 δ 如下：

在这里插入图片描述
考点：NFA⇒DFA （子集构造法：始态出发，遇什么填什么）
解：（1） $DFA-M_1=(Q_1,\{a,b\},δ_1,\{q_0\},\{ \{q_0,q_1,q_3 \},\{q_0,q_2,q_3 \},\{q_0,q_3 \},\{q_0,q_1,q_2,q_3\})，其中 Q_1=\{\{q_0\},\{q_0,q_1\},\{q_0,q_1,q_2\},\{q_0,q_2\},\{q_0,q_1,q_2,q_3\},\{q_0,q_1,q_3\},\{q_0,q_2,q_3\},\{q_0,q_3\}\}$
$δ_1$ 满足:
在这里插入图片描述
（2） $DFA M_1=(\{Q_1,\{a,b\},δ_1,\{q_0\},\{\{q_1\},\{q_3\},\{q_1,q_2\},\{q_0,q_1,q_2\},\{q_1,q_3\},\{q_1,q_2,q_3\},\{q_2,q_3\})$ ，其中 $Q_1=\{ \{q_0\},\{q_1,q_3\},\{q_1\},\{q_2\},\{q_0,q_1,q_2\},\{q_1,q_2\},\{q_3\},\{q_1,q_2,q_3\},\{q_2,q_3\}\}$
$δ_1$ 满足:
在这里插入图片描述

考点：文法⇒正则式 （R规则：设x→αx+β（x→αx|β），则x=α*β）
解：（1）联立方程组：

将④带入③中得： $B = b c B + b d + b$ ，利用规则R，得 $B=(bc)^* (bd+b)····⑤$
再将②和⑤带入①得： $S = b a a S + b a b B + B$
$= b a a S + (b a b + ε) B$
$baaS+(bab+ε) (bc)^* (bd+b)$
$baa)^* (bab+ε) (bc)^* (bd+b)$
∴得到正则式为 $baa)^* (bab+ε) (bc)^* (bd+b)$

（2）联立方程组：
在这里插入图片描述
由③和规则R得： $B=b^* a······⑥$
将⑤⑥带入④中得： $C=d+abb^* a=d+ab^+ a······⑦$
将⑥⑦带入②中得： $A=c(d+ab^+ a)+b^+ a······⑧$
将⑥⑧带入①中得： $S=ac(d+ab^+ a)+ab^+ a+b^* a$
$acd+acab^+ a+ab^+ a+b^* a$
∴得到正则式为 $acd+acab^+ a+ab^+ a+b^* a$

在这里插入图片描述
考点：自动机接受的语言；ε-NFA⇒NFA （先判断F，每步扩展空闭包）
解：（1）矩阵对应的ε-NFA如下：

利用排除法有，共23个串： $a a c, a b b, a b c, a c a, a c b, a c c, b a b, b a c, b b a, b b b, b b c, b c a, b c b, b c c, c a a, c a b, c a c, c b a, c b b, c b c, c c a, c c b, c c c$

（2）因为 $e c l o s u r e (q 0) \cap F = Ø$ ，则 $F_1=F=\{r\}$ ，则 $NFA -M=(\{p,q,r\},\{a,b,c\},δ_1,p,\{r\})$ ，其中 $δ_1$ ：
在这里插入图片描述

考点：正则集⇒右线性文法 （R规则逆用）
解：（2）题目对应的正则表达式为 $a+b)^* abb$ ，逆用R规则得到对应的右线性文法为 $G=(\{S\},\{a,b\},P,S)$ ，其中P： $S \to (a + b) S ∣ a b b$ ，即 $S \to a S ∣ b S ∣ a b b$

（4）题目对应的正则表达式为 $a+b)^* (aa+bb)(a+b)^*$ ，逆用R规则得到对应的右线性文法为 $G=(\{S,A\},\{a,b\},P,S)$ ，其中P为 $S \to (a + b) S ∣ a a A ∣ b b A, A \to (a + b) A ∣ ε$ ，即 $S \to a S ∣ b S ∣ a a A ∣ b b A, A \to a A ∣ b A ∣ ε$

在这里插入图片描述
考点：正则集⇒右线性文法；正则集⇒ε-NAF（有限自动机）；右线性文法⇒NFA
解：（1）逆用R规则得到对应右线性文法 $G=(\{S,A\},\{a,b\},P,S)$ ，其中P为 $S \to a A, A \to b a A ∣ ε$
（2）由（1）中右线性文法有 $S \to ε \in / P$ ，则转换为 $DFA-M=(\{S,A,H\},\{a,b\},δ,S,\{H\})$ ，其中 $δ$ 为：
对于产生式 $S \to a A$ ，有 $δ(S,a)=\{A\}$
对于产生式 $A \to b S$ ，有 $δ(A,b)=\{S\}$
对于产生式 $A \to ε$ ，有 $δ(A,ε)=\{H\}$
状态转移图如下:
在这里插入图片描述
继续进行化简，消去 $ε$ ，将状态A与H合并，得到下图：

考点：DFA⇒最小状态DFA （填表法）
解： $E, F, G, H$ 为不可达状态，删去后利用填表法：

由表格得： B,C等价， ${B,C\}$ 用 $[B]$ 表示，则等价最小DFA的转移图为：
在这里插入图片描述

考点：正则集的泵浦引理
解：（1）L(G)中，a和b的个数相等。由泵浦引理，假设L是正则集，取足够大的整数 k， $ω=a^k (cb)^k c，|ω|=3k+1>k,|ω_0|>0，0<|ω_1ω_0|≤k$ ，则 $ω_0$ 只能处于 $a^k$ 段。当 $i \neq = 1$ 时，a的个数发生改变，而b的个数不会变，a的个数≠b的个数，因此与假设矛盾，则L(G)不是正则集。

（3）由泵浦原理，假设L是正则集，取足够大的整数 $k,ω=0^k 12^{k+1},|ω|=2k+2>k,|ω_0 |>0，0<|ω_1 ω_0 |≤k$ ，限制了 $ω_0$ 只能在 $0^k$ 段。当 $i = 0$ 时， $ω_1 ω_0^0 ω_2$ 中0的数量减少，而1和2的个数没变，不满足 $0^n 1^m 2^{n+m}$ 。与假设矛盾，L不是正则集。

（4）由泵浦原理，假设L是正则集，取足够大的整数 $k，ω=a^k ba^k b，|ω|=2k+2>k，|ω_0 |>0，0<|ω_1 ω_0 |≤k$ ，限制了 $ω_0$ 只能处于 $a^k$ 段。当 $i \neq = 0$ 时， $a^k$ 段中a的个数发生改变，不等于k，不满足 ωω 的形式。与假设矛盾，L不是正则集。

在这里插入图片描述
考点：正则集的泵浦引理；设计正则式
解：（1）首先根据题意设计DFA，0、1的奇偶性需要4个状态来记录，因此容易得出DFA如下：

再利用状态消去的形式化方法，将DFA转换为正则式：
首先加初态s和终态a，与原自动机相，扩展为广义自动机：
在这里插入图片描述
接下来逐个消去中间状态，消去 $q_1$ ：

得到自动机：

最终得到正则式为 $0+(11)^+ 0+(10+(11)^+ 10)(01(11)^* 10)^* (1+01(11)^* 0)(0(11)^* 0+(1+0(11)^* 10)(01(11)^* 10)^* (1+01(11)^* 0))^*$

（2）由泵浦引理，假设L为正则集，取 $ω=a^{2p} b^p,|ω|=|ω_1ω_0ω_2|=3p＞p,0＜|ω_1ω_0|≤p$ ，因此限制了 $ω_1ω_0$ 只能在 $a^{2p}$ 段，当 $i = 0$ 时，a部分的长度减小，但b部分长度不变，a个数≠b个数，不符合L，与假设矛盾，因此L不是正则集。

在这里插入图片描述
考点：有限自动机⇒正则式 （状态消去形式化方法）
解：（a）使用状态消去形式化方法，消去 $q_1$ ,得到状态图：

直接得到正则式为 $a+b(b+ab)^* aa)^*$

（b）用形式化消去法，扩展为广义自动机有：
在这里插入图片描述
消去状态 $q_0$ 有：

消去状态 $q_1$ 有：

由此可直接写出正则式： $a(aa)^*+(b+a(aa)^* (b+ab)) (bb+(a+ba) (aa)^* (b+ab))^* (ε+(a+ba)(aa)^*)$

在这里插入图片描述
考点：构造米兰机和摩尔机；米兰机与摩尔机的相互转换
解：构造摩尔机 $M_1=(\{q_1,q_2,q_3,q_4,q_5\},\{a,b\},\{1,2,3\},δ,g,q_0)$ ，其中 $δ, g$ 如下：

直接将摩尔机转换为米兰机有（将状态中的输出放到弧上） $M_2=(\{q_1,q_2,q_3,q_4,q_5\},\{a,b\},\{1,2,3\},δ,g,q_0)$ ：
在这里插入图片描述