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

北京邮电大学自动机课后习题答案

形式语言与自动机

课后练习答案

第二章

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组成的所有字符串的集合

(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）自动机如下：

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结尾的所有字符串集合

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]}

（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]}

(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

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]} 由于该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 结尾。其他同理。

b/3

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

第四章

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 |

解: ⑴由算法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 |

因此生成的无单生成式等效文法为

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

A3’ | aA3’A4A3’ ,

⑶由此得出等价的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] →ε.

23.证明下列语言不是上下文无关语言:

⑴{ 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不是上下文无关语言.

24.设G是Chomsky 范式文法,存在ω∈L (G) ，求在边缘为ω的推导树中,最长的路

径长度与ω的长度之间的关系.

解: 设边缘为ω的推导树中,最长路径长度为n,则它与ω的长度之间的关系为|ω|≤2n-1 .

因为由Chomsky范式的定义可知,Chomsky范式文法的推导树都是二叉树,在最长路径长度为n的二叉推导树中,满二叉树推出的句子长度最长,为2n-1,因此ω的长度与其推导树的最长路径长度n的关系可以用上式表示.

25.设计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),后跟无限多个空白符B.M的第一次动作先读到第一个0,并改写为1;然后右移,如果找到第一个1,则改写为0,并继续向右寻找下一个0,这样重复进行.当向右寻找1的时候,找到一个空白符B,则结束.

该图灵机所接受的语言L(M) = { 0(10)i | i≥

北邮通信原理课后习题答案(只有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)

(完整版)微机原理课后习题参考答案

第一章 2、完成下列数制之间的转换。（1）01011100B=92D （3）135D=10000111B （5）10110010B=262Q=B2H 3、组合型BCD码和非组合型BCD码有什么区别？写出十进制数254的组合型BCD数和非组合型数。答：组合型BCD码用高四位和低四位分别对应十进制数的个位和十位，其表示范围是0~99；非组合型BCD码用一个字节的低四位表示十进制数，高四位则任意取值，表示范围为0~9。组合型：254=（001001010100）BCD 非组合型：254=（00000010 00000101 00000100）BCD 7、计算机为什么采用补码形式存储数据？当计算机的字长n=16，补码的数据表示范围是多少？答：在补码运算过程中，符号位参加运算，简化了加减法规则，且能使减法运算转化为加法运算，可以简化机器的运算器电路。+32767~ -32768。 9、设计算机字长n=8，求下列各式的[X+Y]补和[X-Y]补，并验证计算结果是否正确。（1）X=18，Y=89 [X+Y]补=00010010+01011001=01101011B=107D 正确 [X-Y]补=10111001B=00010010+10100111=（-71D）补正确（2）X=-23，Y=-11 [X+Y]补=11101001+11110101=11011110B=（-34D）补正确[X-Y]补=11101001+00001011=11110100B=（-12D）补正确（3）X=18，Y=-15 [X+Y]补=00010010+11110001=00000011B=（3D）补正确 [X-Y]补=00010010+00001111=00100001B=（33D）补正确（4）X=-18，Y=120 [X+Y]补=11101110+01111000=01100110B=（102D）补正确[X-Y]补=11101110+10001000=01110110B=（123D）补由于X-Y=-138 超出了机器数范围，因此出错了。 13、微型计算机的主要性能指标有哪些？答:CPU字长、存储器容量、运算速度、CPU内核和IO工作电压、制造工艺、扩展能力、软件配置。第二章 2、8086标志寄存器包含哪些标志位？试说明各标志位的作用。答：进位标志：CF；奇偶校验：PF；辅助进位：AF；零标志：ZF；符号标志：SF；溢出标志：OF。 5、逻辑地址与物理地址有什么区别？如何将逻辑地址转换为物理地址？答：物理地址是访问存储器的实际地址，一个存储单元对应唯一的一个物理地址。逻辑地址是对应逻辑段内的一种地址表示形式，它由段基址和段内偏移地址两部分组成，通常表示为段基址：偏移地址。物理地址=段基址*10H+偏移地址。 6、写出下列逻辑地址的段基址、偏移地址和物理地址。（1）2314H：0035H （2）1FD0H:000AH 答：（1）段基址：2314H；偏移地址：0035H；物理地址：23175H。（2）段基址：1FD0H；偏移地址：000AH；物理地址：1FD0AH。 8、设（CS）=2025H，（IP）=0100H，则当前将要执行指令的物理地址是多少？答：物理地址=（CS）*10H+（IP）=20350H 9、设一个16字的数据区，它的起始地址为70A0H：DDF6H（段基址：偏移地址），求这个数据区的首字单元和末字单元的物理地址。

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

形式语言与自动机课后习题答案第二章 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)

微机原理课后习题答案

李伯成《微机原理》习题第一章本章作业参考书目： ①薛钧义主编《微型计算机原理与应用——Intel 80X86系列》机械工业出版社2002年2月第一版 ②陆一倩编《微型计算机原理及其应用（十六位微型机）》哈尔滨工业大学出版社1994年8月第四版 ③王永山等编《微型计算机原理与应用》西安电子科技大学出版社2000年9月 1.1将下列二进制数转换成十进制数： X=10010110B= 1*27+0*26+0*25+1*24+0*23+1*22+1*21 +0*21 =128D+0D+0D+16D+0D+0D+4D+2D=150D X=101101100B =1*28+0*27+1*26+1*25+0*24+1*23+1*22+0*21+0*20 =256D+0D+64D+32D+0D+16D+4D+0D=364D X=1101101B= 1*26+1*25+0*24+1*23+1*22+0*21 +1*20 =64D+32D+0D+8D+4D+0D+1D=109D 1.2 将下列二进制小数转换成十进制数：（1）X=0.00111B= 0*2-1+0*2-2+1*2-3+1*2-4+1*2-5= 0D+0D+0.125D+0.0625D+0.03125D=0.21875D (2) X=0.11011B= 1*2-1+1*2-2+0*2-3+1*2-4+1*2-5= 0.5D+0.25D+0D+0.0625D+0.03125D=0.84375D (3) X=0.101101B= 1*2-1+0*2-2+1*2-3+1*2-4+0*2-5+1*2-6= 0.5D+0D+0.125D+0.0625D+0D+0.015625D=0.703125D 1.3 将下列十进制整数转换成二进制数：（1）X=254D=11111110B （2）X=1039D=10000001111B （3）X=141D=10001101B 1.4 将下列十进制小数转换成二进制数：（1）X=0.75D=0.11B (2) X=0.102 D=0.0001101B (3) X=0.6667D=0.101010101B 1.5 将下列十进制数转换成二进制数 (1) 100.25D= 0110 0100.01H (2) 680.75D= 0010 1010 1000.11B 1.6 将下列二进制数转换成十进制数 (1) X=1001101.1011B =77.6875D

网制作理论试题及答案

网制作理论试题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]

《网页制作》理论试题及答案一、单选题 1.当测览器不能正常显示图像时，会在图像的位置显示的内容__A__。 A.替代 B.目标 C.地图 D.低品质源 2.将超链接的目标网页在当前窗口中打开的方式是__D___。 3.当网页既设置了背景图像又设置了背景色，那么__A__。 A.以背景图像为主 B.以背景色为主 C.产生--种混合效果 D.冲突，不能同时设置 4.在页面属性对话框中，我们不能设置__C___。 A.网页的背景色 B.网页文本的颜色 C.网页文本的大小 D.网页的边界 5.在文本的属性面板中，不能设置___D__ 。 A.文字的大小和颜色 B.加粗或倾斜风格 C.文字的超链接 D.矩形热区 6.下列路径中属于绝对路径的是___A___ 。 B./xuesheng/chengji/ C. D. staff/ 可以导入的表格式数据的格式是___C___。格式格式 C.文本格式 D.任意格式 8.要一次选择整个行，在标签检查器中选择___B___ 标签。

9.指定表格内单元格之间的间隙大小，需要设置表格属性面板中的___B___。 10.如果层中的图片太大，要设置超出部分照样显示，则"溢出"选项中应选择 __A___ 。 11.不论层中的内容是否超出，都显示滚动条，则"溢出"选项中应选择 ___C____ 。 12.利用键盘方向键移动层时，一次按键只能移动 ___A___ px。 13.层的对齐万式"设成宽度相同"的含义是__B___ 。 A.所有层的宽度调整为和最初选取的层的宽度一样 B.所有层的宽度调整为和最后选取的层的宽度一样 C.所有层的宽度调整为和最窄的层的宽度一样 D.所有层的宽度调整为和最宽的层的宽度一样 14.下列说法中错误的是 __A___ 。 A.模板一次只能更新一个页面自动在文档的head部分插入可编辑区域 C.创建模板时，可编辑区域和锁定区域都可以更改 D.在基于模板的文档中，模板用户只能在可编辑区域中进行更改;无法修改锁定区域 15.能够作为库项目的是 ____D__ 。样式表 B.时间轴 C.行为 D.表格 16．要想在新的浏览器窗口中打开链接页面，应将链接对象的“target”属性设为( B ) 。

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

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=。说明在大信噪比的情况下，宽带调频系统的制度增益是很高的，也就是说抗噪声性能好。

微机原理课后作业答案(第五版)

6、[+42]原＝00101010B=[+42]反＝[+42]补 [－42]原＝B [－42]反＝B [－42]补＝B [+85]原＝01010101B=[+85]反＝[+85]补 [－85]原＝B [－85]反＝B [－85]补＝B 10、微型计算机基本结构框图微处理器通过一组总线(Bus)与存储器和I/O接口相连，根据指令的控制，选中并控制它们。微处理器的工作：控制它与存储器或I/O设备间的数据交换；进行算术和逻辑运算等操作；判定和控制程序流向。存储器用来存放数据和指令，其内容以二进制表示。每个单元可存8位(1字节)二进制信息。输入——将原始数据和程序传送到计算机。输出——将计算机处理好的数据以各种形式（数字、字母、文字、图形、图像和声音等）送到外部。接口电路是主机和外设间的桥梁，提供数据缓冲驱动、信号电平转换、信息转换、地址译码、定时控制等各种功能。总线：从CPU和各I/O接口芯片的内部各功能电路的连接，到计算机系统内部的各部件间的数据传送和通信，乃至计算机主板与适配器卡的连接，以及计算机与外部设备间的连接，都要通过总线（Bus）来实现。 13、8086有20根地址线A19～A0，最大可寻址220=1048576字节单元，即1MB；80386有32根地址线，可寻址232=4GB。8086有16根数据线，80386有32根数据线。

1、8086外部有16根数据总线，可并行传送16位数据；具有20根地址总线，能直接寻址220=1MB的内存空间；用低16位地址线访问I/O端口，可访问216=64K个I/O端口。另外，8088只有8根数据总线 2、8086 CPU由两部分组成：总线接口单元（Bus Interface Unit，BIU） BIU负责CPU与内存和I/O端口间的数据交换： BIU先从指定内存单元中取出指令，送到指令队列中排队，等待执行。执行指令时所需的操作数，也可由BIU从指定的内存单元或I/O端口中获取，再送到EU去执行。执行完指令后，可通过BIU将数据传送到内存或I/O端口中。指令执行单元（Execution Unit，EU） EU负责执行指令：它先从BIU的指令队列中取出指令，送到EU控制器，经译码分析后执行指令。EU的算术逻辑单元（Arithmetic Logic Unit，ALU）完成各种运算。 6、见书P28-29。 7.（1）1200：3500H=1200H×16+3500H=15500H （2）FF00：0458H=FF00H×16+0458H=FF458H （3）3A60：0100H=3A80H×16+0100H=3A700H 8、（1）段起始地址1200H×16＝12000H,结束地址1200H×16+FFFFH＝21FFFH （2）段起始地址3F05H×16＝3F050H,结束地址3F05H×16+FFFFH＝4F04FH （3）段起始地址0FFEH×16＝0FFE0H,结束地址0FFEH×16+FFFFH＝1FFD0H 9、3456H×16+0210H=34770H 11、堆栈地址范围：2000：0000H~2000H(0300H-1)，即20000H~202FFH。执行两条PUSH指令后，SS：SP=2000：02FCH，再执行1条PUSH指令后，SS：SP=2000：02FAH。 12、（2000H）=3AH, (2001H)=28H, (2002H)=56H, (2003H)=4FH 从2000H单元取出一个字数据需要1次操作，数据是283AH; 从2001H单元取出一个字数据需要2次操作，数据是5628H; 17、CPU读写一次存储器或I/O端口的时间叫总线周期。1个总线周期需要4个系统时钟周期（T1~T4）。8086－2的时钟频率为8MHz，则一个T周期为125ns，一个总线周期为500ns，则CPU每秒最多可以执行200万条指令。

中医基础理论考试题库及答案(5)

中医基础理论考试题库及答案《中医基础理论》试题（三）一、单项选择题：（每题1分，共30分）（在下列备选答案中，选出一个最佳答案）1．古代哲学精气概念的产生是源于: A.水地说 B.五材说 C.元气说 D.五方说 E.人体之精说 2．因情志刺激，突然出现下焦胀满，甚至小便失禁。此因： A 恐则气下 B 悲则气消 C 惊则气乱 D 喜则气缓 E 怒则气上 3．痰与饮的主要区别是： A 热者为痰，寒者为饮。 B 得阳气煎熬而成者为痰，受阴气凝聚而成者为饮。 C 浓度较大，较粘稠者为痰；浓度较小，较清稀者为饮。 D 色黄者为痰，色白者为饮。 E 以上都不是。 4．在温病学方面，创立以“三焦为核心”的辨证论治方法的医家是： A朱丹溪 B吴鞠通 C吴又可 D刘完素 E薛生白 5．与语言、声音、呼吸的强弱有关的是： A营气 B卫气C宗气 D元气 E谷气 6．下列不属于津液的排泄途径是： A汗B尿 C粪D呕吐物 E呼气 7．言人身脏腑之阴阳，则脾为： A阴中之阴B阴中之阳 C阴中之至阴 D阳中之阴 E阳中之阳 8．“肝火犯肺”是属于： A子病犯母 B相克 C相乘D相侮 E母病及子 9．与情志抑郁最为关联的是： 34

A心神不足 B髓海空虚 C肝失疏泄 D肝升太过 E神不守舍10．肾在液为： A涎 B唾 C尿 D泪 E涕 11．“泻南补北”法适用于： A肾阴虚而肝阳亢 B肾阴虚而相火动 C肾阴虚而心火旺 D心阴虚而心阳亢 E以上均不是 12．下列不是津所布散的主要部位的是： A皮肤 B孔窍C肌肉D关节 E血脉 13．易使人出现各种血证的是： A 风邪 B 暑邪 C 燥邪 D 火邪 E 寒邪 14．属于阴中之阳的时间是: A.上午 B.下午 C.前半夜 D.后半夜 E.以上都不是15．“益火之源，以消阴翳”的治法适用于： A.实寒证 B.实热证 C.虚寒证 D.虚热证 E.阴阳两虚证16．在五行生克关系中，下列哪项是错误的？ A.木克土 B.火生土 C.金生水 D.金克木 E.水克木 17．在阴阳失调病机中，阳偏衰以哪脏为根本： A心 B肝 C 脾 D肺 E肾 18．“一源三歧”的三条经脉是： A冲、任、带 B任、督、带 C冲、任、督 D督、冲、带 E督、冲、跷 19．少阳经在头部经过的部位是： A头后部 B侧头部 C头顶部 D前额部 E全头部 20．脾之华在： 34

北京邮电大学自动机课后习题答案

形式语言与自动机课后练习答案第二章 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}*

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

数字通信原理》综合练习题一、填空题 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 ___ 提高 ___ ；大信号

自动机理论、语言和计算导论课后复习题答案(中文版)

Solutions for Section 2.2 Exercise 2.2.1(a) States correspond to the eight combinations of switch positions, and also must indicate whether the previous roll came out at D, i.e., whether the previous input was accepted. Let 0 represent a position to the left (as in the diagram) and 1 a position to the right. Each state can be represented by a sequence of three 0's or 1's, representing the directions of the three switches, in order from left to right. We follow these three bits by either a indicating it is an accepting state or r, indicating rejection. Of the 16 possible states, it turns out that only 13 are accessible from the initial state, 000r. Here is the transition table: 杠杆可能出现8种情况，影响着最终状态。并且也要说明，前面一个石球是否从D滚出，也就是说，前一个输入是否被接受。令 0 代表向左方的状态（如图表），1 代表向右方。这三个杠杆的每一个状态都可以用三个数（0或1）组成的序列表示。这个序列后面跟着字母a或者r。a代表接受状态，r代表拒绝状态。16种可能的状态中，只有13种是从初始状态000r可达的。下面它的有穷自动机的转移表。

微机原理课后答案

1.2 课后练习题一、填空题 1．将二进制数1011011.1转换为十六进制数为__5B.8H_____。 2．将十进制数199转换为二进制数为____ 11000111____B。 3．BCD码表示的数,加减时逢__10____进一，ASCII码用来表示数值时，是一种非压缩的BCD 码。 4．十进制数36.875转换成二进制是___100100.111____________。 5．以_微型计算机____为主体，配上系统软件和外设之后，就构成了__微型计算机系统____。6．十进制数98.45转换成二进制为__1100010.0111_B、八进制__142.3463________Q、十六进制__62.7333________H。（精确到小数点后4位）二、选择题 1．堆栈的工作方式是__B_________。 A）先进先出B）后进先出C）随机读写D）只能读出不能写入 2．八位定点补码整数的范围是____D_________。 A）-128-+128 B）-127-+127 C）-127-+128 D）-128-+127 3．字长为16位的数可表示有符号数的范围是___B___。 A）-32767-+32768 B）-32768-+32767 C）0-65535 D）-32768-+32768 三、简答题 1．微型计算机系统的基本组成？微型计算机，系统软件，应用软件，输入输出设备 2．简述冯.诺依曼型计算机基本思想？ ●将计算过程描述为由许多条指令按一定顺序组成的程序，并放入存储器保存 ●指令按其在存储器中存放的顺序执行； ●由控制器控制整个程序和数据的存取以及程序的执行； ●以运算器为核心，所有的执行都经过运算器。 3．什么是微型计算机？微型计算机由CPU、存储器、输入/输出接口电路和系统总线构成。 4．什么是溢出？运算结果超出了计算机所能表示的范围。 2．2 一、填空题 1. 8086/8088的基本总线周期由___4____个时钟周期组成，若CPU主频为10MHz，则一个时钟周期的时间为___0.1μs_____。 2. 在8086CPU的时序中，为满足慢速外围芯片的需要，CPU采样___READY_________信号，若未准备好，插入___TW__________时钟周期。 3. 8086系统总线形成时，须要用_____ALE__________信号锁定地址信号。 4. 对于8086微处理器，可屏蔽中断请求输入信号加在_____INTR__________引脚。

2019年考研政治理论试题库及答案

2019年考研政治理论试题库及答案十个怎么办之一一、填空题 1、科学发展观的第一要义是（发展） 2、中国解决所有问题的关键是要靠自己的发展，是（邓小平）提出来的。 3、解决中国一切问题的总钥匙是（发展） 4、又好又快发展强调的是更加注重（发展质量和效益），走生产发展、生活富裕、生态良好的文明发展道路。 5、坚持发展为先、做到又好又快，必须以（经济建设）为中心，更加注重（经济建设、政治建设、文化建设、社会建设）协调发展。二、判断题 1、发展不但是经济问题，也是一个重大的政治问题。（对） 2、发展必须牢牢扭住经济建设这个中心（对） 3、发展应是又快又好的发展。（错） 4、要实现科学发展、和谐发展、率先发展，必须要着力把握发展规律、大胆创新发展理念、积极转变发展方式、认真破解发展难题。（对） 5、转变增长方式与转变发展方式没有什么区别（错） 6、增长并不等于发展（对）三、理论题 1、大寨村、江西的新江村，济南的振兴街道。他们的故事说明一个道理？只有加快经济发展，才能不断满足人民群众日益增长的物质文化需要；提高人民群众的生活水平朝着共同富裕的方向不断前进；才能更好地解决经济社会生活中的各种矛盾和问题，增强战胜各种困难、应对各种挑战和抵御各种风险的能力。 2、结合济南章丘官庄乡的发展，怎样理解又好又快发展？好表现在几个方面？又好又快要求快以好为前提，同时快也是好的必要条件，必须处理好好与快的辩证关系。

好应该表现在结构优化、资源节约、生态良好、民生改善。 3、中国重汽的又好又快发展说明了什么？怎样加快转变发展方式？始终坚持把自主创新、提高企业核心竞争力放在第一位。第一必须坚持走中国特色新型工业化道路，第二必须坚持走中国特色自主创新道路，第三必须坚持走中国特色农业现代化道路，第四必须把建设资源节约型、环境友好型社会放在工业化、现代化发展战略的突出位置，实现基本公共服务均等化，第五必须坚持走中国特色城镇化道路，第六必须坚定不移地扩大内需。之二一、填空 1、科学发展观的核心是（以人为本） 2、（实现好、维护好、发展好最广大人民的根本利益）是党和国家一切工作的出发点。 3、以人为本的“人”是指（人民群众）“本”就是（本源、根本）就是（出发点、落脚点），就是最广大人民的根本利益。 4、（人民群众）是生产力中最活跃、最革命的因素，（相信谁、为了谁、依靠谁、是否站在最广大人民的立场上）是区分唯物史观和唯心史观的分水岭，也是判断马克思主义政党的试金石。 5、搞好学习实践活动的目的是（人民群众得实惠）。二、判断 1、之所以把以人为本作为科学发展观的核心，根本原因在于它体现了马克思历史唯物论的基本原理，又体现了我党的根本宗旨和我们推动经济社会发展的根本目的。（对） 2、以人为本就是以广大人民的根本利益为本（对） 3、古代的民本思想和现在的以人为本没有本质区别（错） 4、以人为本是我们党立党为公、执政为民的本质要求。（对） 5、以人为本就是坚持发展为了人民、发展依靠人民、发展成果人民共享。（对）

微机原理习题解答

第一章微型计算机的基础知识 1-1 将下列十进制数转换为二进制数、十六进制数。 (1)110 (2)1 039 (3)0.75 (4)0.156 25 1-2 将下列十进制数转换为BCD 码。 (1)129 (2)5 678 (3)0.984 (4)93.745 1-3 将下列二进制数转换为十进制数、十六进制数。 (1)10101010 (2)10000000 (3)11000011.01 (4)01111110 1-4 将下列十六进制数转换为二进制数、十进制数。 (1)8E6H (2)0A42H (3)7E.C5H (4) 0F19.1DH 1-5 将下列二进制数转换为BCD 码。 (1)1011011.101 (2)1010110.001 1-6 将下列BCD 码转换为二进制数。 (1)(0010 0111 0011) BCD (2)(1001 0111.0010 0101) BCD 1-7 完成下列二进制数的运算。 (1)1001.11＋11.11 (2)1101.01-0110.11 (3)1000.011-1001.101 (4)1111＋1101 1-8 完成下列十六进制数的运算。 (1)6AH＋0A6H (2)0AB1FH＋0EFCH (3)12ADH-1DEH (4)117H-0ABH 1-9 已知X=01H，Y=0FFH ，在下面的情况下比较两数的大小。 (1)无符号数 (2)符号数 (均为补码) 1-10 计算下列各表达式。 (1)101＋‘A’＋01101001B＋0D5H＋57Q (2)127.8125＋10111101.101＋375.63Q＋1FC.8AH 1-11 写出下列字符串的ASCII 码。 (1)HELLO (2)A8=

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

形式语言与自动机课后作业答案第二章 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-5,8)汇总

(完整版)微机原理课后习题参考答案

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

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

微机原理课后习题答案

网制作理论试题及答案

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

微机原理课后作业答案(第五版)

中医基础理论考试题库及答案(5)

北京邮电大学 自动机 课后习题答案

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

最新-政治理论考试题库(含答案)实用版

自动机理论、语言和计算导论课后复习题答案(中文版)

微机原理课后答案

2019年考研政治理论试题库及答案

微机原理习题解答

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

北京邮电大学自动机课后习题答案

北京邮电大学自动机课后习题答案