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

考点：文法⇒推导树

解：（1）

（2）

（3）

考点：文法⇒最左/右推导

解：最左推导：$E⇒_{lm} E+T⇒_{lm} T+T⇒_{lm} F+T⇒_{lm} b+T⇒_{lm} b+T/F⇒_{lm} b+F/F⇒_{lm} b+b/F⇒_{lm} b+b/b$E⇒lm​E+T⇒lm​T+T⇒lm​F+T⇒lm​b+T⇒lm​b+T/F⇒lm​b+F/F⇒lm​b+b/F⇒lm​b+b/b

最右推导：$E⇒_{rm} E+T⇒_{rm} E+T/F⇒_{rm} E+T/b⇒_{rm} E+F/b⇒_{rm} E+b/b⇒_{rm} T+b/b⇒_{rm} F+b/b⇒_{rm} b+b/b$E⇒rm​E+T⇒rm​E+T/F⇒rm​E+T/b⇒rm​E+F/b⇒rm​E+b/b⇒rm​T+b/b⇒rm​F+b/b⇒rm​b+b/b

考点：文法二义性证明
解：画出语言 $aaaba$aaaba 的2颗推导树如下：


同一文法可画出2个不同的推导树，因此该文法具有二义性。

考点：语言⇒上下文无关文法（设计上下文无关文法）

解：（1）考虑在产生相同数目的0,1后，再生成多余的1.
$G=(\{S\},\{0,1\},P,S)$G=({S},{0,1},P,S)，其中P为：$S→1S0|1S|10$S→1S0∣1S∣10

（2）考虑将0和1的部分拆开：$G=(\{S,A\},\{0,1\},P,S)$G=({S,A},{0,1},P,S)，其中P为：
$S→1A1|1S1$S→1A1∣1S1
$A→00A|00$A→00A∣00（服务 $0^{2m}$02m）

（3）考虑将语言拆为2部分：$G=(\{S,A,B\},\{0,1\},P,S)$G=({S,A,B},{0,1},P,S)，其中P为：
$S→AB$S→AB（拆为2部分）
$A→1A0|10$A→1A0∣10
$B→1B0|10$B→1B0∣10

考点：消除无用符号

解：（1）首先使用算法1，得到非生成符号C，删去C及其生成式有：
$S→ED$S→ED
$D→a$D→a
$E→b$E→b

使用算法2，发现没有不可达符号，因此等价文法为：$G=(\{S,D,E\},\{a,b\},P,S)$G=({S,D,E},{a,b},P,S)，其中P：
$S→ED$S→ED
$D→a$D→a
$E→b$E→b

（2）首先使用算法1，得到非生成符号C，删去C及其生成式有：
$S→D$S→D
$D→bS|b$D→bS∣b
$E→DS|b$E→DS∣b

使用算法2，发现不可达符号E，删去E及其生成式。因此等价文法为：$G=(\{S,D\}.\{b\},P,S)$G=({S,D}.{b},P,S)，其中P：
$S→D$S→D
$D→bS|b$D→bS∣b

考点：消空产生式

解：根据算法得，可得致空符号有：$D、E、C、S$D、E、C、S，$S$S 也为致空符号，因此加入 $S_1→S|ε$S1​→S∣ε，对于 $S→DCE$S→DCE 有：$S→DCE|CE|DE|DC|D|C|E$S→DCE∣CE∣DE∣DC∣D∣C∣E。因此消空后的等价文法为：$G_1=(\{S_1,S,C,D,E\},\{a,b\},P,S_1)$G1​=({S1​,S,C,D,E},{a,b},P,S1​)，其中 $P$P：
$S_1→S|ε$S1​→S∣ε
$S→DCE|CE|DE|DC|D|C|E$S→DCE∣CE∣DE∣DC∣D∣C∣E
$D→CC|C$D→CC∣C
$C→EE|E|b$C→EE∣E∣b
$E→DD|D|a$E→DD∣D∣a

考点：简化CFG（消无用→消空→消单→消无用 ）

解：首先消无用符号，利用算法1发现没有非生成符号，再利用算法2也没有发现不可达符号。

再消致空符号，利用算法发现所有符号都为致空符号。$S$S 为致空符号，因此将 $S_1→S|ε$S1​→S∣ε 加入P，P变为：
$S_1→S|ε$S1​→S∣ε
$S→A_1 |A_2$S→A1​∣A2​
$A_1→A_3 |A_4$A1​→A3​∣A4​
$A_2→A_4 |A_5$A2​→A4​∣A5​
$A_3→S|b$A3​→S∣b
$A_4→S|a$A4​→S∣a
$A_5→S|d$A5​→S∣d

再消除单产生式，构造 $N_S,N_{A_i},i=1,2,3,4,5$NS​,NAi​​,i=1,2,3,4,5，产生式的关系如下图：

因此P为：
$S_1→a|b|d|ε$S1​→a∣b∣d∣ε
$S→a|b|d$S→a∣b∣d
$A_1→a|b|d$A1​→a∣b∣d
$A_2→a|b|d$A2​→a∣b∣d
$A_3→a|b|d$A3​→a∣b∣d
$A_4→a|b|d$A4​→a∣b∣d
$A_5→a|b|d$A5​→a∣b∣d

最后消去无用符号，利用算法1发现没有非生成符号；再用算法2发现只有 $S_1$S1​ 为可达符号，删去其他符号及其产生式得到文法 $G_1=(\{S_1 \},\{a,b,d\},P,S_1)$G1​=({S1​},{a,b,d},P,S1​)，其中P为 $S_1→a|b|d|ε$S1​→a∣b∣d∣ε

考点：转换为CNF（Chomsky范式）

解：首先删除无用符号，利用算法1发现没有非生成符号，再利用算法2发现没有不可达符号；
再删除致空符号，利用算法发现S为致空符号，将 $S_1→ε|S$S1​→ε∣S加入到P中，此时P为：
$S_1→ε|S$S1​→ε∣S
$S→ASB|AB$S→ASB∣AB
$A→aAS|aA|a$A→aAS∣aA∣a
$B→SBS|SB|BS|A|bb$B→SBS∣SB∣BS∣A∣bb

再消单产生式，单产生式有：$S_1→S,B→A$S1​→S,B→A，因此此时P变为：
$S_1→ε|ASB|AB$S1​→ε∣ASB∣AB
$S→ASB|AB$S→ASB∣AB
$A→aAS|aA|a$A→aAS∣aA∣a
$B→SBS|BS|SB|bb|aAS|aA|a$B→SBS∣BS∣SB∣bb∣aAS∣aA∣a

再消去无用符号，利用算法1、2发现没有无用符号。
最后转换为CNF：对 $S_1→ε|AB,S→AB,A→a,B→BS|SB|a$S1​→ε∣AB,S→AB,A→a,B→BS∣SB∣a 为CNF，加入到P中。
将 $S_1→ASB$S1​→ASB 变换为 $S_1→AC,C→SB$S1​→AC,C→SB
将 $S→ASB$S→ASB 变换为 $S→AC$S→AC，
将 $A→aAS|aA$A→aAS∣aA 变换为 $A→ED，A→EA，D→AS，E→a$A→ED，A→EA，D→AS，E→a
将 $B→SBS|aAS|aA|bb$B→SBS∣aAS∣aA∣bb 变换为 $B→CS，B→ED，B→EA，B→FF，F→b$B→CS，B→ED，B→EA，B→FF，F→b

由此得到文法 $G1=(\{S_1,S,A,B,C,D,E,F\},\{a,b\},P_1,S_1)$G1=({S1​,S,A,B,C,D,E,F},{a,b},P1​,S1​)，其中 $P_1$P1​ 为：
$S_1→AB|ε|AC$S1​→AB∣ε∣AC
$S→AB|AC$S→AB∣AC
$A→ED|EA|a$A→ED∣EA∣a
$B→BS|SB|a|CS|ED|EA|FF$B→BS∣SB∣a∣CS∣ED∣EA∣FF
$C→SB$C→SB
$D→AS$D→AS
$E→a$E→a
$F→b$F→b

考点：转换为CNF（Chomsky范式）

解：先消除无用符号，利用算法1、2发现没有无用符号；再消致空符号，利用算法发现致空符号为A,B，因此P变为：
$S→0BB|0B|1AA|1A|0|1$S→0BB∣0B∣1AA∣1A∣0∣1
$B→0B0|00$B→0B0∣00
$A→11A|11$A→11A∣11

此时没有单产生式和无用符号，转换为CNF：$S→0|1$S→0∣1为CNF，加入到P中
将 $S→0BB$S→0BB 变换为 $S→CB，C→DB，D→0$S→CB，C→DB，D→0
将 $S→0B$S→0B 变换为 $S→DB$S→DB
将 $S→1AA$S→1AA 变换为 $S→EA$S→EA，$E→FA$E→FA，$F→1$F→1
将 $S→1A$S→1A 变换为 $S→FA$S→FA
将 $B→0B0$B→0B0 变换为 $B→CD$B→CD
将 $B→00$B→00 变换为 $B→DD$B→DD
将 $A→11A$A→11A 变换为 $A→FE$A→FE
将 $A→11$A→11 变换为 $A→FF$A→FF

由此得到的文法为：$G1=(\{S,A,B,C,D,E,F,G\},\{0,1\},P_1,S)$G1=({S,A,B,C,D,E,F,G},{0,1},P1​,S)，其中 $P_1$P1​ 如下：
$S→CB|DB|EA|FA|0|1$S→CB∣DB∣EA∣FA∣0∣1
$A→FE|FF$A→FE∣FF
$B→CD|DD$B→CD∣DD
$C→DB$C→DB
$D→0$D→0
$E→FA$E→FA
$F→1$F→1

考点：转换为GNF（Greibach范式）

解：题给产生式为CNF，N排序为 $S,D$S,D，其中D为高位，第2个式子右边首符序号＞左边的N，需要变换，将1式代入2式中有：$D→DDS|aS|b$D→DDS∣aS∣b

消除直接左递归，$D→aS|b|asD'|bD',D'→DS|DSD'$D→aS∣b∣asD′∣bD′,D′→DS∣DSD′

进行回代，此时N排序为 $D',S,D$D′,S,D，其中D为高位：
$D’$D’ 回代入$S$S：$S→aSD|bD|aSD'D|bD'D|a$S→aSD∣bD∣aSD′D∣bD′D∣a
$D$D 回代入$D’$D’： $D'→aSS|bS|asD'S|bD'S|aSSD'|bSD'|asD' SD'|bD'SD'$D′→aSS∣bS∣asD′S∣bD′S∣aSSD′∣bSD′∣asD′SD′∣bD′SD′

考点：
解：