《形式语言与自动机》答案.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.16M 资料格式：doc 举报版权申诉

kql1234-3297845-16359647559088260049.doc.pdf-第1页.png

第1页 / 共28页

kql1234-3297845-16359647559088260049.doc.pdf-第2页.png

第2页 / 共28页

kql1234-3297845-16359647559088260049.doc.pdf-第3页.png

第3页 / 共28页

kql1234-3297845-16359647559088260049.doc.pdf-第4页.png

第4页 / 共28页

kql1234-3297845-16359647559088260049.doc.pdf-第5页.png

第5页 / 共28页

kql1234-3297845-16359647559088260049.doc.pdf-第6页.png

第6页 / 共28页

kql1234-3297845-16359647559088260049.doc.pdf-第7页.png

第7页 / 共28页

kql1234-3297845-16359647559088260049.doc.pdf-第8页.png

第8页 / 共28页

(3) 是正则集

(1){a,b}*

(3)以b为首后跟若干个a的字符串的集合

P: S→aS S→bS S→ε

P: S→aS S→bS S→abb

P: S→bA A→aA A→ε

P: S→aS/bS/aaA/bbB

（2）假设该集合是正则集，对于足够大的k取ω= ak bk

（3）假设该集合是正则集，对于足够大的k取ω= ak cak

（4）假设该集合是正则集，对于足够大的k取ωω= ak bakb

N’ = { S, A1,A2,A3,A4,A5 }

NS1 = { S1,S,A1,A2,A3,A4, A5 } ,

NS = NA1 = NA2 = NA3 = NA4 = NA5 = { S, A1,A2,A3,A

N’ = { S }

NS1 = { S1,S } , NS = { S } , NA = { A } , NB = {

⑴对于D →SS ,用S →DD | a 代入得 D →DDS | aS | b ,

⑵将D生成式代入S生成式得 S →aSD | bD | aSD’D | bD'D | a ,

⑶将D生成式代入D’生成式得

⑷由此得出等价的Greibach范式文法：

因为有δ(q0,ε, Z0) = {(q0, ε)},则有

⑴{ anbncm | m≤n };

⑵{ ak | k是质数 };

⑶由 a,b,c 组成的字符串且是含有 a,b,c 的个数相同的所有字符串.

因为由Chomsky范式的定义可知,Chomsky范式文法的推导树都是二叉树,在最长路径长度为n的二

北京邮电大学——形式语言与自动机课后作业答案第二章 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} 其中 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 7．找出由下列各组生成式产生的语言（起始符为 S） (1) S→SaS S→b (2) S→aSb S→c (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 偶b b b 偶a 奇b 奇a 偶b b b 奇a 奇b a a 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→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）自动机如下： P1 a b P2 (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}),其中σ如下：

b q1 q2 q3 q3 b Φ Φ q2 b q0 q0 q0 q0 q1 q2 q3 a q0 q0 q0 q3 （2）M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下： q0 q1 q2 a q1 q2 q2 （3）M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下： q0 q1 q2 a q1 q2 q2 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] [ q0,q1, q2,q3] [ q0,q1, q3] [ q0,q2, q3] [ q0,q3] a [q0,q1] [q0,q1,q2] [ q0,q1, q2,q3] [ q0,q1, q3] [ q0,q1, q2,q3] [ q0,q1, q2,q3] [ q0,q1, q3] [ q0,q1, q3] b [ q0] [ q0,q2] [ q0,q2] [q0] [ q0,q2, q3] [ q0,q2, q3] [ q0,q3] [ q0,q3] （ 2 ） DFA M1={Q1, {a,b}, σ 1, [q0],{ [q1],[q3],

分享到：

赞收藏

资料库

《形式语言与自动机》答案.doc

相关推荐

课程资源

热门标签

最新资料