北邮形式语言与自动机二三章答案.docx
《北邮形式语言与自动机二三章答案.docx》由会员分享，可在线阅读，更多相关《北邮形式语言与自动机二三章答案.docx（13页珍藏版）》请在冰点文库上搜索。
北邮形式语言与自动机二三章答案
形式语言与自动机课后作业答案
第二章
4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。
答：
G={N,T,P,S}
其中N={S,A,B,C,D}T={x,y}其中x€{所有字母}y€{所有的字符}P如下:
StxStxAAfyAfyB
BtyBtyCCtyCtyDDty
6．构造上下文无关文法能够产生
L={3/{a,b}*且3中a的个数是b的两倍}
答：
G={N,T,P,S}
其中N={S}T={a,b}P如下:
StaabStabaStbaa
StaabSStaaSbStaSabStSaab
StabaSStabSaStaSbaStSaba
StbaaSStbaSaStbSaaStSbaa
7．找出由下列各组生成式产生的语言（起始符为S）
（1）StSaSStb
（2）StaSbStc
（3）StaSfaEaS
答：
（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）是正则集，自动机如下
bbbb
⑵不是正则集，用泵浦引理可以证明，具体见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如下：
StaAStB
AtabSAtbB
BtbBtcC
CtDDtbB
Dtd
（2）G=（{S,A,B,C,D},{a,b,c,d},P,S）,生成式P如下：
StaAStB
AtcCAtbB
BtbBBta
CtDCtabB
Dtd
答：
（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的字符串的集合
⑷含有两个相继a和两个相继b的由a和b组成的所有字符串集合
答：
（1）右线性文法G=（{S},{a,b},P,S）
P:
S^aSStbSSt&
（2）右线性文法G=（{S},{a,b},P,S）
P:
S^aSStbSStabb
（3）此正则集为{ba*}
右线性文法G=（{S,A},{a,b},P,S）
P:
S^bAAtaAAt£
（4）此正则集为{{a,b}*aa{a,b}*bb{a,b}*,{a,b}*bb{a,b}*aa{a,b}*}
右线性文法G=（{SAB,C},{a,b},P,S）
P:
S^aS/bS/aaA/bbB
AtaA/bA/bbC
BtaB/bB/aaC
CtaC/bC/&
7.设正则集为a（ba）*
（1）构造右线性文法
（2）找出
（1）中文法的有限自动机
答：
（1）右线性文法G=（{S,A},{a,b},P,S）
P:
S^aAAtbSAt&
（2）自动机如下：
（p2是终结状态）
9.对应图（a）（b）的状态转换图写出正则式。
（图略）
（1）由图可知q°=aqo+bqi+a+e
q1=aq2+bq1
qo=aqo+bq1+a
=>q1=abq1+bq1+aaqo+aa
=（b+ab）q1+aaqo+aa
=（b+ab）*（aaqo+aa）
=>qo=aqo+b（b+ab）*（aaqo+aa）+a+e
=qo（a+b（b+ab）*aa）+b（b+ab）*aa+a+e
=（a+b（b+ab）*aa）*（（b+ab）*aa+a+e）
=（a+b（b+ab）*aa）*
（3）qo=aq1+bq2+a+b
q1=aqo+bq2+b
qo=aq1+bqo+a
=>q1=aqo+baq1+bbqo+ba+b
=（ba）*（aqo+bbqo+ba+b）
=>q2=aaqo+abq2+bqo+ab+a
=（ab）*（aaqo+bqo+ab+a）
=>qo=a（ba）*（a+bb）qo+a（ba）*（ba+b）+b（ab）*（aa+b）qo+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=（{qo,qiq2,q3},{a,b},（T,qo,{qs}）,其中如下:
a
b
qo
Qo
qi
qi
qo
q2
q2
qo
q3
q3
q3
q3
（2）M=（{qo,qiq2},{a,b},（T,qo,{q2}）,其中q如下:
a
b
qo
qi
①
qi
q2
①
q2
q2
q2
（3）M=（{qo,qiq2},{a,b},q,qo,{q2}）,其中q如下:
a
b
qo
qi
qo
qi
q2
qo
q2
q2
qo
14构造DFAMi等价于NFAM,NFAM如下：
（"M=（{qo,qiq2,q3},{a,b},o,qo,{q3}），其中c如下：
&（qo,a）={qo,qi}o（qo,b）={q0}
o（qi,a）={q2}o（qi,b）={q2}
o（q2,a）={q3}o（q2,b）=①
o（q3,a）={q3}o（q3,b）={q3}
（2）M=（{qo,qiq2,q3},{a,b},o,qo,{qi,q2}），其中o如下:
o（qo,a）={qi,q2}o（qo,b）={qi}
o（qi,a）={q2}o（qi,b）={qi,q2}
o（q2,a）={q3}o（q2,b）={qo}
o（q3,a）=①o（q3,b）={qo}
答：
（〔）DFAMi二{Qi,{a,b},o1,[qo],{[qo,qi,q3],[qo,q2,q3],[qo,qi,q2,q3]}
其中Qi二{[qo],[qo,qi],[qo,qi,q2],[qo,q2],[qo,qi,q2,q3],[qo,qi,q3】,[qo,q2,q3],[qo,q3]}
（T1满足
a
b
[qo]
[qo,q1]
[qo]
[qo,q1]
[qo,q1,q2]
[qo,q2]
[qo,q1,q2]
[qo,q1,q2,q3]
[qo,q2]
[qo,q2]
[qo,q1,q3]
[qo]
[qo,qi,q2,q3]
[qo,qi,q2,q3]
[qo,q2,q3]
[qo,qi,q3]
[qo,qi,q2,q3]
[qo,q2,q3]
[qo,q2,q3
[qo,qi,q3]
[qo,q3]
[qo,q3]
[qo,qi,q3]
[qo,q3]
（2）DFAMi={Qi,{a,b},&1,[qo],{[qi],"],
[qi,q3],[qo,qi,q2],[qi,q2],[qi,q2,q3],[q2,q3]}
其中Qi二{[qo],[qi,q3],[qi],[q2],[qo,qi,q2],[qi,q2],[q3],[qi,q2,q3],[q2,q3]}
（T1满足
a
b
[qo]
[qi,q3]
[qi]
[qi,q3]
[q2]
[qo,qi,q2]
[qi]
[q2]
[qi,q2]
[q2]
[q3]
[qo]
[qo,qi,q2]
[qi,q2,q3]
[qo,qi,q2]
[qi,q2]
[q2,q3]
[qo,qi,q2]
[q3]
①
[qo]
[qi,q2,q3]
[q2,q3]
[qo,qi,q2]
[q2,q3]
[q3]
[qo]
15.15对下面矩阵表示的£-NFA
£
a
b
c
p（起始状态）
©
{p}
{q}
{r}
q
{p}
{q}
{r}
©
r（终止状态）
{q}
{r}
©
{p}
（1）给出该自动机接收的所有长度为3的串
⑵将此£-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},（T,p,r）其中c如表格所示。
因为£-closure（p）={p}
则设不含£的NFAM=（{p,q,r},{a,b,c},c1,p,r）
（T1（p,a）=
:
c'（p,a）=
=£-closure（
c（c'（p,£）,a））={p}
q1（p,b）=
:
c'（p,b）=
=£-closure（
c（c'（p,£）,b））={p,q}
（T1（p,c）=
:
c'（p,c）=
:
£-closure（
c（c'（p,£）,c））={p,q,r}
31（q,a）=
:
c'q,a）=
=£-closure（
c（c（q,£）,a））={p,q}
q1（q,b）=
:
c'q,b）=
=£-closure（
c（c'q,£）,b））={p,q,r}
c1（q,c）=
:
c'q,c）=
:
£-closure（
c（c（q,£）,c））={p,q,r}
o-1（r,a）二
c'r,a）=
£-closure（
c（c'r,£）,a））={p,q,r}
o-1（r,b）=
c'r,b）=
£-closure（
c（c（r,£）,b））={p,q,r}
q1（r,c）=
c'r,c）=
£-closure（
c（c'r,£）,c））={p,q,r}
图示如下：
（r为终止状态）
a,b,c
16.设NFAM=（{qo,qi},{a,b},,qo,{qi}）,其中c如下：
&（qo,a）={qo,qi}c（qo,b）={qi}
c（qi,a）=①c（qi,b）={qo,qi}
构造相应的DFAMi,并进行化简
答：
构造一个相应的DFAMi二{Qi,{a,b},ci,[qo],{[qi]，[qo,qi]}
其中Qi={[qo],[qi],[qo,qi]}
（Ti满足
a
b
[qo]
[qo,qi]
[qi]
[qi]
①
[qo,qi]
[qo,qi]
[qo,qi]
[qo,qi]
由于该DFA已是最简，故不用化简
17.使用泵浦引理，证明下列集合不是正则集：
（1）由文法G的生成式S-aSbS/c产生的语言L（G）
（2）{3/{a,b}*且3有相同个数的a和b}
kk
（3）{aca/k>1}
（4）{33/3€{a,b}*}
证明：
（1）在L（G）中，a的个数与b的个数相等
假设L（G）是正则集，对于足够大的k取3=ak（cb）kc令3=313032
因为|3o|>O|313o|所以对于任意30只能取30=an€（0,k）
则313Oi32=ak-n（an）i（cb）kc在i不等于1时不属于L与假设矛盾。
则L（G）不是正则集
（2）假设该集合是正则集，对于足够大的k取3=akbk令3=313O32
因为|3o|>O|313o|Wk存在30使313032€L
所以对于任意3o只能取3o=ann€（0,k）
则313Oi32=ak-n（an）ibk在i不等于1时a与b的个数不同，不属于该集合
与假设矛盾。
则该集合不是正则集
（3）假设该集合是正则集，对于足够大的k取3=akcak令3=313032
因为|30|>0|3130|Wk存在30使313032€L
所以对于任意30只能取3o=ann€（0,k）
则313oi32=ak-n（an）icak在i不等于1时c前后a的个数不同,不属于该集合
与假设矛盾。
则该集合不是正则集
（4）假设该集合是正则集，对于足够大的k取33=akbakb
令33=313032
因为|3o|>O|313o|Wk存在30使313032€L
所以对于任意3o只能取3o=ann€（0,k）
则313oi32=ak-n（an）ibakb在i不等于1时不满足33的形式,不属于该集合
与假设矛盾。
则该集合不是正则集
18．构造米兰机和摩尔机
对于{a,b}*的字符串，如果输入以bab结尾，则输出1;如果输入以bba结尾，则输出2；否则输出3。
答：
米兰机：
说明状态qaa表示到这个状态时，输入的字符串是以aa结尾。
其他同理
摩尔机，状态说明同米兰机。
qbb,3
b/3
升级会员 