形式语言与自动机课后习题答案
第二章
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)[
(4)S→a S→aE E→aS
答:(1)b(ab)n /n≥0}或者L={(ba)n b/n≥0}
(2) L={a n cb n /n≥0}
(3)L={a2n+1 /n≥0}
第三章
1.下列集合是否为正则集,若是正则集写出其正则式。
(1)含有偶数个a和奇数个b的{a,b}*上的字符串集合(2)含有相同个数a和b的字符串集合
(3)`
(4)不含子串aba的{a,b}*上的字符串集合
答:(1)是正则集,自动机如下
b b b b
》
(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的字符串的集合
(5)含有两个相继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):
(3)找出(1)中文法的有限自b动机
答:(1)右线性文法G=({S,A},{a,b},P,S)
P: S→aA A→bS A→ε
(2)自动机如下:
(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) *
(4)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}),其中σ如下:
(2)M=({q0,q1 q2 },{a,b},σ,q0,{q2}),其中σ如下:
(3)M=({q0,q1 q2 },{a,b},σ,q0,{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满足
(2)DFA 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满足
15. 15.对下面矩阵表示的ε-NFA (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)= Φ
则设不含ε的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 为终止状态)
a,b,c
?
a,b,c
16.设NFA M=({q 0,q 1},{a,b},σ,q 0,{q 1}),其中σ如下:
σ(q 0,a)={q 0,q 1} σ(q 0,b)={q 1}
;
σ(q 1,a)= Φ σ(q 1,b)= {q 0, q 1}
构造相应的DFA M 1,并进行化简
答:构造一个相应的DFA M 1={Q 1, {a,b},σ1, [q 0],{ [q 1],[q 0,q 1]}
其中Q 1 ={[q 0],[q 1],[q 0,q 1]} σ1满足 由于该DFA 已是最简,故不用化简
17.使用泵浦引理,证明下列集合不是正则集: (1) 、
(2)
由文法G 的生成式S →aSbS/c 产生的语言L(G)
(3) {ω/ω∈{a,b}*且ω有相同个数的a 和b} (4) {a k ca k /k ≥1} (5) {ωω/ω∈{a,b}*}
证明:(1)在L(G)中,a 的个数与b 的个数相等
假设L(G)是正则集,对于足够大的k 取ω= a k (cb)k c 令ω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0i ω2∈L 所以对于任意ω0只能取ω0=a n n ∈(0,k)
则ω1ω0iω2= a k–n(a n)i(cb)k c 在i不等于0时不属于L
,
与假设矛盾。则L(G)不是正则集
(2)假设该集合是正则集,对于足够大的k取ω= a k b k
令ω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
所以对于任意ω0只能取ω0=a n n∈(0,k)
则ω1ω0iω2= a k–n(a n)i b k在i不等于0时a与b的个数不同,不属于该集合与假设矛盾。则该集合不是正则集
(3)假设该集合是正则集,对于足够大的k取ω= a k ca k
令ω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
¥
所以对于任意ω0只能取ω0=a n n∈(0,k)
则ω1ω0iω2= a k–n(a n)i ca k在i不等于0时c前后a的个数不同,不属于该集合
与假设矛盾。则该集合不是正则集
(4)假设该集合是正则集,对于足够大的k取ωω= a k ba k b
令ωω=ω1ω0ω2
因为|ω0|>0 |ω1ω0|≤k 存在ω0使ω1ω0iω2∈L
所以对于任意ω0只能取ω0=a n n∈(0,k)
则ω1ω0iω2= a k–n(a n)i ba k b 在i不等于0时不满足ωω的形式,不属于该集合
与假设矛盾。则该集合不是正则集
》
18.构造米兰机和摩尔机
对于{a,b}*的字符串,如果输入以bab结尾,则输出1;如果输入以bba结尾,则输出2;否则输出3。
答:米兰机:
说明状态qaa表示到这个状态时,输入的字符串是以aa结尾。其他同理。
b/3
:
摩尔机,状态说明同米兰机。
a a
b a
。
a b a b
:
a b b
第四章
10. 把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法:
S →A 1 | A 2 , A 1 →A 3 | A 4 , A 2 →A 4 | A 5 , A 3 →S | b |ε, A 4 →S | a ,A 5 →S | d |ε
解: ⑴ 由算法3,变换为无ε生成式:
N ’ = { S, A 1,A 2,A 3,A 4,A 5 }
G 1 = ( { S 1,S, A 1,A 2,A 3,A 4,A 5 } , { a,b,d }, P 1 , S 1 ) ,其中生成式P 1如下:
、
S 1 →ε| S , S →A 1 | A 2 ,
A 1 →A 3 | A 4 , A 2 →A 4 | A 5 , A 3 →S | b , A 4 →S | a , A 5 →S | d ,
⑵ 由算法4,消单生成式:
N S1 = { S 1,S,A 1,A 2,A 3,A 4, A 5 } ,
N S = N A1 = N A2 = N A3 = N A4 = N A5 = { S, A 1,A 2,A 3,A 4, A 5 } ,
'
运用算法4,则P 1变为: S1 →a | b | d |ε , S →a | b | d , A 1 →a | b | d , A 2 →a | b | d , A 3 →a | b | d ,
qaa,3 qbba,2
qbb,3 qbab,1
qaba,3
qaab,3
A4→a | b | d ,
A5→a | b | d
⑶由算法1和算法2,消除无用符号,得到符合题目要求的等价文法:
G1 = ( { S1 } , { a,b,d } , P1 , S1 ) ,其中生成式P1为:S1→a | b | d |ε.
(
11.设2型文法G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) , 其中P:
S →ASB |ε; A →aAS | a ; B →SBS | A | bb
试将G变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.
解: ⑴由算法3,变换为无ε生成式:
N’ = { S }
由S →ASB得出S →ASB | AB ,
由A →aAS得出A →aAS | aA ,
由B →SBS得出B →SBS | SB | BS |B,
由S∈N’得出S1→ε| S ,
~
因此无ε的等效文法G1 = ( { S1,S,A,B } , { a,b,d } , P1 , S1 ) ,其中生成式P1如下:
S1→ε| S ,
S →ASB | AB ,
A →aAS | aA | a,
B →SBS | SB | BS | B| A | bb ,
⑵由算法4,消单生成式:
N S1 = { S1,S } , N S = { S } , N A = { A } , N B = { A,B }
由于S →ASB | AB∈P且不是单生成式,故P1中有S1→ε| ASB | AB ,同理有S →ASB | AB , A →aAS | aA | a , B →SBS | SB | BS | aAS | aA | a | bb,
因此生成的无单生成式等效文法为
:
G1 = ( { S1,S, A,B } , { a,b } , P1 , S1 ) ,其中生成式P1如下:
S1→ε| ASB | AB ,
S →ASB | AB ,
A →aAS | aA | a ,
B →SBS | SB | BS | aAS | aA | a | bb,
⑶由算法1和算法2,消除无用符号(此题没有无用符号);
⑷转化为等价的Chomsky范式的文法:
将S1 →ASB变换为S →AC , C →SB ,
将S →ASB 变换为S →AC ,
将A →aAS | aA 变换为 A →ED | EA, D →AS , E →a,
>
将B →SBS | aAS | aA | a | bb , 变换为 B →CS | ED | EA | FF, F →b ,
⑸由此得出符合题目要求的等价文法:
G1 = ( { S1,S, A,B,C,D } , { a,b } , P1 , S1 ) ,其中生成式P1如下:
S1→ε| AC | AB ,
S →AC | AB ,
A →ED | EA | a ,
B →CS | SB | BS | ED | EA | a | FF ,
C →SB ,
D →AS ,
E →a ,
—
F →b .
15.将下列文法变换为等价的Greibach范式文法:
⑴S →DD | a , D →SS | b
解: 将非终结符排序为S,D,S为低位,D为高位,
⑴对于D →SS ,用S →DD | a 代入得D →DDS | aS | b ,
用引理变化为D →aS | b | aSD' | bD' , D’→DS | DSD’ ,
⑵将D生成式代入S生成式得S →aSD | bD | aSD’D | bD'D | a ,
⑶将D生成式代入D’生成式得
D’→aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' ,…
⑷由此得出等价的Greibach范式文法:
G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下:
S →aSD | bD | aSD’D | bD'D | a ,
D →aS | b | aSD' | bD' ,
D’→aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' .
⑵A1→A3b | A2a , A2→A1b | A2A2a | b , A3→A1a | A3A3b | a 解: ⑴转化为等价的Chomsky范式的文法:
A1→A3A4 | A2A5 ,
A2→A1A4 | A2A6 | b ,
?
A3→A1A5 | A3A7 | a ,
A4→b ,
A5→a ,
A6→A2A5 ,
A7→A3A4 ,
⑵转化为等价的Greibach范式的文法:
将非终结符排序为A1, A2,A3,A4,A5 ,A1为低位A5为高位,
①对于A2→A1A4,用A1→A3A4| A2A5代入得A2→A3A4A4| A2A5A4| A2A6 | b ,
用引理变化为
A2→A3A4A4 | b | A3A4A4A2’ | bA2’ ,
~
A2’→A5A4A2’ | A6A2’ | A5A4 | A6 ,
②对于A3→A1A5,用A1→A3A4| A2A5代入得A3→A3A4A5| A2A5A5| A3A7 | a ,
A3生成式右边第一个字符仍是较低位的非终结符,将A2生成式代入A3生成式得
A3→A3A4 A5 | A3A4A4 A5A5 | b A5A5 | A3A4A4A2’ A5A5 | bA2’A5A5 | A3A7 | a ,
用引理变化为
A3→b A5A5 | bA2’A5A5 | a | b A5A5A3’ | bA2’A5A5A3’ | aA3’ ,
A3’→A4A5| A4A4A5A5| A4A4A2’A5A5| A7| A4A5A3’| A4A4A5A5A3’| A4A4A2’A5A5A3’ | A7A3’ ,
③对于A6→A2A5 ,将A2生成式代入A6生成式得
A6→A3A4A4A5 | bA5 | A3A4A4A2’A5 | bA2’A5 ,
A6生成式右边第一个字符仍是较低位的非终结符,将A3生成式代入A6生成式得…
A6→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 ,
④对于A7→A3A4 , 将A3生成式代入A7生成式得
A7→b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 ,⑤将A5,A6生成式代入A2’生成式得
A2’→aA4A2’| bA5A5A4A4A5A2’| bA2’A5A5A4A4A5A2’| aA4A4A5A2’| bA5A5A3’A4A4A5A2’| bA2’A5A5A3’A4A4A5A2’| aA3’A4A4A5A2’| bA5A5A4A4A2’A5A2’| bA2’A5A5A4A4A2’A5A2’| aA4A4A2’A5A2’| bA5A5A3’A4A4A2’A5A2’| bA2’A5A5A3’A4A4A2’A5A2’| aA3’A4A4A2’A5A2’| bA2’A5A2’| b A5A2’| aA4| b A5A5A4A4A5| 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 ,
将A4,A7生成式代入A3’生成式得
A3’→aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b A5A5A4| bA2’A5A5A4| aA4| bA5A5A3’A4| bA2’A5A5A3’A4| aA3’A4 | bA5A5A4A3’ | bA2’A5A5A4A3’ | a A4A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ |
aA3’A4A3’ ,
⑶由此得出等价的Greibach范式文法:
G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下:
A1→A3A4 | A2A5 ,
:
A2→A3A4A4 | b | A3A4A4A2’ | bA2’ ,
A3→b A5A5 | bA2’A5A5 | a | bA5A5A3’ | bA2’A5A5A3’ | aA3’ ,
A4→b ,
A5→a ,
A6→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 ,
A7→b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 , A2’→aA4A2’| bA5A5A4A4A5A2’| bA2’A5A5A4A4A5A2’| aA4A4A5A2’| bA5A5A3’A4A4A5A2’| bA2’A5A5A3’A4A4A5A2’| aA3’A4A4A5A2’| bA5A5A4A4A2’A5A2’| bA2’A5A5A4A4A2’A5A2’| aA4A4A2’A5A2’| bA5A5A3’A4A4A2’A5A2’| bA2’A5A5A3’A4A4A2’A5A2’| aA3’A4A4A2’A5A2’| bA2’A5A2’| bA5A2’| aA4| b A5A5A4A4A5| 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 ,
A3’→aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b
A5A5A4| bA2’A5A5A4| aA4| bA5A5A3’A4| bA2’A5A5A3’A4| aA3’A4 |
bA5A5A4A3’ | bA2’A5A5A4A3’ | a A4 A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ |
aA3’A4A3’ .
20.设文法G有如下得生成式: S →aDD , D →aS | bS | a , 构造等价的下推自
动机.
]
解: 根据P162-163的算法,构造下推自动机M,使M按文法G的最左推导方式工作.
设M = (Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q f } ,
T = { a,b} ,
Г= { a,b,D,S } ,
Z0 = S ,
F = { q f } ,
δ定义如下:
δ( q0,ε,S) = { ( q0, aDD ) } ,
δ( q0,ε,D ) = { ( q0,aS ) , ( q0,bS ) , ( q0,a ) } ,
<
δ( q0,a,a ) = { ( q0,ε) } ,
δ( q0,ε,ε) = { ( q f,ε) } .
21.给出产生语言L = { a i b j c k | i , j , k≥0 且i = j 或者j = k }的上下文无关文法.
你给出的文法是否具有二义性为什么
解: G=({S,A,B,C,D,E},{a,b,c},P,S)
P:S →AD |EB, A →aAb |ε, B →bBc |ε, D →cD |ε, E →aE |ε文法具有二义性。
因为当句子ω中a,b,c个数相同时,对于ω存在两个不同的最左(右)推导。
如abc L,存在两个不同的最左推导S AD aAbD abD abcC abc 及S EB aEB aB abBc abc 。
22.,
23.设下推自动机M = ( {q0,q1},{a,b},{Z0,X},δ, q0, Z0,φ),其中δ如下:
δ(q0,b, Z0) = {(q0, XZ0)} ,δ(q0,ε, Z0) = {(q0, ε)} ,A
δ(q0,b, X) = {(q0, XX)} , δ(q1,b, X) = {(q1, ε)} ,
δ(q0,b, X) = {(q1, X)} , δ(q1,a, Z0) = {(q0, Z0)} ,
试构造文法G产生的语言L (G) = L(M).
解: 在G中,N = { [q0,Z0,q0], [q0,Z0,q1], [q0,X,q0], [q0,X,q1], [q1,Z0,q0], [q1,Z0,q1], [q1,X,q0], [q1,X,q1] } .⑴S生成式有
S →[q0,Z0,q0] ,
S →[q0,Z0,q1] ,
根据δ(q0,b, Z0) = {(q0, XZ0)} ,则有?
[q0,Z0,q0] →b[q0,X,q0] [q0,Z0,q0] ,
[q0,Z0,q0] →b[q0,X,q1] [q1,Z0,q0] ,
[q0,Z0,q1] →b[q0,X,q0] [q0,Z0,q1] ,
[q0,Z0,q1] →b[q0,X,q1] [q1,Z0,q1] ,因为有δ(q0,b, X) = {(q0, XX)},则有[q0,X,q0] →b[q0,X,q0] [q0,X,q0] ,
[q0, X,q0] →b[q0,X,q1] [q1, X,q0] ,
[q0, X,q1] →b[q0,X,q0] [q0, X,q1] ,
[q0, X,q1] →b[q0,X,q1] [q1, X,q1] ,因为有δ(q0,a, X) = {(q1, X)},则有,
[q0,X,q0] →a[q1,X,q0] ,
[q0,X,q1] →a[q1,X,q1] ,
因为有δ(q1,a, Z0) = {(q0, Z0)},则有[q1,Z0,q0] →a[q0,Z0,q0] ,
[q1,Z0,q1] →a[q0,Z0,q1] ,
因为有δ(q0,ε, Z0) = {(q0, ε)},则有
[q0,Z0,q0] →ε,
因为有δ(q1,b, X) = {(q1, ε)},则有
[q1,X,q1] →ε
⑵利用算法1和算法2,消除无用符号后,得出文法G产生的语言L(G) = { N,T,P,S }
*
其中N = { S,[q0,Z0,q0],[q1,Z0,q0],[q1,X,q1], [q0,X,q1] },T = { a,b },生成式P如下:
S →[q0,Z0,q0] ,
[q0,Z0,q0] →b[q0,X,q1] [q1,Z0,q0] ,
[q0, X,q1] →b[q0,X,q1] [q1, X,q1] ,
[q0,X,q1] →a[q1,X,q1] ,
[q1,Z0,q0] →a[q0,Z0,q0] ,
[q0,Z0,q0] →ε,
[q0,Z0,q0] →ε.
24.证明下列语言不是上下文无关语言:
~
⑴{ a n b n c m | m≤n };
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取
ω= a p b p c p ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p
⑴ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0
ω3|>p;
⑵如果ω2和ω3都只包含a (b) ,即ω2ω0ω3 = a j(b j ) (j≤p) ,则当i≠1
时, ω1ω2iω0ω3iω4中会出现a的个数与b的个数不等;
如果ω2和ω3都只包含c ,即ω2ω0ω3 = c j (j≤p),当i大于1时,ω1ω2iω0
ω3iω4中会出现c的个数大于a的个数(b的个数);
⑶如果ω2和ω3分别包含a和b (b和c) ,当i=0时ω1ω2iω0ω3iω4
中会出现a, b的个数小于c的个数(或a,b个数不等)
这些与假设矛盾,故L不是上下文无关语言.
⑵{ a k | k是质数};
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取ω=a k ( k≥p且k≠1 ) ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2
ω0ω3|≤p ,且
)
|ω2ω3|=j≥1 ,则当i=k+1时,|ω1ω2iω0ω3iω4|=k+(i-1)*j=k+k*j=
k*(1+j) ,k*(1+j)至少包含因子k且k≠1 ,因此必定不是质数,即ω1ω2iω0
ω3iω4不属于L.
这与假设矛盾,故L不是上下文无关语言.
⑶由a,b,c 组成的字符串且是含有a,b,c 的个数相同的所有字符串.
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取
ω= a k b k c k (k≥p) ,将ω写为ω=ω1ω2ω0ω3ω4,同时满足|ω2ω0ω3|
≤p
⑴ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0
ω3|>p;
⑵如果ω2和ω3都只包含a (b或c) ,即ω2ω0ω3 = a j(b j或c j ) (j≤p) ,
则当i≠1时, ω1ω2iω0ω3iω4中会出现a,b,c的个数不再相等;
⑶如果ω2和ω3分别包含a和b (b和c) , ω1ω2iω0ω3iω4中会出现
a,b的个数与c的不等;
这些与假设矛盾,故L不是上下文无关语言.
.
25.设G是Chomsky 范式文法,存在ω∈L (G) ,求在边缘为ω的推导树中,最
长的路径长度与ω的长度之间的关系.
解: 设边缘为ω的推导树中,最长路径长度为n,则它与ω的长度之间的关系为|ω|≤2n-1 .
因为由Chomsky范式的定义可知,Chomsky范式文法的推导树都是二叉树,在最长路径长度为n的二叉推导树中,满二叉树推出的句子长度最长,为2n-1,因此ω的长度与其推导树的最长路径长度n的关系可以用上式表示.
26.设计PDA接受下列语言(注意:不要求为确定的)
⑴{ 0m1n | m≤n };
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1,q f } ,
T = { 0,1} ,
Г= { 0,1, Z0 } ,
F = { q f } ,
δ定义如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } ,
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ) } ,
δ( q0,1, Z0 ) = { ( q f,ε) } ,
δ( q0,1, 0 ) = { ( q1,ε) } ,
δ( q1,1, 0 ) = { ( q1,ε) } ,
δ( q1,ε, Z0 ) = { ( q f,ε) }
δ( q1,1, Z0 ) = { ( q f,ε) }
δ( q f,1, ε) = { ( q f,ε) }
⑵{ 0m1n | m≥n };
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中Q = { q0,q1,q f } ,
T = { 0,1} ,
Г= { 0,1, Z0 } ,
F = { q f } ,
δ定义如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } ,
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ) } ,
δ( q0,1, 0 ) = { ( q1,ε) } ,
δ( q1,1, 0 ) = { ( q1,ε) } ,
δ( q1,ε,Z0 ) = { ( q f,ε) } ,
δ( q1,ε,0 ) = { ( q f,ε) }
δ( q f,1, ε) = { ( q f,ε) }
⑶{ 0m1n0m | n和m任意};
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中Q = { q0,q1, q2,q3,q f } ,
T = { 0,1} ,
Г= { 0,1, Z0 } ,
F = { q f } ,
δ定义如下:
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ),( q0,ε)} ,
δ( q0,1, Z0 ) = { ( q3,ε) } ,
δ( q3,1, ε) = { (q3,ε) } ,
δ( q3,ε, ε) = { ( q f,ε) } ,
δ( q0,1,0 ) = { ( q1,0 ) } ,
δ( q1,1,0 ) = { ( q1,0 ) } ,
δ( q1,0,0 ) = { ( q2,ε) } ,
δ( q2,0,0 ) = { ( q2,ε) } ,
δ( q2,ε, Z0 ) = { ( q f,ε) } ,
δ( q0, ε, Z0 ) = { ( q f, ε)}nm
第五章
1.考虑如下的图灵机M = ( {q0, q1, q f, },{0,1},{0,1,B},δ, q0,B,{ q f } ),其中δ定义
为:
δ(q0,0) = {(q1,1,R)} , δ(q1,1) = {(q0,0,R)} , δ(q1,B) = {(q f,B,R)} ,
非形式化但准确地描述该图灵机的工作过程及其所接受的语言.
解: 开始时,M的带上从左端起放有字符串0(10)i(i≥0),后跟无限多个空白符的第一次动作先读到第一个0,并改写为1;然后右移,如果找到第一个1,则改写为0,并继续向右寻找下一个0,这样重复进行.当向右寻找1的时候,找到一个空白符B,则结束.
该图灵机所接受的语言L(M) = { 0(10)i | i≥