北邮形式语言与自动机二三章答案
更新时间:2024-04-21 11:24:01 阅读量: 综合文库 文档下载
- 形式语言与自动机理论推荐度:
- 相关推荐
形式语言与自动机课后作业答案
第二章
4.找出右线性文法,能构成长度为1至5个字符且以字母为首的字符串。
答:G={N,T,P,S}
其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字
符} P如下:
S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y
6.构造上下文无关文法能够产生
L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答:G={N,T,P,S}
7.找出由下列各组生成式产生的语言(起始符为S) (1) S→SaS S→b (2) S→aSb S→c
其中N={S} T={a,b} P如下: S→aab S→aba S→baa
S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa
(3) S→a S→aE E→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偶b 奇a偶b a b b b b a a
(2) 不是正则集,用泵浦引理可以证明,具体见17题(2)。 (3) 是正则集
先看L’为包含子串aba的{a,b}*上的字符串集合
显然这是正则集,可以写出表达式和画出自动机。(略)
偶a奇b 奇a奇b 则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质,L也是正则集。
4.对下列文法的生成式,找出其正则式
(1) G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下:
S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d
(2) G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下:
S→aA S→B A→cC A→bB B→bB B→a C→D C→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→aS S→bS S→ε
(2) 右线性文法G=({S},{a,b},P,S)
P: S→aS S→bS S→abb
(3) 此正则集为{ba*}
右线性文法G=({S,A},{a,b},P,S) P: S→bA A→aA A→ε
(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)中文法的有限自动机 答:(1)右线性文法G=({S,A},{a,b},P,S)
P: S→aA A→bS A→ε
(2)自动机如下: a P1 P2 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,q1 q2,q3},{a,b},σ,q0,{q3}),其中σ如下: q0 q1 q2 q3
(2)M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下:
q0 q1 q2
(3)M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下:
q0 q1 q2 a q1 q2 q2 b q0 q0 q0 a q1 q2 q2 b Φ Φ q2 a Q0 q0 q0 q3 b q1 q2 q3 q3
14构造DFA M1等价于NFA M,NFA M如下: (1)M=({q0,q1 q2,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,q1 q2,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)DFA M1={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满足 [q0] [q0,q1] [q0,q1,q2] [ q0,q2] a [q0,q1] [q0,q1,q2] [ q0,q1, q2,q3] [ q0,q1, q3] b [ q0] [ q0,q2] [ q0,q2] [q0] [ q0,q1, q2,q3] [ q0,q1, q3] [ q0,q2, q3] [ q0,q3]
(2)DFA
[ q0,q1, q2,q3] [ q0,q1, q2,q3] [ q0,q1, q3] [ q0,q1, q3] [ q0,q2, q3] [ q0,q2, q3] [ q0,q3] [ q0,q3] M1={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满足 [q0] [q1,q3] [q1] [q2] [ q0,q1,q2] [q1,q2] [q3] [q1,q2,q3] [q2,q3]
a [q1,q3] [q2] [q2] [q3] [q1,q2,q3] [q2,q3] Φ [q2,q3] [q3] b [q1] [ q0,q1,q2] [q1,q2] [q0] [ q0,q1,q2] [ q0,q1,q2] [q0] [ q0,q1,q2] [q0] 15. 15.对下面矩阵表示的ε-NFA ε a {p} {q} {r} b {q} {r} φ c {r} φ {p} P(起始状态) φ q {p} r(终止状态) {q} (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)={p}
则设不含ε的NFA M1=({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 p q a,b,c a,b,c a,b,c c a,b,c b,c a,b,c
a,b,c
16.设NFA M=({q0,q1},{a,b},σ,q0,{q1}),其中σ如下:
σ(q0,a)={q0,q1} σ(q0,b)={q1} σ(q1,a)= Φ σ(q1,b)= {q0, q1}
r 构造相应的DFA M1,并进行化简
答:构造一个相应的DFA M1={Q1, {a,b},σ1, [q0],{ [q1],[q0,q1]} 其中Q1 ={[q0],[q1],[q0,q1]} σ1满足 [q0] [q1] [q0,q1] a [q0,q1] Φ [q0,q1] b [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ωi0ω2∈L 所以对于任意ω0只能取ω0=an n∈(0,k)
则ωik–n1ω0ω2= a(an)i(cb)kc 在i不等于1时不属于L 与假设矛盾。则L(G)不是正则集
(2)假设该集合是正则集,对于足够大的k取ω= ak bk 令ω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ωi0ω2∈L 所以对于任意ωn0只能取ω0=a n∈(0,k)
则ωi1ω0ωk–nn2= a(a)ibk 在i不等于1时a与b的个数不同,不属于该集合
与假设矛盾。则该集合不是正则集
(3)假设该集合是正则集,对于足够大的k取ω= ak cak 令ω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ωi1ω0ω2∈L
所以对于任意ω0只能取ω0=an n∈(0,k)
则ω1ω0iω2= ak–n(an)icak 在i不等于1时c前后a的个数不同,不属于该集合
与假设矛盾。则该集合不是正则集
(4)假设该集合是正则集,对于足够大的k取ωω= ak bakb 令ωω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L 所以对于任意ω0只能取ω0=an n∈(0,k)
则ω1ω0iω2= ak–n(an)ibakb 在i不等于1时不满足ωω的形式,不属于该集合
与假设矛盾。则该集合不是正则集
18.构造米兰机和摩尔机
对于{a,b}*的字符串,如果输入以bab结尾,则输出1;如果输入以bba结尾,则输出2;否则输出3。 答:米兰机:
说明状态qaa表示到这个状态时,输入的字符串是以aa结尾。其
他同理。
a/3 qaa qab b/3 a/3 a/3 b/3 b/1 qba a/2 qbb b/3
摩尔机,状态说明同米兰机。
a a qaa,3 b qaab,3 a b/3 b/3 qaba,3 b/3 a b a b qbba,2 a qbb,3 b b/3 qbab,1 b/3 b b
b/3
正在阅读:
北邮形式语言与自动机二三章答案04-21
下雪堆雪人简笔画02-12
JSP在EBS中的开发 - V1.001-29
吉大19年9月课程考试薪酬管理离线作业考核要求离线作业答案01-05
2013修订版毛概课后习题答案05-16
2016.7盐池一小体卫艺工作总结04-12
质谱条件05-14
净度分级04-06
应急准备响应方案(金海湾)10-28
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 自动机
- 北邮
- 形式
- 答案
- 语言
- 二三