内容发布更新时间 : 2024/11/5 22:01:51星期一 下面是文章的全部内容请认真阅读。

北京邮电大学——形式语言与自动机课后作业答案

第二章

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 a 奇a偶b a b b b b a 偶a奇b 奇a奇b 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=ba+c(d+ba) ⑧

++

将⑥⑧代入① S=a(ba+c(d+aba))+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）中文法的有限自 b动机 答：（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)