当前位置：文档库 › 北京邮电大学-形式语言与自动机-课后习题答案

北京邮电大学-形式语言与自动机-课后习题答案

形式语言与自动机

第二章

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 →y

C C →y C →y

D 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 →a S b S →c

(3) 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={a 2n+1 /n ≥0}

第三章

1．下列集合是否为正则集，若是正则集写出其正则式。

（1）含有偶数个a 和奇数个b 的{a,b}*上的字符串集合（2）含有相同个数a 和b 的字符串集合（3）不含子串aba 的{a,b}*上的字符串集合答：（1）是正则集，自动机如下

a a

b b b b

(2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。

偶a 偶b 偶a 奇b 奇a 奇b 奇a 偶b

(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=d⑤

由③得 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(b a)*

(1)构造右线性文法

(2)找出（1）中文法的有限自动机

答：（1）右线性文法G=({S,A},{a,b},P,S)

P: S→aA A→bS A→ε

（2）自动机如下：

P1 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}),其中ζ如下：

a b

q0q0q1

q1q0q2

q2q0q3

q3q3q3（2）M=({q0,q1 q2 },{a,b},ζ,q0,{q2}),其中ζ如下：

a b

q0q1Φ

q1q2Φ

q2q2q2（3）M=({q0,q1 q2 },{a,b},ζ,q0,{q2}),其中ζ如下：

a b

q0q1q0

q1q2q0

q2q2q0

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满足

a b

[q0] [q0,q1] [ q0]

[q0,q1] [q0,q1,q2] [ q0,q2]

[q0,q1,q2] [ q0,q1, q2,q3] [ q0,q2]

[ q0,q2] [ q0,q1, q3] [q0] [ q0,q1, q2,q3] [ q0,q1, q2,q3] [ q0,q2, q3]

[ q0,q1, q3] [ q0,q1, q2,q3] [ q0,q2, q3]

[ q0,q2, q3] [ q0,q1, q3] [ q0,q3]

[ q0,q3] [ q0,q1, q3] [ q0,q3]

（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满足

a b

[q0] [q1,q3] [q1]

[q1,q3] [q2] [ q0,q1,q2]

[q1] [q2] [q1,q2]

[q2] [q3] [q0] [ q0,q1,q2] [q1,q2,q3] [ q0,q1,q2]

[q1,q2] [q2,q3] [ q0,q1,q2]

[q3] Φ[q0]

[q1,q2,q3] [q2,q3] [ q0,q1,q2]

[q2,q3] [q3] [q0]

15. 15.对下面矩阵表示的ε-NFA

ε a b c

P(起始状态) φ{p} {q} {r}

q {p} {q} {r} φ

r(终止状态) {q} {r} φ{p}

(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为终止状态)

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}

构造相应的DFA M1，并进行化简

答：构造一个相应的DFA M1={Q1, {a,b},ζ1, [q0],{ [q1]，[q0,q1]}

其中Q1 ={[q0]，[q1]，[q0,q1]}

ζ1满足

a b

[q0] [q0,q1] [q1]

[q1] Φ[q0,q1]

[q0,q1] [q0,q1] [q0,q1]

由于该DFA已是最简，故不用化简

17.使用泵浦引理，证明下列集合不是正则集：

（1）由文法G的生成式S→aSbS/c产生的语言L(G)

（2）{ω/ω∈{a,b}*且ω有相同个数的a和b}

（3）{a k ca k/k≥1}

（4）{ωω/ω∈{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 结尾。其他同理。

a/3

b/3

a/3 a/3 b/3

b/1

a/2 b/3

摩尔机，状态说明同米兰机。

a a

b a

a b a b

a b

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 |ε

qaa

qba qbb

qab qaa,3 b/3 qbba,2

b/3

qbb,3 b/3 qbab,1 b/3 qaba,3

b/3

qaab,3 b/3

解: ⑴由算法3，变换为无ε生成式：

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

G1 = ( { S1,S, A1,A2,A3,A4,A5 } , { a,b,d },P1 , S1 ) ,其中生成式P1如下：

S1→ε|S,

S →A1| A2,

A1→A3| A4 ,

A2→A4| A5 ,

A3→S | b ,

A4→S|a,

A5→S | d ,

⑵由算法4，消单生成式：

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

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

运用算法4，则P1变为：

S1 →a | b|d |ε,

S →a | b|d ,

A1→a | b|d ,

A2→a | b|d ,

A3→a | b|d ,

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 ,

用引理4.2.4,变化为D →aS | b | aSD' | bD' , D’→DS | DSD’ ,

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

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

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

G1 = ( { S,D,D’ } , { a,b } ,P1 , S ) ,其中生成式P1如下：

S →aSD | bD | aSD’D | bD'D | a ,

D →aS | b | aSD' | bD' ,

⑵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 ,

用引理4.2.4,变化为

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 ,

用引理4.2.4,变化为

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生成式得

④对于A7→A3A4 , 将A3生成式代入A7生成式得

⑤将A5,A6生成式代入A2’生成式得

将A4,A7生成式代入A3’生成式得

⑶由此得出等价的Greibach范式文法:

G1 = ( { S,D,D’ } , { a,b } ,P1 , S ) ,其中生成式P1如下：

A1→A3A4 | A2A5 ,

A2→A3A4A4 | b | A3A4A4A2’ | bA2’ ,

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 ,

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’|

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 ,

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)

文法具有二义性。

因为当句子ω中a,b,c个数相同时，对于ω存在两个不同的最左(右)推导。

如abc∈L，存在两个不同的最左推导S?AD?aAbD?abD?abcC?abc 及S?EB?aEB?aB?abBc?abc 。

22.设下推自动机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] →ε.

北邮通信网基础课后习题答案

第一章通信网概述简述通信系统模型中各个组成部分的含义，并举例说明。答：通信系统的基本组成包括：信源，变换器，信道，噪声源，反变换器和信宿六部分。信源：产生各种信息的信息源。变换器：将信源发出的信息变换成适合在信道中传输的信号。信道：按传输媒质分有线信道和无线信道，有线信道中，电磁信号或光电信号约束在某种传输线上传输；无线信道中，电磁信号沿空间传输。反变换器：将信道上接收的信号变换成信息接收者可以接收的信息。信宿：信息的接收者。噪声源：系统内各种干扰。现代通信网是如何定义的答：由一定数量的节点和连接这些节点的传输系统有机地组织在一起的，按约定信令或协议完成任意用户间信息交换的通信体系。适应用户呼叫的需要，以用户满意的效果传输网内任意两个或多个用户的信息。试述通信网的构成要素及其功能。答：通信网是由软件和硬件按特定方式构成的一个通信系统。硬件由：终端设备，交换设备和传输系统构成，完成通信网的基本功能：接入、交换和传输；软件由：信令、协议、控制、管理、计费等，它们完成通信网的控制、管理、运营和维护，实现通信网的智能化。分析通信网络各种拓扑结构的特点。（各种网络的拓扑结构图要掌握）答：基本组网结构：》网状网：优点：①各节点之间都有直达线路，可靠性高；②各节点间不需要汇接交换功能，交换费用低；缺点：①各节点间都有线路相连，致使线路多，建设和维护费用大；②通信业务量不大时，线路利用率低。如网中有N 个节点，则传输链路数H=1/2*N(N-1)。》星形网：优点：①线路少，建设和维护费用低；②线路利用率高；缺点：① 可靠性低，②中心节点负荷过重会影响传递速度。如网中有 N 个节点，则

北邮通信原理课后习题答案(只有1-5,8)汇总

第三章 1 2 3

4 5 6 6.1

6.2 7

8 9 10 第4章（1）（2）()()()sin(2)sin(2)m c s t m t c t f t Ac f t ππ==

[cos 2()cos 2()]2c m c m Ac f f t f f t ππ= --+ (){[()][()]}4c m c m Ac S f f f f f f f δδ=+-+-- {[()][()]}4 c m c m Ac f f f f f f δδ-+++-+ （3）相干解调相干解调：将接收信号与载波信号sin(2)fct π相乘，得到 ()sin(2)()sin(2)sin(2)c c c c r t f t A m t f t f t πππ=()[1cos(4)]2 c c A m t f t π= - 通过低通滤波器抑制载频的二倍频分量，得到解调信号为0()()2 c A y t m t = 2解：(1)444)4cos()cos(2 1.210)()cos(2102 1.110t t t s t πππ++=????? 444cos(2 1.110)[10.5cos(20.110)]t t ππ=+???? 调制系数是a=0.5; 信号频率是f=1000Hz (2)44441 ()[(10)(10)]2[( 1.110)( 1.110)]2S f f f f f δδδδ=++-+++-?? 441 [( 1.210)( 1.210)]2 f f δδ+++-?? (3) 3解：(1)已调信号无法用包络检波解调，因为能包络检波的条件是()1m t ≤，这里的max ()151A m t ==>，用包络检波将造成解调波形失真。 (2)

《形式语言与自动机》(王柏、杨娟编著)课后习题答案

形式语言与自动机课后习题答案第二章 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 →y C C →y C →y D 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={a 2n+1 /n ≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。（1）含有偶数个a 和奇数个b 的{a,b}*上的字符串集合（2）含有相同个数a 和b 的字符串集合（3） < （4）不含子串aba 的{a,b}*上的字符串集合答：（1）是正则集，自动机如下 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 ⑥

北邮通信原理课后习题答案

北邮通信原理课后习题答案第三章 1 2 3

4 5

6 6.1 6.2

7 8

9 10 (1) (2) stmtctftAcft()()()sin(2)sin(2),,,,mc Ac ,,,，[cos2()cos2()],,cmcmfftfft2 Ac (){[()][()]},，,，,,,,cmcmSfffffff4 Ac ,，，，,，{[()][()]},,cmcmffffff4 (3)相干解调输出y0(t)r(t)

理想低通滤波器 Cos(Wct) 与发端相干解调相干解调:将接收信号与载波信号相乘，得到 sin(2),fct Ac rtftAmtftft()sin(2)()sin(2)sin(2),,,ccc,c,,()[1cos(4)],mtftc2 Ac 通过低通滤波器抑制载频的二倍频分量，得到解调信号为 0()()ytmt,2 444st()cos(21021.110,，，，，，,,ttt)4cos()cos(21.210)，，,2解:(1) 44,，4cos(21.110)[10.5cos(20.110)],,，，，，tt 调制系数是a=0.5; 信号频率是f=1000Hz 14444 (2) ,，，,，，，,,,,,，，Sfffff()[(10)(10)]2[(1.110)(1.110)]2 144 ，，，,,,，，[(1.210)(1.210)]ff2 S(f) 5/2 2 3/2 1 1/2 10000120000f(Hz)-12000-10000-1100011000 (3) r(t)y(t) 包络检波器 3解:(1)已调信号无法用包络检波解调，因为能包络检波的条件是， mt()1, 这里的，用包络检波将造成解调波形失真。 Amt,,,max()151 (2)

形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析一、按要求完成下列填空 1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2.设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A→ε|A’|A” A’→0|01|01A’ A”→1|10|10A” 3.构造识别下列语言的DFA 2x6' (1) {x|x∈{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) {x|x∈{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R I I ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x I ∈。 )),(),((321R y z R R z x z ∈∧∈??I },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x I ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 I 2型语言 I 1型语言 I 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc

形式语言与自动机

形式语言与自动机的发展和在计算理论中的作用 2015060104020王桢形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称为字母表，用∑表示。又用∑*表示∑中字母组成的所有符号串的集合。∑*的每个子集都是∑上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林在研究神经细跑中，建立了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能用O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为BNF 范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF 范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计算机学科里重要的分支。 19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,

北邮考研通信原理简答题题库

1、非均匀量化的目的是什么？答案：首先，当输入量化器的信号具有非均匀分布的概率密度时，非均匀量化器的输出端可以得到较高的平均信号量化噪声功率比；其次，非均匀量化时，量化噪声对大、小信号的影响大致相同，即改善了小信号时的量化信噪比。难度：较难 2、数字通信有何优点？答案：差错可控；抗干扰能力强，可消除噪声积累；便于加密处理，且保密性好；便于与各种数字终端接口，可用现代化计算技术对信号进行处理、加工、变换、存储；便于集成化，从而使通信设备微型化。难度：较难 3、在PCM 系统中，信号量噪比和信号（系统）带宽有什么关系？答案： )/(22/H f B q N S =，所以PCM 系统的输出信号量噪比随系统的带宽B 按指数规律增长。难度：难 4、什么是带通调制？带通调制的目的是什么？答案：用调制信号去调制一个载波，使载波的某个（些）参数随基带信号的变化规律去变化的过程称为带通调制。调制的目的是实现信号的频谱搬移，使信号适合信道的传输特性。难度：难 5、什么是奈奎斯特准则？什么是奈奎斯特速率？答案：为了得到无码间串扰的传输特性，系统传输函数不必须为矩形，而容许具有缓慢下降边沿的任何形状，只要此传输函数是实函数并且在f=W 处奇对称，称为奈奎斯特准则。同时系统达到的单位带宽速率，称为奈奎斯特速率。难度：难 6、什么是多径效应？答案：在随参信道当中进行信号的传输过程中，由于多径传播的影响，会使信号的包络产生起伏，即衰落；会使信号由单一频率变成窄带信号，即频率弥散现象；还会使信号的某些频率成分消失，即频率选择性衰落。这种由于多径传播对信号的影响称为多径效应。难度：中 8、什么是调制？调制在通信系统中的作用是什么？答案：所谓调制，是指按调制信号的变化规律去控制高频载波的某个参数的过程。作用是：将基带信号变换成适合在信道中传输的已调信号；实现信道的多路复用；改善系统抗噪声性能。难度：难 9、FM 系统的调制制度增益和信号的带宽的关系如何？这一关系说明什么问题？答案：m FM f FM f B m G 223=。说明在大信噪比的情况下，宽带调频系统的制度增益是很高的，也就是说抗噪声性能好。

形式语言与自动机理论蒋宗礼第三章参考答案

第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0 ，1}+ ，1 （3）{x|x {0，1}+且x 中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

（4）{ x|x∈{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态）（5）{x|x∈{0，1}+且x中含形如10110的子串} （6）{x|x∈{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（7）{x|x∈{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t

现代通信网综合练习题_含答案(北邮)

1、通信网的硬件构成要素有___终端设备___、__传输链路___和_交换设备_ 。 2、通信网按服务范围可分为__本地网_、__长途网__和_国际网___ 。 3、通信网的基本结构有_网形_、星形_、_复合形_、_总线形_、_环形_、_树形_和_线形_。 4、支撑网包括_信令网__、_同步网__和__管理网___。 5、业务网即用户信息网，按功能又可分为用户接入网、交换网和传输网三部分。 6、电话网的接续质量通常用接续损失和接续时延来衡量。 7、本地网的类型有特大和大城市本地网和中等城市本地网。 8、本地网的网络结构有_网形网__和__二级网__两种。 9、路由按呼损分有_高效路由__和_低呼损路由__两种。 10、路由选择结构有_有级选路结构___和___无级选路结构____两种。 11、SDH的基本网络单元有__终端复用器___、__分插复用器__和_数字交叉连接设备___。 12、现阶段我国SDH传输网分为四个层面，分别是省际干线层、省内干线层、 ___中继网层面___和用户接入网层面。 13、点线图中点的度数是__与之关联的边的个数__。 14、点线图中的路径是__无重复边的链路___。 15、正则图是__所有点的度数相等___。 16、树的定义是无回路的连通图，只有连通图才有支撑树。 17、具有n个点的树共有n-1 个树枝。 18、B-ISDN业务可分为两大类，分别是交互型业务和分配型业务。 19、ATM的信息单元叫做信元，固定长度为53字节，其中信头为5字节。 20、B-ISDN的用户-网络接口配置中，U B接口的标准速率为155Mbit/s 和622Mbit/s 。 21、ATM交换包括__ VP交换____和__ VC交换___。 22、ATM交换的缓冲排队方式有__输入缓冲排队方式___、__输出缓冲排队方式______ 和___中央缓冲排队方式______。 23、接入网的三种主要接口类型是用户网络接口、业务节点接口和维护管理接。 24、利用分层模型可以将接入网的传送网划分为电路层、传送通道层和_传输媒介层_三个层次。 25、业务节点接口主要有两种，其一是__模拟接口（Z接口）_，其二是_数字接口（V5接口） 26、ADSL系统将双绞线对上的频谱分为三个，分别是___双向普通电话业务_____、______ 上行信道_____________和下行信道。 27、光纤接入网的基本结构有___星形_____、__总线形____和___环形___三种。 28、HFC是一种以模拟频分复用技术为基础，综合应用___模拟___和__数字传输__传输技术、光纤和同轴电缆基础、射频技术及高度分布式智能技术的宽带接入网络，是____ CATV ______网和___电话网_________网结合的产物。 29、按网络覆盖范围可以将计算机网络分成___广域网__、_城域网___和__局域网___。 30、一般将城域网的结构分成3层：__核心层____、_汇聚层___和__接入层__。 31、宽带接入技术主要有：_ ADSL _、__ HFC_、_ FTTX＋LAN __和_无线宽带接入__等。 32、因特网的路由选择协议分成两大类，即：_内部网关协议（IGP）_和_外部网关协议（EGP）。 33、信令网由__信令点__、_信令转接点____和连接它们的信令链路组成。

北邮《数字通信原理》期末综合练习题

数字通信原理》综合练习题一、填空题 1 、模拟信号的特点是幅度（信号强度）的取值连续变化，数字信号的特点是 ___ 幅度的取值离散变化 _ 。 2 、模拟通信采用频分制 ___实现多路通信，数字通信采用时分制 _ 实现多路通信。 3、 PAM 信号的 ___幅度 _ 连续， ___时间离散，它属于 ___模拟 ___信号。 4 、数字通信系统的主要性能指标有 _ 有效性 ___和 ___ 可靠性 ____ 两个方面。 5、 A/D 变换包括 __ 抽样 ____ 、 ____ 量化 ___ 和 _____ 编码三步。 6、 D/A 变换包括 __ 译码 _____ 和 ___ 低通 _____ 两步。 7 、波形编码是 _ 对信号波形进行的编码（或根据语声信号波形的特点，将其转换为数字信号）。 8 、参量编码是 ___ 提取语声信号的一些特征参量对其进行编码 ______ 。 9 、抽样是将模拟信号在 ___ 时间上 __ 离散化的过程，抽样要满足 __抽样定理。 10、量化是将 PAM 信号在幅度上 _______ 离散化的过程。 11、量化分为 ___ 均匀量化 ___ 和 ___ 非均匀量化 __。 12、均匀量化量化区内（非过载区）的最大量化误差为 ___=△ /2 __ ；过载区内的最大量化误差为 __ > △ /2___ 。 13、 A 律压缩特性小信号时，随着时，随着 A 的增大，信噪比改善量 14、实现非均匀量化的方法有 ________________ ___模拟压扩法和 15、 A 律压缩特性一般 A 的取值为 87.6 ______ 。 A 的增大，信噪比改善量 Q___下降 ___ 。 Q ___ 提高 ___ ；大信号

形式语言与自动机课后习题答案

形式语言与自动机课后作业答案第二章 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)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）不含子串aba的{a,b}*上的字符串集合答：（1）是正则集，自动机如下 (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组成的所有字符串的集合

北邮《现代通信网》期末复习题含答案+阶段作业汇总

现代通信网-综合练习题一、填空题 1、所谓通信系统就就是用电信号(或光信号)传递信息的系统,也叫电信系统。 2、通信网在硬件设备方面的构成要素就是终端设备、传输链路与交换设备。 3、若按服务范围分,电话网通信网可分为本地网、长途网与国际网。 4、通信网的基本结构主要有网形、星形、复合形、总线形、环形及线形、树形。 5、未来的通信网正向着数字化、综合化、智能化与个人化的方向发展 6、电话通信网通常由用户终端(电话机)、传输信道与交换机等构成。 7、我国电话通信网由长途电话网(长途网)与本地电话网(本地网)两部分组成。 8、二级结构的本地网,有分区汇接与全覆盖两种结构。 9、按组成路由的电路群的个数,路由可分为直达路由与汇接路由两种。 10、路由选择计划有固定选路计划与动态选路计划两种。 11、动态选路方法有时间相关选路(TDR)、状态相关选路(SDR)与事件相关选路(EDR)三种。 12、 B-ISDN的业务分为两大类,分别就是交互型业务与分配型业务。 13、 B-ISDN的信息传递方式采用异步转移模式 (ATM)。 14、 ATM交换包括VP交换与VC交换。 15、 ATM协议参考模型的三个平面包括用户平面、控制平面与管理平面。 16、 ATM交换的缓冲排队方式有输入缓冲排队方式、输出缓冲排队方式与中央缓冲排队方式。 17、TCP/IP协议就是IP网络的基础与核心。 18、宽带IP城域网的结构分为核心层、汇聚层与接入层三层。 19、路由器按位置划分有核心路由器与接入路由器。 20、接入网由业务节点接口(SNI)与用户网络接口 (UNI)之间的一系列传送实体(如线路设施与传输设施)组成,为供给电信业务而提供所需传送承载能力的实施系统。 21、接入网的业务节点接口主要有两种,模拟接口(Z 接口)与数字接口(V5接口)。 22、根据传输设施中就是否采用有源器件,光纤接入网分为有源光网络 (AON)与无源光网络 (PON)。 23、无源光网络(PON)的拓扑结构一般采用星形、树形与总线形。 24、无线接入网可分为固定无线接入网与移动无线接入网两大类。 25、无线局域网(WLAN)就是无线通信技术与计算机网络相结合的产物。 26、 No、7信令网由信令点(SP)、信令转接点(STP) 与信令链路组成。27、三级信令网由高级信令转接点(HSTP)、低级信令转接点(LSTP)与信令点(SP)三级构成。 28、我国No、7信令网就是由长途信令网与大、中城市本地信令网组成。 29、我国数字同步网的基准时钟有两种:全国基准时钟(PRC)与区域基准时钟(LPR)。 30、 TMN主要从三个方面界定电信网络的管理:管理层次、管理功能与管理业务。 31、我国电信管理网的网络结构一般也分为三级, 并且在各级网管机构设置该级的网管中心,即全国网网管中心、省级网网管中心与本地网网管中心。 32、没有自环与并行边的图称为简单图。 33、一般有两种距离测度方法,即欧氏距离测度与矩形线距离测度。 34、具有n个点的树共有 n-1 个树枝。 35、排队系统的基本参数包括:顾客到达率、服务员数目与服务员服务速率。 36、通信网络规划按时间跨度可分为长期规划、中期规划与近期规划(滚动规划)。 37、通信业务预测的内容主要包括用户预测、业务量预测与业务流量预测。 38、随着网络规模的不断扩大,局所采用“大容量、少局点”的布局已显得十分必要。 39、用户环路的配线方式有直接配线、复接配线与交接配线。 40、两交换局间中继路由种类主要由费用比与局间话务量确定。二、单项选择题 1、构成通信网的核心要素就是(C)C 交换设备 2、通信网的下列基本结构中可以采用自愈环的就是 (C)C 环形网 3、响度、清晰度与逼真度就是用来衡量电话通信网的(B)B 传输质量 4、我国电话网现在采用的等级结构为(B)B 三级 5、我国在二级长途网上采用选路方式为D)动态无级 6、话务量不允许溢出的路由为(D) A 低呼损直达路由C 基干路由 D A与C 7、电子邮件属于(B)B 消息型业务 8、 ATM网中VC交换就是(B)B VPI值、VCI值均改变 9、下列关于ATM的描述中,不正确的就是(C) C ATM网中,要进行逐段链路的差错控制与流量控制 10、二层交换机的特点就是(A)交换速度快,控制功能弱 11、路由器可以实现协议转换的层次为(D) D 物理层、链路层及网络层 12、下面所列接入网接口中,不属于用户网络接口的就是(C)C V5、2接口 13、目前以太网接入的实现方式为(A)A FTTC与 FTTB 14、属于移动无线接入的有(C)C 蜂窝移动通信系统 15、我国No、7信令网的级数为(B)B 三级

形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S →X01011Y X →ε|0X|1X Y →ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A →ε |A ’|A ” A’ →0|01|01A ’ A ” →1|10|10A ” 3. 构造识别下列语言的DFA 2x6' (1) {x|x ∈{0，1}+且x 以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） 1 S 1 1 0,10 (2) {x|x ∈{0，1} + 且x 的第十个字符为1} （设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态） 1S 0,1 0,10,10,10,110,0,10,10,10,1 0,1

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x ∈。 )),(),((321R y z R R z x z ∈∧∈?? },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 2型语言 1型语言 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc

形式语言与自动机的关系

形式语言与自动机的关系研究新疆师范大学数理信息学院数学03-6班摘要：形式语言的直观意义，自动机的直观意义，形式语言的定义，形式语言的特征，语法的分类，自动机的定义，自动机的分类，各种自动机的定义，形式语言和自动的的关系，自动机的对语言的例子基本关键词：形式语言的定义；自动机的定义；形式语言和自动机的关系 1，形式语言的直观意义 α→的直观地讲，形式语言是用来精确描述语言和它结构的手段。它一重写规则β α,均为字符串。重写规则就是在包含α的字符穿中遇见规则左边的形式来表示，其中，β α时，α部分重新写为右边的β。这样一个初设的字符串通过不断地运用重写规则，就可以到另一个字符串。通过选择不同的规则并且以各种不同的顺序来运用最这些规则，如果指定一个初始符，某规则以其为左部，一组规则就可以构成一个语法。 2，形式语言的定义

形式语法是一个四元组G=（N, V , P, S ）,其中N 是非终结符的有限集合，有时也称变量，它们相当于各种句法范畴。V 是终结符的有限集合，若语法生成的是自然语言，这些终端语符就相当于这种语言中具体的词，终端语符集这种语言的词库，P 是以重写规则的有限集合，基本形式P }{βα→，即""βα改写为，其中箭头表示指令，一条规则就是一个机械性的操作程序，用来演算它联系着的两侧语符集或语符序列之间的关系，而S 是一个特定的初始符； 3，语法的分类乔姆斯在他的著名【文章】中根据重写规则将语法分成四类：正则语法，上下文有关语法，上下文无关语法；有这些语法生成的语言是正则语言，，上下文有关语言，上下文无关语言，递归数集合。 a 如果P 中的规则，满足如下的形式：x A Bx A →→或，，其中，A,B 是非终结符，x 是终结符，则G 称为正则语法（简称为FSG ）。 b 如果P 中的规则，满足如下的形式：α→A ,其中，A 是非终结符, α是由N 和V 中字符所组成的字符串（或可表示为()*∈V N α,*意味着它右边的字符可以重复0到任何多次），则G 称为上下文无关语法（简称为CFG ）。 d 如果P 中的规则，满足如下的形式：αγββα→A ,其中，A 是非终结符,γβα,,,是字符串，且γ至少包含一个字符，则G 称为上下有无关语法（简称为CSG ）。 d 如果P 中的规则，满足如下的形式：其中，α，β是字符串，则G 称为无限制重写系统。对于以上任何一种语法，两个字符串之间一次派生关系?可定义为：如果y x →是P 中的规则，βαβαy x ?。字符串α，β有多次派生关系* ?则是说，通过多次应用一次派生关系，从α可派生出β，并记为α* ?β： n αβαα==,0，而对n i i n i +?-=αα,1,....0。给定以语法，其语言定义为所有合法终结字符串的集合。合法终结字符串是指由初始符S 出发，运用重写规则而派生得终结字符串，即， (){}ααα**;?∈=S V G L 例子：假设G=(N, V , P, S), N={S, A} , V={0, 1}, P={0,0,1→→→A A A A S } 则，{}110)(≥=m G L m 是正则语法，在V={0, 1}上它所对应的正则表达式是100*。形式语言的特征： ⑴ 高度抽象化（采用形式化的手段，专用符号，数学公式来描述语言的，结构关系，这种关系是抽象的）。

(精品)(通信企业管理)北京邮电大学现代通信网阶段作业全

（通信企业管理）北京邮电大学现代通信网阶段作业全

一、判断题（共5道小题，共50.0分） (错误) 欧式距离测度适用于固定电话，考虑到用户线路沿着方格形街道铺设的情况。 1正确 1错误知识点: 通信网络结构设计基础学生答案: [A;] 标准答案: B 得分: [0] 试题分值: 10.0 提示: 1 (错误) 度数为奇数的点的数目必为偶数。 1正确 1错误知识点: 通信网络结构设计基础

学生答案: [] 标准答案: A 得分: [0] 试题分值: 10.0 提示: 2 (错误) 主从同步方式各节点必须采用原子钟作为时钟源。 1正确 1错误知识点: 第6章电信支撑网学生答案: [] 标准答案: B 得分: [0] 试题分值: 10.0 提示: 3 (错误)

No.7信令是一种数字式随路信令方式。 1正确 1错误知识点: 第6章电信支撑网学生答案: [] 标准答案: B 得分: [0] 试题分值: 10.0 提示: 4 (错误) 交接配线的通融性要好于复接配线。 1正确 1错误知识点: 第8章通信网络规划学生答案: [] 标准答案: A 得分: [0] 试题分10.0

值: 提示: 二、单项选择题（共5道小题，共50.0分） (错误) 关于排队系统，下面说法错误的是（） 1顾客到达间隔时间的分布为负指数分布 1服务时间的分布为负指数分布 1系统只有一个服务员 1为损失排队系统（即时拒绝方式）知识点: 网络流量设计基础学生答案: [] 标准答案: D 得分: [0] 试题分值: 10.0 提示: 5 (错误) 关于排队系统，下面说法错误的是（）

移动通信原理与系统(北京邮电出版社)课后习题答案

第一章概述 1．1简述移动通信的特点：答：①移动通信利用无线电波进行信息传输；②移动通信在强干扰环境下工作；③通信容量有限；④通信系统复杂；⑤对移动台的要求高。 1．2移动台主要受哪些干扰影响？哪些干扰是蜂窝系统所特有的？答：①互调干扰；②邻道干扰；③同频干扰（蜂窝系统所特有的）；④多址干扰。 1．3简述蜂窝式移动通信的发展历史，说明各代移动通信系统的特点。答：第一代（1G）以模拟式蜂窝网为主要特征，是20世纪70年代末80年代初就开始商用的。其中最有代表性的是北美的AMPS（Advanced Mobile Phone System）、欧洲的TACS（Total Access Communication System）两大系统，另外还有北欧的NMT 及日本的HCMTS系统等。从技术特色上看，1G以解决两个动态性中最基本的用户这一重动态性为核心并适当考虑到第二重信道动态性。主要是措施是采用频分多址FDMA 方式实现对用户的动态寻址功能，并以蜂窝式网络结构和频率规划实现载频再用方式，达到扩大覆盖服务范围和满足用户数量增长的需求。在信道动态特性匹配上，适当采用了性能优良的模拟调频方式，并利用基站二重空间分集方式抵抗空间选择性衰落。第二代（2G）以数字化为主要特征，构成数字式蜂窝移动通信系统，它于20世纪90年代初正式走向商用。其中最具有代表性的有欧洲的时分多址（TDMA）GSM（GSM原意为Group Special Mobile，1989年以后改为Global System for Mobile Communication）、北美的码分多址（CDMA）的IS-95 两大系统，另外还有日本的PDC 系统等。从技术特色上看，它是以数字化为基础，较全面地考虑了信道与用户的二重动态特性及相应的匹配措施。主要的实现措施有：采用TDMA（GSM）、CDMA（IS-95）方式实现对用户的动态寻址功能，并以数字式蜂窝网络结构和频率（相位）规划实现载频（相位）再用方式，从而扩大覆盖服务范围和满足用户数量增长的需求。在对信道动态特性的匹配上采取了下面一系列措施：（1）采用抗干扰性能优良的数字式调制：GMSK（GSM）、QPSK（IS-95），性能优良的抗干扰纠错编码：卷积码（GSM、IS-95）、级联码（GSM）；（2）采用功率控制技术抵抗慢衰落和远近效应，这对于CDMA方式的IS-95尤为重要；（3）采用自适应均衡（GSM）和Rake 接收（IS-95）抗频率选择性衰落与多径干扰；（4）采用信道交织编码，如采用帧间交织方式（GSM）和块交织方式（IS-95）抗时间选择性衰落。第三代（3G）以多媒体业务为主要特征，它于本世纪初刚刚投入商业化运营。其中最具有代表性的有北美的CDMA2000、欧洲和日本的WCDMA及我国提出的TD-SCDMA三大系统，另外还有欧洲的DECT及北美的UMC-136。从技术上看，3G 是在2G 系统适配信道与用户二重动态特性的基础上又引入了业务的动态性，即在3G 系统中，用户业务既可以是单一的语音、数据、图像，也可以是多媒体业务，且用户选择业务是随机的，这个是第三重动态性的引入使系统大大复杂化。所以第三代是在第二代数字化基础上的、以业务多媒体化为主要目标，全面考虑并完善对信道、用户二重动态特性匹配特性，并适当考虑到业务的动态性能，尽力采用相应措施予以实现的技术。其主要实现措施有：（1）继续采用第二代（2G）中所采用的所有行之有效的措施；（2）对CDMA 扩频方式应一分为二，一方面扩频提高了抗干扰性，提高了通信容量；另一方面由于扩频码互相关性能的不理想，使多址干扰、远近效应影响增大，并且对功率控制提出了更高要求等；（3）为了克服CDMA 中的多址干扰，在3G 系统中，上行链路建议采用多用户检测与智能天线技术；下行链路采用发端分集、空时编码技术；（4）为了实现与业务动态特性的匹配，3G 中采用了可实现对不同速率业务（不同扩频比）间仍具有正交性能的OVSF（可变扩频比正交码）多址码；（5）针对数据业务要求误码率低且实施性要求不高的特点，3G 中对数据业务采用了Turbo 码。