第二章
4•找出右线性文法，能构成长度为 1至5个字符且以字母为首的字符串。
答：G={N,T,P,S}
其中N={S,A,B,C,D} T={x,y} 其中x€ {所有字母} y € {所有的字符} P如下:
4 x S 4 y B L={ 3 /
f xA A f y A f yB
f yC C f y C f yD D f y 6 •构造上下文无关文法能够产生
{a,b}*且3中a的个数是b的两倍}
答: G={N,T,P,S}
其中 N={S} T={a,b} P 如下：
Sf aab S f aba S Sf aabS S Sf abaS S Sf baaS S
f baa
f aaSbS f aSab S f Saab f abSaS f aSba S f Saba f baSaS f bSaa S f Sbaa
S)
7 •找出由下列各组生成式产生的语言(起始符为 ⑴ Sf SaS S f b ⑵ Sf aSb S f c (3) Sf a S f aE E f aS
答：(1) b(ab) n /n > 0}或者 L={(ba) nb /n > 0}
(2) L={a ncbn /n > 0} (3) L={a2n+1 /n > 0}
第三章
1.下列集合是否为正则集，若是正则集写出其正则式。
(1) (2) (3)
含有偶数个a和奇数个b的{a,b}*上的字符串集合 含有相同个数a和b的字符串集合 不含子串aba的{a,b}*上的字符串集合
答：(1)是正则集，自动机如下
b b b b
⑵ 不是正则集，用泵浦引理可以证明，具体见 17题(2) (3) 是正则集
先看L '为包含子串aba的{a,b}*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。(略) 则不包含子串aba的{a,b}*上的字符串集合L是L'的非。 根据正则集的性质，L也是正则集。
4．对下列文法的生成式，找出其正则式
(1)
Sf aA S — B Af abS A — bB Bfb B fcC CfD DfbB Dfd
G=({SAB,C,D},{a,b,c,d},P,S), 生成式 P如下：
(2)
SfaA S fB AfcC A fbB BfbB B fa Cf D C f abB Dfd
G=({SAB,C,D},{a,b,c,d},P,S), 生成式 P如下：
答： (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+ (2) 由生成式得：
S=aA+B ① A=bB+cC② B=a+bB ③ C=D+abB④ D=dB ⑤
⑥
& )(cb)*(cd+b)
由③得 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+acaba+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 f aS S f bS S
(2) 右线性文法 G=({S},{a,b},P,S)
P: S f aS S f bS S f abb (3) 此正则集为{ba*}
右线性文法 G=({S,A},{a,b},P,S)
P: S f bA A f aA A f£
(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 f aS/bS/aaA/bbB A f aA/bA/bbC Bf aB/bB/aaC Cf aC/bC/ &
7.设正则集为a(ba)* (1)
构造右线性文法
⑵找出(1)中文法的有限自b动机
答：(1)右线性文法 G=({S,A},{a,b},P,S)
P: S f aA A f bS A f& (2) 自动机如下：
(p2是终结状态) 9.
对应图(a) (b)的状态转换图写出正则式。(图略) (1)
由图可矢廿 qo=aqo+bq1+a+&
q 1=aq2+bq1 q o=aqo+bq+a
=>q1 =abq1+bq1 +aaqo+aa
=(b+ab) q 1+aaqo+aa =(b+ab) *( aaq 0+aa)
=>q0=aqo+b(b+ab) *( aaq o+aa ) +a+ &
=q 0(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) qo=aq1+bq2+a+b
q1=aqo+bq2+b qo=aq1+bqo+a
=>q1 =aqo+baq1+bbqo+ba+b
=(ba)*(aq 0 +bbq o+ba+b) =>q2=aaqo+abq2+bqo+ab+a
=(ab)*(aaq 0 +bq 0+ ab+a)
=>qo=a(ba)*(a+bb) q 0 + a(ba)*(ba+b)+b(ab)*(aa+b)q
0
+ 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) (2) (3)
含有3个连续b的所有字符串集合 以aa为首的所有字符串集合 以aa结尾的所有字符串集合
a qo q1 q2 q3 qo qo qo q3 b q1 q2 q3 q3 答：(1) M=({qo,q i q 2,q 3},{a,b}, o ,qo,{q 3}),其中①如下:
(2) M=({qo,qq },{a,b}, o ,q o,{q 2}),其中o如下:
a qo q1 q2 (3) M=({qo,q i q2 },{a,b}, o ,q o,{q 2}),其中 o如下:
a q。 q1 q2 q1 q2 q2 b q。 q。 qo q1 q2 q2 b ① ① q2
14构造DFA Mi等价于NFA M, NFA M如下：
(1)
M=({qo,q 1 q2,q3},{a,b}, o ,qo,{q 3}),其中 o如下：
o (qo,a)={q o,q 1} o (q o,b)={q o} o (q1,a)={q 2} o (q1,b)= {q 2 } o (q2,a)={q 3} o (q2,b)= o (q3,a)={q 3} o (q3,b)= {q 3 }
(2)
M=({qo,q 1 q 2,q 3},{a,b}, o ,qo,{ q 1,q 2}),其中 o如下：
①
o (qo,a)={q 1,q2} o (q o,b)={q 1}
o (q1,a)={q 2} o (q1,b)= {q 14} o (q2,a)={q 3} o (q2,b)= {q o} o (q3,a)= ① o (q3,b)= {q o}
答：(1) DFA M={Q, {a,b}, o 1, [q 其中 Q ={[q
q3],[ q o,q 3]}
o
o
],{ [q
o
,q 1,q 3] , [q o,q 2,q 3] , [q o, q 1,q 2,q 3]}
q2,q 3],[ qo,q
1
],[q o,q 1], [q o,q 1,q 2],[ qo,q 2],[ qo,q 1, , q3],[ qo,q 2,
o 1满足
a [q o] [qo,q1] [qo,q1,q 2] b [q o] [q o,q 2] [q o,q1] [q 0,q 1,q2] [q 0,q 2] [q 0,q 1, q 2加 [q 0,q 1, q 3] [q 0,q 2, q 3]
[q 0,q1, q 2,q3] [q 0,q1, q 3] [q 0,q 1, q 2皿] [q 0,q 1, q 2心] [q 0,q1, q 3] [q 0,q1, q 3] M={Qi,
i
[q 0,q 2] [q 0] [q 0,q 2, q 3] [q 0,q 2, q 3] [q 0,q 3] [q 0,q 3] [q 0,q 3] 2
3
(
[qi,q
) DFA
{a,b},
2
© 1, [q。],{ [q i],[q 3],
],[q o,qi,q2],[q ,q2] ,[q i,q
2
2
,q3],[q
o
,q 3]}
i
其中 Q ={[q o],[q i,q3], [q i],[q © 1满足
],[ q ,q i,q2],[q ,q 2],[q 3], [q i,q2,q
3
],[q 2,q3]}
a [q 0] [q 1,q3] [q 1] [q 2] [q 0,q1,q2] [q 1,q2] [q 3] [q1,q 2,q3] [q 2,q 3] 15. 15.对下面矩阵表示的& -NFA
[q 1,q3] [q2] [q2] [q3] [q 1,q2,q 3] [q2,q3] — b [q 1] [q 0,q1,q2] [q 1,q 2] 「 [q 0,q1,q2] [q 0,q1,q2] [q 0] [q 0,q1,q2] [q 0] ① [q2,q3] [q3]
£ a {p} {q} {r} 3的串
b {q} {r} c {r} P（起始状态）— q r（终止状态） 0 {P} {q} 0(1) 给出该自动机接收的所有长度为 (2) 将此£ -NFA转换为没有&的NFA
{p} 0答：(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}, 因为& -closure(p)= ①
则设不含&的 NFA M=({p,q,r},{a,b,c}, ©1(p,a)= © (p,a)= ©1(P,b)= © (p,b)= © 1(P,C)= © (p,c)= ©1(q,a)= © (q,a)= ©1(q,b)= © (q,b)= ©1(q,c)= © (q,c)= © 1(r,a)= © (r,a)= © 1(r,b)= © (r,b)= © 1(r,c)= © (r,c)=
© ,p,r)其中© 如表格所示。
© 1,p,r)
£ ),a))={p} £ ),b))={p,q} £ ),c))={p,q,r} £ ),a))={p,q} £ ),b))={p,q,r} £ ),c))={p,q,r} £ ),a))={p,q,r} £ ),b))={p,q,r} £ ),c))={p,q,r}
£ -closure( ©( © (p, £ -closure( ©( © (p, £ -closure( ©( © (p, £ -closure( ©( © (q, £ -closure( ©( © (q, £ -closure( ©( © (q, £ -closure( ©( © (r, £ -closure( ©( © (r, £ -closure( ©( © (r,
图示如下： (r 为终止状态）
16.
设 NFA M=({q o,q i},{a,b},
© (qo,a)={q o,q 1} o (q o,b)={q 1} o (qi,a)=
o ,qo,{qi}),其中厅如下：
① o (qi,b)= {q 0, q 1}
构造相应的DFA M1,并进行化简 答：构造一个相应的
DFA M1={Q1, {a,b}, o 1, [q o],{ [q
1
] , [qo,q(|}
其中 Q ={[q 0] , [q1], [qo,q1]}
o 1满足
a [q 0] [q 1] [q 0,q1] [q0,q1] b [q 1] [q 0,q1] [q 0,q 1] ① [q0,q1]
由于该DFA已是最简，故不用化简
17. 使用泵浦引理，证明下列集合不是正则集：
(1) (2) (3) (4)
由文法G的生成式S- aSbS/c产生的语言L(G)
{ 3 /
k k
{a,b}*且3有相同个数的 a和b}
{aca/k > 1} { 33 /
{a,b}*}
证明：(1)在L(G)中，a的个数与b的个数相等 假设L(G)是正则集，对于足够大的 k取3 = a k (cb) kc 令
3 = 3 1 3 0 3 2
因为| 3 o|>O | 3 1 3 o| W k 存在 3 0使 3 1 3 0 3 2 € L
所以对于任意3 0只能取3 0=an n € (0,k) 则 3 13 J 3 2= akn(an)i(cb) kc 在 i 不等于 0 时不属于 L 与
-
假设矛盾。则L(G)不是正则集 (2)
akbk 令3 = 3 1 3 0 3 2
假设该集合是正则集，对于足够大的 k取3 =
因为| 3 o|>O |
3 1 3 o| W k 存在 3 0使 3 1 3 0 3 2 € L
所以对于任意3 0只能取3 0=an n € (0,k) 则3 13 0 3 2= akn(an)ibk在i不等于0时a与b的个数
-
不同，不属于该集合 与假设矛盾。则该集合不是正则集 (3)
akcak
假设该集合是正则集，对于足够大的 k取3 =
令 3 = 3 13 0 CO 2
因为| 3 o|>O | 3 1 3 o| W k 存在 3 0使 3 1 3 0 3 2 € L 所以对于任意3 o只能取3 o=an n € (0,k)
则3 13 oi3 2= akn(an)icak在i不等于0时c前后a的个数不同，不属于该集合 与假设矛盾。则该集
-
合不是正则集
(4)假设该集合是正则集，对于足够大的 令3 3 = 3 1 3 03 2
因为 | 3 o|>O | 3 1 3 o| W k 存在 3 0使 3 1 3 0 3 2 € L
所以对于任意3 o只能取3 o=an n € (0,k) 则3 13 oi 3 2= akn(an)ibakb 在i不等于0时不满足3 3
-
k取33 = ak bakb
的形式，不属于该集合 与假设矛盾。则该集合不是正则集
18. 构造米兰机和摩尔机
对于{a,b}*的字符串，如果输入以 bab结尾，则输出1;如果输入以bba结尾，则 输出2；否则输出
3。
答：米兰机：
说明状态qaa表示到这个状态时，输入的字符串是以
aa结尾。其他同理。
摩尔机，状态说明同米兰机
a
b a b
b
第四章
10.把下列文法变换为无&生成式、无单生成式和没有无用符号的等价文法:
S f A | A 2 , A i f A | A 4 , A 2 f A | A 5 , A 3 f S | b |
& , A 4 f S | a , A f S
I d |
&
N' = { S, A 1,A2,A3,A4,A5 }
G = ( { S i,S, A I,A2,A3,A4,A5 } , { a,b,d }, P 1 , S 1 ),其中生成式 P 如下： Si f£ | S , 解：⑴ 由算法3,变换为无&生成式：
S f A1 | A 2 , A1 f A3 | A 4 , A2 f A4 | A 5 , A3 f S | b , A4 f S | a , A5 f S | d ,
⑵ 由算法 4,消单生成式：
NS1 = { S 1,S,A 1,A2,A3,A4, A 5 } ,
NS = N A1 = N A2 = N A3 = N A4 = N A5 = { S, A 1,A2,A3,A4, A 5 } ,
运用算法4,则Pi变为：
Si fa | b | d| £
,
S fa | b | d , A1 f a | b | d , A2 f a | b | d , A3 f a | b | d , A4 f a | b | d , A5 f a | b | d
⑶ 由算法 1 和算法 2,消除无用符号,得到符合题目要求的等价文法：
G = ( { S 1 } , { a,b,d } , P 1 , S 1 )，其中生成式 Pi为：S f a | b | d |
&・
11・ 设2型文法 G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) ,
S f ASB I & ; A f aAS | a ; B f SBS | A | bb
试将G变换为无&生成式
，无单生成式，没有无用符号的文法
Chomsky范式・
解：⑴ 由算法3,变换为无&生成式：
N' = { S }
由 S f ASBW出 S f ASB | AB , 由 A f aAS得出 A f aAS | aA , 由 B f SBS得出 B f SBS | SB | BS |B, 由 S€ N'得出 S f£ | S ,
因此无&的等效文法 G = ( { S 1,S,A,B } , { a,b,d } , P 成式 P1 如下：
Si f£ | S , S f ASB I AB , A f aAS I aA I a,
B fSBS I SB I BS I BI A I bb ,
其中 P：
，再将其转换为1
, S 1 ),其中生
⑵ 由算法 4,消单生成式：
NS1 = { S 1,S } , N S = { S } , N
A
= { A } , N B = { A,B }
由于S f ASB | AB € P且不是单生成式,故Pl中有S | ASB | AB , 同理有 S f ASB | AB , A f aAS | aA | a , B f SBS | SB | BS | aAS | aA
| a | bb,
因此生成的无单生成式等效文法为
G = ( { S i,S, A,B } , { a,b } , P S f£ | ASB | AB , S f ASB | AB , A f aAS | aA | a ,
B fSBS | SB | BS | aAS | aA | a | bb,
1
, S 1 ),其中生成式 Pi如下：
⑶ 由算法 1 和算法 2，消除无用符号 ( 此题没有无用符号 ); ⑷转化为等价的Chomsky范式的文法：
将 Si f ASB变换为 S f AC , C f SB , 将S f ASB变换为S f AC ,
将 A f aAS | aA 变换为 A f ED | EA, D f AS , E f a,
将 B f SBS | aAS | aA | a | bb , 变换为 B f CS | ED | EA | FF, F f b , ⑸ 由此得出符合题目要求的等价文法：
G = ( { S i,S, A,B,C,D } , { a,b } , P S f£ | AC | AB , S f AC | AB , A fED | EA | a ,
B fCS | SB | BS | ED | EA | a | FF , C fSB , D f AS , E fa , F fb .
i5. 将下列文法变换为等价的 Greibach 范式文法 ：
i
, S i ),其中生成式 P 如下：
⑴ S fDD | a , D fSS | b
解： 将非终结符排序为 S,D,S 为低位 ,D 为高位,
⑴ 对于 D f SS ,用 S f DD | a 代入得 D f DDS | aS | b , 用引理变化为 D faS | b | aSD' | bD' , D ' fDS
| DSD' ,
⑵ 将D生成式代入 S生成式得S f aSD | bD | aSD ' D | bD'D | a , ⑶将D生成式代入D'生成式得
D' faSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' , ⑷ 由此得出等价的 Greibach
范式文法：
G = ( { S,D,D ' } , { a,b } , P i , S ), S faSD | bD | aSD ' D | bD'D | a , D faS | b | aSD' | bD' ,
D' faSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' .
其中生成式 Pi如下:
⑵ Ai f A3b | A 2a , A 2 f Aib | A 2A2a | b , A 3 f Aia | A 3A3b | a 解：⑴转化为等价的Chomsky范式
的文法：
Ai f A3A4 | A 2A5 , A2 fA1A4 | A
2
A6 | b ,
A3 fA1A5 | A A4 fb , A5 fa , A6 fA2A5 , A7 fA3A4 ,
3
A7 | a ,
⑵转 化为等价的 Greibach 范式的文法
将非终结符排序为 A, A 2,A3,A4,A5 ,A 1为低位A为高位,
① 对于 A f A1A4 ,用 Al f A3A4 | A 2A5代入得 A f A3A4A4 | A 2 A4 | A 2A | b , 用引理变化为
A2 f A3A4A4 | b | A
3
A4A4A2' | bA 2' ,
A2' fA5A4A2' | A 6A2' | A 5A4 | A 6 ,
② 对于 A f AA ,用 Ai f A3A | A 2A5 代入得 A f A3A4A5 | A 2A5A5 | A 4 | a , A生成式右边第一个字符仍是较低位的非终结符
A3 fb A5A5 | bA 2'A5A5 | a | b A
，将A生成式代入A生成式得
A3 fA3A4 A 5 | A 3A4A4 A 5A5 | b A 5A5 | A 3A4A4A2' A5A5 | bA 2' A5A5 | A 3A7 | a , 用引理变化为
5
A5A3' | bA 2'A5A5A3' | aA 3' ,
A3' fA4A5 | A4A4A5A5| A4A4A2'A5A5| A7 | A4A5A3'| A4A4A5A5A3' | A4A4A2'A5A5A3' | A 7A3' ,
③ 对于A f A2A5，将A2生成式代入A生成式得
A6 f A3A4A4A5 | bA 5 | A 3A4A4A2'A5 | bA 2'A5 ,
A生成式右边第一个字符仍是较低位的非终结符 ，将A生成式代入A6生成式得
A6 f 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 | b A5 ,
④ 对于A f AA ,将A生成式代入A生成式得
A7 fb A5A5A4 | bA 2'A5A5A4 | a A 4 | b A 5A5A3'A4 | bA 2'A5A5A3'A4 | aA 3'A4 ,
⑤ 将A,A6生成式代入A2‘生成式得
A2' A2'
f aA4A2' | bA5A5A4A4A5A2' | bA2'A5A5A4A4A5A2' | bA 2 ' A5 A5A3 ' A4A4A5A2 '
| aA 3'A4A4A5A2'
| bA 2'A5A2'
|
| aA4A4A2' A5A2'
| aA4A4A5A2' | bA 5A5A4A4A2' A5
| |
bA5A5A3'A4A4A5A2'
| bA2 ' A5A5A4A4A2 ' A5A2 ' | bA5A5A3 ' A4A4A2 ' A5A2 '
| b A 5A2' aA4A4A2'A5
bA2 ' A5A5A3 ' A4A4A2 ' A5A2 ' | aA 3 ' A4A4A2 ' A5A2 '
|
| aA 4
aA3'|
| b A 5A5A4A4A5 | bA 2' A5A5A4A4A5 | aA 4A4A5 | bA 5A5A3' A4A4A5 | bA 2' A5A5A3' A4A4A5 |
A4A4A5 | 生成式得
bA5A5A4A4A2'A5 bA2'A5A5A4A4A2'A5
bA5A5A3' A4A4A2' A5 | bA2' A5A5A3' A4A4A2' A5 | aA3'A4A4A2'A5 | bA2'A5 | b A5 , 将A4,A7生成式代入A3'A3'faA5 | aA 4A5A5 | aA 4A2'A5A5 | aA 5A3'
| aA 4A5A5A3 '
A3'
|
| aA 4A2 ' A5A5A3 ' |
bA2'A5A5A4A3'A3' |
b A5A5A4 | bA2'A5A5A4 | aA4 | bA5A5A3' A4 | bA2' A5A5A3' A4 | aA3'A4 | bA5A5A4A3' |
| a A4A3'
,
| b
A5A5A3' A4 bA2' A5A5A3' A4
aA3' A4A3'
⑶ 由此得出等价的 Greibach 范式文法 :
G = ( { S,D,D ' } , { a,b } , P 1 , S ), A1 fA3A4 | A 2A5 , A2 f A3A4A4 | b | A
3
其中生成式 Pi如下：
A4A4A2 ' | bA 2' ,
A — b A5A5 | bA 2' A5A5 | a | bA 5AA3' | bA 2'氏氏A' | aA 3', A — b , A — a ,
A — bAAsAAA | bA' AA5氏AA | aAA4 | bAAA' A4AA5 | bA' AAA' AAA | aA' A4A4A5 |
bAsAAAA' A |
bA'
AAAAA' A |
aA4AA' A |
bAAsA/ A4AA2' A | bA' AAA' AAA2'
AAA | a A 4 |
| bAAAAAsA'
A |
aA' AAA/ A | bA' A5 | | aQAA'
b 氏，
|
A — b A5A5A4 | bA 2' A' — aAA2‘
b A 5AA3' A | bA 2' AAA' | bA' AAAAAA'
A | aA 3' A ,
bAAA/ AAAA2' | bA 2' AAA^' AA4A5A2' | aA 3' AAAA' | bA 5A5AAA' A A' | bA?' AAAAA AA | aAAA?' AA | bAAA' AAA2' A5A2' | bA' AAA' AAA AA' | aA 3' AAA' AA' | bA 2' AA |
bA 5A2' | aA 4 | b A 5A5A4A1A5 | bA 2' A5A5A4A4A5 | aA 4A | bA 5A5A3' AA^A | bA 2' AsAsAs' AAA | aA' AAAs | bAsAAAA' A | bA' AAAAA' A | aAAA' A | bAAA' A4AA2' A | bA' AAA' AAA2'
A | aA' AAA/ A | bA' As | b As , A'
— aAs | aA 4A5A5 | aA 4A2' AA | aA sA'
| aA 4AA5A3' | aA 4A2' AA5A3' |
b AsAA| bA' AAA I aA | bAAA' A| bA' AAA' A| aA' A| bAsAAA' | bA 2' AsAAA' A 4 A3' | b A sAsA' A A3' | bA 2' AsAA' A A3' aA' AA'.
20.设文法G有如下得生成式：S — aDD , D — aS | bS | a ,
构造等价的下推自动机
解：根据P162-163的算法,构造下推自动机 M,使M按文法G的最左推导方式工作•
设 M = (Q,T,
r , 3 ,q
0,Z°,F ),其中
Q = { q
0,q f },
T = { a,b},
r
= { a,b,D,S },
Z = S ,
F = { q
f
},
3
定义如下:
3
( q 0, & ,S ) = { ( q 0
, aDD ) },
3 ( q 0, & ,D ) = { ( q 0
,aS ) , ( q
0
,bS ) , ( q
0
,a ) },
3 ( q 0,a,a ) = { ( q 0,
£
) },
3 ( q 0, &, & ) = { ( q
£
) } •
f
,
21.给出产生语言
1
r
i」k
文法•你给出的文法是否具有二义性L = { a b c
I i , j , k
> 0 且 i = j 或者j = k } 的上下文无关
？为什么？ 解：G=({SAB,C,D,E},{a,b,c}
，P, S)
P: S — AD |EB, A — aAb | & , B — bBc | & , D — cD | £ , E — aE | & 文法具有二义性。因为当句子宀中a,b,c个数相同时，对于3存在两个不同的最左
(右)推导。
如 abc L ,存在两个不 同的最左推导 S AD aAbD abD abcC abc及 S EB aEB aB abBc abc。
22.设下推自动机 M = ( {q 0,q 1},{a,b},{Z
°
,X}, S , q 0, Z 0, 0 ),其中 3 如下：
3 (q 0,b, Z 0) = {(q 0, XZ 0)} , 3 (q 0, & , Z 0) = {(q 0, & )} ,A
3 (qo,b, X) = {(q o, XX)} , S (q i,b, X) = {(q
1
,
& )},
S (qo,b, X) = {(q i, X)} ,
3 (q i,a, Z o) = {(q o, Z 0)},
试构造文法G产生的语言L (G) = L(M). 解：在 G 中,N = { [qo,Zo,qo],
[qo,Zo,q<|, [qo,X,q。], [q o,X,q 1], [q i,Zo,q o], [q i,Zo,q 1],
[q 1,X,q o], [q 1,X,q 1] } .
⑴ S 生成式有
S f [q o,Z o,q o],
| a |
S f [q o,Z o,q 1],
根据 S (q o,b, Z o) = {(q o, XZ o)},则有
[qo,Zo,qo] fb[qo,X,q o] [q o,Zo,qo] , [qo,Zo,qo] fb[qo,X,q 1] [q 1,Zo,qo] , [qo,Zo,q1] fb[qo,X,q o] [q o,Zo,q1] ,
[qo,Zo,q1] fb[qo,X,q 1] [q 1,Zo,q1] , 因为有 S (q o,b, X) = {(q [q o,X,q o] fb[q o,X,q o] [q o,X,q o] , [qo, X,q [qo, X,q [qo, X,q
o
o
, XX)},则有
fb[qo,X,q 1] fb[qo,X,q 1] fb[qo,X,q
]
1
1
] [q 1, X,q ] [q o, X,q ] [q 1, X,q
o11
] , ] , ] ,
o1
因为有 S (q o,a, X) = {(q
[q o,X,q o] fa[q 1,X,q o] ,
, X)},则有
[q o,X,q 1] fa[q 1,X,q 1] , 因为有 S (q 1,a, Z o) = {(q o, Z o)},则有 [q1,Zo,qo] fa[qo,Zo,qo] ,
[q1,Zo,q1] fa[qo,Zo,q1] , 因为有 S (q o, & , Z o) = {(q o, [q o,Z o,q o] f£ ,
& )},则有
因为有 S (q1,b, X) = {(q
[q 1,X,q 1] fe
1
, & )},则有
⑵ 利用算法 1 和算法 2, 消除无用符号后 , 得出文法 G 产生的语言 L(G) = { N,T,P,S }
其中 N = { S,[q
式 P 如下 ：
S f[qo,Zo,qo] ,
[qo,Zo,qo] fb[qo,X,q 1] [q 1,Zo,qo] , [qo, X,q 1] fb[qo,X,q 1] [q 1, X,q 1] , [q o,X,q 1] fa[q 1,X,q 1] , [q1,Zo,qo] fa[qo,Zo,qo] , [q o,Z o,q o] fe , [q o,Z o,q o] fe .
o
,Zo,qo],[q 1,Zo,qo],[q 1,X,q 1], [q
o
,X,q 1] },T = { a,b }, 生成
23. 证明下列语言不是上下文无关语言 ：
⑴{ a nbncm | m < n };
证明： 假设L是上下文无关语言，由泵浦引理，取常数p,当L且| 3 | > p时,可取
3 = a PbC ,将3写为3 =3 1 3 23 03 3 3 4 ,同时满足 | 3 2 3 03 3| < p
|3|W
(1)
3 2和3 3不可能同时分别包含 a和C,因为在这种情况下，有| 3 23 03 3|>p；
⑵ 如果3 2和3 3都只包含a (b),即3 2303 3 = a j (b j ) (j 如果3 2和3 3都只包含C ,即3 2 3 0 3 3 = c j (j W p),当i大于1时，3 1 3 2 3 03 3i 3冲会出现 c的个数大于a的个数(b的个数); ⑶ 如果3 2和3 3分别包含 a 和 b (b 和 C) , 当 i=0 时 3 13 2i3 03 3i3 4中会出 现 a, b 的个数小于 c 的个数(或 a,b 个数不等) 这些与假设矛盾 , 故 L 不是上下文无关语言 . ⑵ { a k | k 是质数 }; 证明： 假设L是上下文无关语言，由泵浦引理，取常数p,当3€ L且| 3 | > p时,可取3 =ak ( k 》p 且 k 工 1 ), 将3与为3 = 3 1 3 2 3 0 3 3 3 4 , 同时满足 | 3 23 03 3| W p , 且 | 3 2 3 3|=j > 1 ,则当 i=k+1 时,| 3 1 3 2i 3 0 3 3i 3 4〔=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j) 至少 包含因子k且k工1 ,因此必定不是质数，即3 13 2i 3 03 3 3 4 不属于 L. 这与假设矛盾 , 故 L 不是上下文无关语言 . ⑶ 由 a,b,c 组成的字符串且是含有 a,b,c 的个数相同的所有字符串 证明 ： 假设L是上下文无关语言，由泵浦引理，取常数p,当3€ L且| 3 | > p时,可取 3 = a b c (k > p),将 3 写为 3 =3 1 3 23 0 3 3 3 41 3 ,同时满足 | 3 23 0 3 3| W p 2和3 3不可能同时分别包含 a 和 c, 因为在这种情况下 , 有| 3 23 03 3|>p; ⑵ 如果3 2和3 3都只包含a (b或c),即3 23 0 3 3 = a j (b j或cj ) (j < p), 则当i工1时，3 1 3 2i3 0 3 3i 3 4中会出现a,b,c的个数不再相等； ⑶ 如果3 2和3 3分别包含 a 和 b (b 和 c) , 3 132i3 03 3i3 4中会出现 a,b 的 个数与 c 的不等; 这些与假设矛盾 , 故 L 不是上下文无关语言 . 24.设G是Chomsky范式文法,存在L (G)，求在边缘为3的推导树中,最长的路 径长度与3的长度之间的 解： 设边缘为3的推导树中 , 最长路径长度为 n, 则它与3的长度之间的关系为 关系 . n-1 因为由Chomsky范式的定义可知，Chomsky范式文法的推导树都是二叉树,在最长路 径长度为n的二叉推导树中,满二叉树推出的句子长度最长,为2n-1,因此3的长度与 其推导树的最长路径长度 n 的关系可以用上式表示 . 25.设计PDA接受下列语言(注意：不要求为确定的) 1 { 0 m1n | m W n }; 解：设 PDA M = ( Q,T, r , S ,q0,Z°,F ),其中 Q = { q 0,q 1,q f } , T = { 0,1} , r = { 0,1, Z 0 }, F = { q f } , S定义如下： S ( q 0, £ , Z 0) = { ( q 1, Z 0 ) }, 3 ( q 0,0, Z o) = { ( q S ( q 0,0,0 ) = { ( q o, 00 ) }, o , 0Z o ) }, 3 ( q 0,1, Z 0 ) = { ( q S ( q 0,1,0 ) = { ( q S ( q 1,1,0 ) = { ( q f , & ) }, i , e ) }, , e ) }, , e ) } ,e ) } i S ( q 1, e , Z 0 ) = { ( q S( q 1,1, Z 0 ) = { ( q S( q f,1, f f e ) = { ( q f,e ) } (2) { 0 m1n | m > n }; 解： 设 PDA M = ( Q,T, r , S ,q0,Z°,F ),其中 Q = { q 0,q 1,q f } , T = { 0,1} , r = { 0,1, Z 0 }, F = { q f } , S ( q 0, e , Z 0 ) = { ( q S ( q 0,0, Z 0 ) = { ( q S( q 0,0,0 ) = { ( q S ( q 0,1, 0 ) = { ( q S( q 1,1, 0 ) = { ( q S( q 1, e ,Z0 ) = { ( q S( q 1, e ,0 ) = { ( q S( q f,1, e ) = { ( q 100 , Z 0 ) } , , 0Z 0 ) } , , e ) } , , e ) } , , 00 ) } , 11f , e ) } , , e ) } , e ) } ff ⑶{ 0 m1n0m | n和m任意}; 解：设 PDA M = ( Q,T, r , S ,q°,Z°,F ),其中 Q = { q 0,q 1, q 2,q 3,qf } , T = { 0,1} , r = { 0,1, Z 0 }, F = { q f } , S定义如下： S( q 0,0, Z 0 ) = { ( q S( q S( q S( q S( q S( q S( q S( q S( q S( q S( q 00 00 , 0Z 0 ) } , 0 ,0,0 ) = { ( q ,1, Z 0 ) = { ( q , 00 ),( q 3 , e )} , , e ) } , e ) = { (q 3, e ) } , 3, e , e ) = { ( q f, e ) } , 3,1, 011220 ,1,0 ) = { ( q ,1,0 ) = { ( q ,0,0 ) = { ( q ,0,0 ) = { ( q , e , Z 0 1122 ,0 ) } , ,0 ) } , , e ) } , , e ) } , ff ) = { ( q , e ) } , , e )}nm , e , Z 0 ) = { ( q 第五章 1.考虑如下的图灵机 M = ( {q 0 , q i, q f, },{0,1},{0,1,B}, S , q o,B,{ q f }),其中 3定义为： S (qo,O) = {(q i ,1,R)} , S (qi,1) = {(q 0 ,O,R)} , S (q i,B) = {(q f,B,R)}, 非形式化但准确地描述该图灵机的工作过程及其所接受的语言 解：开始时,M的带上从左端起放有字符串 0(10)，(i >0),后跟无限多个空白符的第一次 动作先读到第一个0,并改写为1;然后右移，如果找到第一个1,则改写为0,并继续 向右寻找下一个 0,这样重复进行.当向右寻找1的时候，找到一个空白符B,则结束. 该图灵机所接受的语言 L(M) = { 0(10) i | i > 因篇幅问题不能全部显示，请点此查看更多更全内容