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

考点：语言⇒DFA（设计DFA，记录关键信息）

解：（1）$M=(\{q_0,q_1,q_2,q_3\},\{a,b\},δ,q_0,\{q_3\})$M=({q0​,q1​,q2​,q3​},{a,b},δ,q0​,{q3​})，其中 δ 如下：

（2）$M=(\{q_0,q_1,q_2\},\{a,b\},δ,q_0,\{q_2\})$M=({q0​,q1​,q2​},{a,b},δ,q0​,{q2​})，其中 δ 如下：

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

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

考点：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\}\}$DFA−M1​=(Q1​,{a,b},δ1​,{q0​},{{q0​,q1​,q3​},{q0​,q2​,q3​},{q0​,q3​},{q0​,q1​,q2​,q3​})，其中Q1​={{q0​},{q0​,q1​},{q0​,q1​,q2​},{q0​,q2​},{q0​,q1​,q2​,q3​},{q0​,q1​,q3​},{q0​,q2​,q3​},{q0​,q3​}}
$δ_1$δ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\})$DFAM1​=({Q1​,{a,b},δ1​,{q0​},{{q1​},{q3​},{q1​,q2​},{q0​,q1​,q2​},{q1​,q3​},{q1​,q2​,q3​},{q2​,q3​})，其中 $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\}\}$Q1​={{q0​},{q1​,q3​},{q1​},{q2​},{q0​,q1​,q2​},{q1​,q2​},{q3​},{q1​,q2​,q3​},{q2​,q3​}}
$δ_1$δ1​ 满足:


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

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

（2）联立方程组：

由③和规则R得：$B=b^* a······⑥$B=b∗a⋅⋅⋅⋅⋅⋅⑥
将⑤⑥带入④中得：$C=d+abb^* a=d+ab^+ a······⑦$C=d+abb∗a=d+ab+a⋅⋅⋅⋅⋅⋅⑦
将⑥⑦带入②中得：$A=c(d+ab^+ a)+b^+ a······⑧$A=c(d+ab+a)+b+a⋅⋅⋅⋅⋅⋅⑧
将⑥⑧带入①中得：$S=ac(d+ab^+ a)+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
∴得到正则式为 $acd+acab^+ a+ab^+ a+b^* a$acd+acab+a+ab+a+b∗a

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

利用排除法有，共23个串：$aac,abb,abc,aca,acb,acc,bab,bac,bba,bbb,bbc,bca,bcb, bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc$aac,abb,abc,aca,acb,acc,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc

（2）因为$eclosure(q0)∩F=Ø$eclosure(q0)∩F=Ø，则$F_1=F=\{r\}$F1​=F={r}，则$NFA -M=(\{p,q,r\},\{a,b,c\},δ_1,p,\{r\})$NFA−M=({p,q,r},{a,b,c},δ1​,p,{r})，其中$δ_1$δ1​：

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

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

考点：正则集⇒右线性文法；正则集⇒ε-NAF（有限自动机）；右线性文法⇒NFA
解：（1）逆用R规则得到对应右线性文法 $G=(\{S,A\},\{a,b\},P,S)$G=({S,A},{a,b},P,S)，其中P为 $S→aA,A→baA|ε$S→aA,A→baA∣ε
（2）由（1）中右线性文法有 $S→ε∉P$S→ε∈/​P，则转换为 $DFA-M=(\{S,A,H\},\{a,b\},δ,S,\{H\})$DFA−M=({S,A,H},{a,b},δ,S,{H})，其中$δ$δ为：
对于产生式 $S→aA$S→aA，有 $δ(S,a)=\{A\}$δ(S,a)={A}
对于产生式 $A→bS$A→bS，有 $δ(A,b)=\{S\}$δ(A,b)={S}
对于产生式 $A→ε$A→ε，有 $δ(A,ε)=\{H\}$δ(A,ε)={H}
状态转移图如下:

继续进行化简，消去 $ε$ε，将状态A与H合并，得到下图：


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

由表格得： B,C等价，$\{B,C\}${B,C}用 $[B]$[B] 表示，则等价最小DFA的转移图为：


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

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

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

考点：
解：

考点：
解：

考点：
解：