《形式语言与自动机》王柏杨娟编著答案.docx
《《形式语言与自动机》王柏杨娟编著答案.docx》由会员分享，可在线阅读，更多相关《《形式语言与自动机》王柏杨娟编著答案.docx（25页珍藏版）》请在冰点文库上搜索。
《形式语言与自动机》王柏杨娟编著答案
形式语言与自动机课后习题答案
第二章
4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。
答：
G={N,T,P,S}
其中N={S,A,B,C,D}T={x,y}其中x∈{所有字母}y∈{所有的字符}P如下:
S→xS→xAA→yA→yB
B→yB→yCC→yC→yDD→y
6．构造上下文无关文法能够产生
L={ω/ω∈{a,b}*且ω中a的个数是b的两倍}
答：
G={N,T,P,S}
其中N={S}T={a,b}P如下:
S→aabS→abaS→baa
S→aabSS→aaSbS→aSabS→Saab
S→abaSS→abSaS→aSbaS→Saba
S→baaSS→baSaS→bSaaS→Sbaa
7．找出由下列各组生成式产生的语言（起始符为S）
（1）S→SaSS→b
（2）S→aSbS→c
（3）S→aS→aEE→aS
答：
（1）b（ab）n/n≥0}或者L={（ba）nb/n≥0}
（2）L={ancbn/n≥0}
（3）L={a2n+1/n≥0}
第三章
1．下列集合是否为正则集，若是正则集写出其正则式。
（1）含有偶数个a和奇数个b的{a,b}*上的字符串集合
（2）含有相同个数a和b的字符串集合
（3）不含子串aba的{a,b}*上的字符串集合
答：
（1）是正则集，自动机如下
a
a
bbbb
a
a
（2）不是正则集，用泵浦引理可以证明，具体见17题
（2）。
（3）是正则集
先看L’为包含子串aba的{a,b}*上的字符串集合
显然这是正则集，可以写出表达式和画出自动机。
（略）
则不包含子串aba的{a,b}*上的字符串集合L是L’的非。
根据正则集的性质，L也是正则集。
4．对下列文法的生成式，找出其正则式
（1）G=（{S,A,B,C,D},{a,b,c,d},P,S）,生成式P如下：
S→aAS→B
A→abSA→bB
B→bB→cC
C→DD→bB
D→d
（2）G=（{S,A,B,C,D},{a,b,c,d},P,S）,生成式P如下：
S→aAS→B
A→cCA→bB
B→bBB→a
C→DC→abB
D→d
答：
（1）由生成式得：
S=aA+B①
A=abS+bB②
B=b+cC③
C=D④
D=d+bB⑤
③④⑤式化简消去CD，得到B=b+c（d+bB）
即B=cbB+cd+b=>B=（cb）*（cd+b）⑥
将②⑥代入①
S=aabS+ab（cb）*（cd+b）+（cb）*（cd+b）=>S=（aab）*（ab+ε）（cb）*（cd+b）
（2）由生成式得：
S=aA+B①
A=bB+cC②
B=a+bB③
C=D+abB④
D=dB⑤
由③得B=b*a⑥
将⑤⑥代入④C=d+abb*a=d+ab+a⑦
将⑥⑦代入②A=b+a+c（d+b+a）⑧
将⑥⑧代入①S=a（b+a+c（d+ab+a））+b*a
=ab+a+acd+acab+a+b*a
5.为下列正则集，构造右线性文法：
（1）{a,b}*
（2）以abb结尾的由a和b组成的所有字符串的集合
（3）以b为首后跟若干个a的字符串的集合
（4）含有两个相继a和两个相继b的由a和b组成的所有字符串集合
答：
（1）右线性文法G=（{S},{a,b},P,S）
P:
S→aSS→bSS→ε
（2）右线性文法G=（{S},{a,b},P,S）
P:
S→aSS→bSS→abb
（3）此正则集为{ba*}
右线性文法G=（{S,A},{a,b},P,S）
P:
S→bAA→aAA→ε
（4）此正则集为{{a,b}*aa{a,b}*bb{a,b}*,{a,b}*bb{a,b}*aa{a,b}*}
右线性文法G=（{S,A,B,C},{a,b},P,S）
P:
S→aS/bS/aaA/bbB
A→aA/bA/bbC
B→aB/bB/aaC
C→aC/bC/ε
7.设正则集为a（ba）*
（1）构造右线性文法
（2）找出
（1）中文法的有限自b动机
答：
（1）右线性文法G=（{S,A},{a,b},P,S）
P:
S→aAA→bSA→ε
（2）自动机如下：
a
b
（p2是终结状态）
9.对应图（a）（b）的状态转换图写出正则式。
（图略）
（1）由图可知q0=aq0+bq1+a+ε
q1=aq2+bq1
q0=aq0+bq1+a
=>q1=abq1+bq1+aaq0+aa
=（b+ab）q1+aaq0+aa
=（b+ab）*（aaq0+aa）
=>q0=aq0+b（b+ab）*（aaq0+aa）+a+ε
=q0（a+b（b+ab）*aa）+b（b+ab）*aa+a+ε
=（a+b（b+ab）*aa）*（（b+ab）*aa+a+ε）
=（a+b（b+ab）*aa）*
（3）q0=aq1+bq2+a+b
q1=aq0+bq2+b
q0=aq1+bq0+a
=>q1=aq0+baq1+bbq0+ba+b
=（ba）*（aq0+bbq0+ba+b）
=>q2=aaq0+abq2+bq0+ab+a
=（ab）*（aaq0+bq0+ab+a）
=>q0=a（ba）*（a+bb）q0+a（ba）*（ba+b）+b（ab）*（aa+b）q0+b（ab）*（ab+a）+a+b
=[a（ba）*（a+bb）+b（ab）*（aa+b）]*（a（ba）*（ba+b）+b（ab）*（ab+a）+a+b）
10.设字母表T={a,b},找出接受下列语言的DFA：
（1）含有3个连续b的所有字符串集合
（2）以aa为首的所有字符串集合
（3）以aa结尾的所有字符串集合
答：
（1）M=（{q0,q1q2,q3},{a,b},σ,q0,{q3}）,其中σ如下：
a
b
q0
q0
q1
q1
q0
q2
q2
q0
q3
q3
q3
q3
（2）M=（{q0,q1q2},{a,b},σ,q0,{q2}）,其中σ如下：
a
b
q0
q1
Φ
q1
q2
Φ
q2
q2
q2
（3）M=（{q0,q1q2},{a,b},σ,q0,{q2}）,其中σ如下：
a
b
q0
q1
q0
q1
q2
q0
q2
q2
q0
14构造DFAM1等价于NFAM，NFAM如下：
（1）M=（{q0,q1q2,q3},{a,b},σ,q0,{q3}）,其中σ如下：
σ（q0,a）={q0,q1}σ（q0,b）={q0}
σ（q1,a）={q2}σ（q1,b）={q2}
σ（q2,a）={q3}σ（q2,b）=Φ
σ（q3,a）={q3}σ（q3,b）={q3}
（2）M=（{q0,q1q2,q3},{a,b},σ,q0,{q1,q2}）,其中σ如下：
σ（q0,a）={q1,q2}σ（q0,b）={q1}
σ（q1,a）={q2}σ（q1,b）={q1,q2}
σ（q2,a）={q3}σ（q2,b）={q0}
σ（q3,a）=Φσ（q3,b）={q0}
答：
（1）DFAM1={Q1,{a,b},σ1,[q0],{[q0,q1,q3]，[q0,q2,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满足
a
b
[q0]
[q0,q1]
[q0]
[q0,q1]
[q0,q1,q2]
[q0,q2]
[q0,q1,q2]
[q0,q1,q2,q3]
[q0,q2]
[q0,q2]
[q0,q1,q3]
[q0]
[q0,q1,q2,q3]
[q0,q1,q2,q3]
[q0,q2,q3]
[q0,q1,q3]
[q0,q1,q2,q3]
[q0,q2,q3]
[q0,q2,q3]
[q0,q1,q3]
[q0,q3]
[q0,q3]
[q0,q1,q3]
[q0,q3]
（2）DFAM1={Q1,{a,b},σ1,[q0],{[q1],[q3],[q1,q3],[q0,q1,q2],[q1,q2],[q1,q2,q3],[q2,q3]}
其中Q1={[q0],[q1,q3],[q1],[q2],[q0,q1,q2],[q1,q2],[q3],[q1,q2,q3],[q2,q3]}
σ1满足
a
b
[q0]
[q1,q3]
[q1]
[q1,q3]
[q2]
[q0,q1,q2]
[q1]
[q2]
[q1,q2]
[q2]
[q3]
[q0]
[q0,q1,q2]
[q1,q2,q3]
[q0,q1,q2]
[q1,q2]
[q2,q3]
[q0,q1,q2]
[q3]
Φ
[q0]
[q1,q2,q3]
[q2,q3]
[q0,q1,q2]
[q2,q3]
[q3]
[q0]
15.15.对下面矩阵表示的ε-NFA
ε
a
b
c
P（起始状态）
φ
{p}
{q}
{r}
q
{p}
{q}
{r}
φ
r（终止状态）
{q}
{r}
φ
{p}
（1）给出该自动机接收的所有长度为3的串
（2）将此ε-NFA转换为没有ε的NFA
答：
（1）可被接受的的串共23个，分别为aac,abc,acc,bac,bbc,bcc,cac,cbc,ccc,caa,cab,cba,cbb,cca,ccb,bba,aca,acb,bca,bcb,bab,bbb,abb
（2）ε-NFA：
M=（{p,q,r},{a,b,c},σ,p,r）其中σ如表格所示。
因为ε-closure（p）=Φ
则设不含ε的NFAM1=（{p,q,r},{a,b,c},σ1,p,r）
σ1（p,a）=σ’（p,a）=ε-closure（σ（σ’（p,ε）,a））={p}
σ1（p,b）=σ’（p,b）=ε-closure（σ（σ’（p,ε）,b））={p,q}
σ1（p,c）=σ’（p,c）=ε-closure（σ（σ’（p,ε）,c））={p,q,r}
σ1（q,a）=σ’（q,a）=ε-closure（σ（σ’（q,ε）,a））={p,q}
σ1（q,b）=σ’（q,b）=ε-closure（σ（σ’（q,ε）,b））={p,q,r}
σ1（q,c）=σ’（q,c）=ε-closure（σ（σ’（q,ε）,c））={p,q,r}
σ1（r,a）=σ’（r,a）=ε-closure（σ（σ’（r,ε）,a））={p,q,r}
σ1（r,b）=σ’（r,b）=ε-closure（σ（σ’（r,ε）,b））={p,q,r}
σ1（r,c）=σ’（r,c）=ε-closure（σ（σ’（r,ε）,c））={p,q,r}
图示如下：
（r为终止状态）
b,c
a,b,ca,b,ca,b,c
ca,b,cb,ca,b,c
a,b,c
16．设NFAM=（{q0,q1},{a,b},σ,q0,{q1}）,其中σ如下：
σ（q0,a）={q0,q1}σ（q0,b）={q1}
σ（q1,a）=Φσ（q1,b）={q0,q1}
构造相应的DFAM1，并进行化简
答：
构造一个相应的DFAM1={Q1,{a,b},σ1,[q0],{[q1]，[q0,q1]}
其中Q1={[q0]，[q1]，[q0,q1]}
σ1满足
a
b
[q0]
[q0,q1]
[q1]
[q1]
Φ
[q0,q1]
[q0,q1]
[q0,q1]
[q0,q1]
由于该DFA已是最简，故不用化简
17.使用泵浦引理，证明下列集合不是正则集：
（1）由文法G的生成式S→aSbS/c产生的语言L（G）
（2）{ω/ω∈{a,b}*且ω有相同个数的a和b}
（3）{akcak/k≥1}
（4）{ωω/ω∈{a,b}*}
证明：
（1）在L（G）中，a的个数与b的个数相等
假设L（G）是正则集，对于足够大的k取ω=ak（cb）kc
令ω=ω1ω0ω2
因为|ω0|>0|ω1ω0|≤k存在ω0使ω1ω0iω2∈L
所以对于任意ω0只能取ω0=ann∈（0,k）
则ω1ω0iω2=ak–n（an）i（cb）kc在i不等于0时不属于L
与假设矛盾。
则L（G）不是正则集
（2）假设该集合是正则集，对于足够大的k取ω=akbk
令ω=ω1ω0ω2
因为|ω0|>0|ω1ω0|≤k存在ω0使ω1ω0iω2∈L
所以对于任意ω0只能取ω0=ann∈（0,k）
则ω1ω0iω2=ak–n（an）ibk在i不等于0时a与b的个数不同，不属于该集合
与假设矛盾。
则该集合不是正则集
（3）假设该集合是正则集，对于足够大的k取ω=akcak
令ω=ω1ω0ω2
因为|ω0|>0|ω1ω0|≤k存在ω0使ω1ω0iω2∈L
所以对于任意ω0只能取ω0=ann∈（0,k）
则ω1ω0iω2=ak–n（an）icak在i不等于0时c前后a的个数不同，不属于该集合
与假设矛盾。
则该集合不是正则集
（4）假设该集合是正则集，对于足够大的k取ωω=akbakb
令ωω=ω1ω0ω2
因为|ω0|>0|ω1ω0|≤k存在ω0使ω1ω0iω2∈L
所以对于任意ω0只能取ω0=ann∈（0,k）
则ω1ω0iω2=ak–n（an）ibakb在i不等于0时不满足ωω的形式，不属于该集合
与假设矛盾。
则该集合不是正则集
18．构造米兰机和摩尔机
对于{a,b}*的字符串，如果输入以bab结尾，则输出1；如果输入以bba结尾，则输出2；否则输出3。
答：
米兰机：
说明状态qaa表示到这个状态时，输入的字符串是以aa结尾。
其他同理。
a/3
b/3
a/3a/3b/3
b/1
a/2b/3
摩尔机，状态说明同米兰机。
aa
ba
abab
ab
b
b
Ø第四章
10.把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法：
S→A1|A2,A1→A3|A4,A2→A4|A5,A3→S|b|ε,A4→S|a，A5→S|d|ε
解:
⑴由算法3，变换为无ε生成式：
N’={S,A1,A2,A3,A4,A5}
G1=（{S1,S,A1,A2,A3,A4,A5},{a,b,d},P1,S1）,其中生成式P1如下：
S1→ε|S,
S→A1|A2,
A1→A3|A4,
A2→A4|A5,
A3→S|b,
A4→S|a,
A5→S|d,
⑵由算法4，消单生成式：
NS1={S1,S,A1,A2,A3,A4,A5},
NS=NA1=NA2=NA3=NA4=NA5={S,A1,A2,A3,A4,A5},
运用算法4，则P1变为：
S1→a|b|d|ε,
S→a|b|d,
A1→a|b|d,
A2→a|b|d,
A3→a|b|d,
A4→a|b|d,
A5→a|b|d
⑶由算法1和算法2，消除无用符号，得到符合题目要求的等价文法：
G1=（{S1},{a,b,d},P1,S1），其中生成式P1为：
S1→a|b|d|ε.
11.设2型文法G=（{S,A,B,C,D,E,F},{a,b,c},P,S）,其中P：
S→ASB|ε;A→aAS|a;B→SBS|A|bb
试将G变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.
解:
⑴由算法3，变换为无ε生成式：
N’={S}
由S→ASB得出S→ASB|AB,
由A→aAS得出A→aAS|aA,
由B→SBS得出B→SBS|SB|BS|B,
由S∈N’得出S1→ε|S,
因此无ε的等效文法G1=（{S1,S,A,B},{a,b,d},P1,S1）,其中生成式P1如下：
S1→ε|S,
S→ASB|AB,
A→aAS|aA|a,
B→SBS|SB|BS|B|A|bb,
⑵由算法4，消单生成式：
NS1={S1,S},NS={S},NA={A},NB={A,B}
由于S→ASB|AB∈P且不是单生成式,故P1中有S1→ε|ASB|AB,
同理有S→ASB|AB,A→aAS|aA|a,B→SBS|SB|BS|aAS|aA|a|bb,
因此生成的无单生成式等效文法为
G1=（{S1,S,A,B},{a,b},P1,S1）,其中生成式P1如下：
S1→ε|ASB|AB,
S→ASB|AB,
A→aAS|aA|a,
B→SBS|SB|BS|aAS|aA|a|bb,
⑶由算法1和算法2，消除无用符号（此题没有无用符号）;
⑷转化为等价的Chomsky范式的文法:
将S1→ASB变换为S→AC,C→SB,
将S→ASB变换为S→AC,
将A→aAS|aA变换为A→ED|EA,D→AS,E→a,
将B→SBS|aAS|aA|a|bb,变换为B→CS|ED|EA|FF,F→b,
⑸由此得出符合题目要求的等价文法：
G1=（{S1,S,A,B,C,D},{a,b},P1,S1）,其中生成式P1如下：
S1→ε|AC|AB,
S→AC|AB,
A→ED|EA|a,
B→CS|SB|BS|ED|EA|a|FF,
C→SB,
D→AS,
E→a,
F→b.
15.将下列文法变换为等价的Greibach范式文法:
⑴S→DD|a,D→SS|b
解:
将非终结符排序为S,D,S为低位,D为高位,
⑴对于D→SS,用S→DD|a代入得D→DDS|aS|b,
用引理4.2.4,变化为D→aS|b|aSD'|bD',D’→DS|DSD’,
⑵将D生成式代入S生成式得S→aSD|bD|aSD’D|bD'D|a,
⑶将D生成式代入D’生成式得
D’→aSS|bS|aSD'S|bD'S|aSSD'|bSD'|aSD'SD'|bD'SD',
⑷由此得出等价的Greibach范式文法：
G1=（{S,D,D’},{a,b},P1,S）,其中生成式P1如下：
S→aSD|bD|aSD’D|bD'D|a,
D→aS|b|aSD'|bD',
D’→aSS|bS|aSD'S|bD'S|aSSD'|bSD'|aSD'SD'|bD'SD'.
⑵A1→A3b|A2a,A2→A1b|A2A2a|b,A3→A1a|A3A3b|a
解:
⑴转化为等价的Chomsky范式的文法:
A1→A3A4|A2A5,
A2→A1A4|A2A6|b,
A3→A1A5|A3A7|a,
A4→b,
A5→a,
A6→A2A5,
A7→A3A4,
⑵转化为等价的Greibach范式的文法:
将非终结符排序为A1,A2,A3,A4,A5,A1为低位A5为高位,
①对于A2→A1A4,用A1→A3A4|A2A5代入得A2→A3A4A4|A2A5A4|A2A6|b,
用引理4.2.4,变化为
A2→A3A4A4|b|A3A4A4A2’|bA2’,
A2’→A5A4A2’|A6A2’|A5A4|A6,
②对于A3→A1A5,用A1→A3A4|A2A5代入得A3→A3A4A5|A2A5A5|A3A7|a,
A3生成式右边第一个字符仍是较低位的非终结符,将A2生成式代入A3生成式得
A3→A3A4A5|A3A4A4A5A5|bA5A5|A3A4A4A2’A5A5|bA2’A5A5|A3A7|a,
用引理4.2.4,变化为
A3→bA5A5|bA2’A5A5|a|bA5A5A3’|bA2’A5A5A3’|aA3’,
A3’→A4A5|A4A4A5A5|A4A4A2’A5A5|A7|A4A5A3’|A4A4A5A5A3’|A4A4A2’A5A5A3’|A7A3’,
③对于A6→A2A5,将A2生成式代入A6生成式得
A6→A3A4A4A5|bA5|A3A4A4A2’A5|bA2’A5,
A6生成式右边第一个字符仍是较低位的非终结符,将A3生成式代入A6生成式得
A6→bA5A5A4A4A5|bA2’A5A5A4A4A5|aA4A4A5|bA5A5A3’A4A4A5|bA2’A5A5A3’A4A4A5|aA3’A4A4A5|bA5A5A4A4A2’A5|bA2’A5A5A4A4A2’A5|aA4A4A2’A5|bA5A5A3’A4A4A2’A5|bA2’A5A5A3’A4A4A2’A5|aA3’A4A4A2’A5|bA2’A5|bA5,
④对于A7→A3A4,将A3生成式代入A7生成式得
A7→bA5A5A4|bA2’A5A5A4|aA4|bA5A5A3’A4|bA
升级会员 