北邮形式语言与自动机二三章答案

形式语言与自动机课后作业答案

第二章

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

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

（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)={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=({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满足

由于该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不等于1时不属于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不等于1时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不等于1时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不等于1时不满足ωω的形式，不属于该集合

与假设矛盾。则该集合不是正则集

18．构造米兰机和摩尔机

对于{a,b}*的字符串，如果输入以bab结尾，则输出1；如果输入以bba结尾，则输出2；否则输出3。

答：米兰机：

说明状态qaa表示到这个状态时，输入的字符串是以aa结尾。其他同理。

b/3

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

形式语言与自动机

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

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

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

第三章作业答案 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

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

形式语言与自动机课后作业答案 第二章 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. 给出集合{Φ,{Φ}}和集合{ε,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

北邮通信原理复习重点提示

北邮通信原理复习重点提示 说明：本文是根据我自己的考研经验，以及近两年来讲授北邮通信原理辅导班的经历所写，旨在为大家复习通信原理提供一些参考，这样在复习中更容易做到有的放矢，提高复习的效率。 无论是801还是803都有通信原理的考试大纲，但是实际上考试大纲的参考价值并不大，其主要原因在于考试大纲所给出的内容太过简单，这样使得很多内容都模糊，令考生无法把握复习的度。本文将在考试大纲的基础上进行更详细的说明。考虑到801和803中通信原理的部分基本相同，下面的介绍同时适合801和803。 以下对北邮通信原理的内容进行标记，标记中重要程度顺序为：了解，识记，理解，掌握。了解就是看看就行，能记下一些就记一些。对于识记，就是知道有这么回事，遇到填空要会，能记住结论，实在记不下也没事，没有必要详细推导其中的原理。理解就是要求能弄懂知识点的来龙去脉，能独立推导出结论。掌握其实也是理解，只是更深入的理解，不但能理解书上所提到的知识本身，还应该能将基本原理灵活运行，遇到与之类似的问题也能解决。其中标有★的内容为最重点内容，几乎是每年必考的，务必掌握。 再次说明：以下所说的不是大纲，是我根据自己的经验所写，仅供参考。 第一章绪论 介绍通信的发展历史和一些相关的技术，考纲没有要求，肯定不考。也没有什么可以考，不过可以在复习累了的时候当小说看，消遣嘛！ 第二章确定信号分析 这一章系统介绍了通信的基础知识，包括傅立叶变换，相关，卷积，希尔伯特变换，能量信号与功率信号，解析信号，频带信号，这些都是非常重要的，而且是全书中比较难的地方，花的时间可能会比较多。如果这章很熟练了，看起后面的章节来会比较容易。 2.2 确定信号的分类了解 2.3 周期信号的傅利叶级数分析识记结论 2.4 傅利叶变换理解变换的原理，并能运用 2.5 单位冲激函数的傅利叶变换识记结论，掌握变换的方法 2.6 功率信号的傅利叶变换识记结论 2.7 能量谱密度和功率谱密度理解定义，并能运用 2.8 确定信号的相关函数理解定义的含义 2.9 卷积理解定义，掌握计算方法 2.10 确定信号通过线性系统了解基本过程

北邮通信原理通原实验16QAM

实验二、16QAM调制 一、实验目的 1、学会使用SystemView观察信号的星座图与眼图，分析性能 2、学习正交幅度调制解调的基本原理。 二、实验原理 1、正交幅度调制 QAM是由两个正交载波的多电平振幅键控信号叠加而成的，因此正交幅度调制是一种频谱利用率很高的调制方式。同时利用已调信号在同一带宽内频谱正交的性质来实现两路并行的数字信息在一个信道中传输。 2、调制原理 3、解调原理 4、眼图 眼图的“眼睛”的大小代表码间串扰的情况。“眼睛”张开的越大，表示码间串扰越小；反之表示码间串扰越大。 5、星座图 我们通常把信号矢量端点的分布图称为星座图。它对于调制方式的误码率有很直观的判断。 三、实验内容 1、在system view软件中做出仿真连线图。

2、设置参数，观察调制信号波形 3、眼图设置：在SystemView中，在分析窗口单击图标，选择style，单击slice，并且设置合适的起点和终点的时间切片，然后选择信号后，得到眼图。 4、星座图设置：在SystemView中，在分析窗口中单击图标，选择style，单击scatter plot，在右侧的窗口中选择所需要观察的信号波形，确定，得到星座图。 5、设置无噪声和有噪声情况参数，对眼图和星座图进行对比分析。 四、实验结果 1、无噪声情况下，即序列均值为0，方差为0。 原基带信号：

调制信号（同向） （正交）

无噪眼图： 无噪星座图： 2、有噪声：均值为0，方差为1 眼图（有噪）：

星座图（有噪）： 五、结果分析 从上述实验结果图中可以看出： 1、原基带信号经过调制后，同向正交都满足。 2、在无噪情况下，眼图较清晰，眼睛睁开较大，表明码间干扰较小； 星座图能量较规整，误码率相对较低。 3、在有噪情况下，眼图较，眼睛睁开较小，表明码间干扰较大； 星座图能量杂乱，误码率较高。 4、可见，噪声对系统性能有一定影响。

北邮考研通信原理模拟题7

试题七 一. 回答下列问题 (1)平稳随机过程)(t X 的自相关函数为)(τR 。已知对任意t ，()t X 和()τ+t X 当∞→τ时不相关。问)(t X 的平均功率，直流功率，交流功率各为多少？ (2)什么是理想信道的幅频特性，相频特性。 (3)有一个FM 发射机，它的最大调频频偏为10kHz ，已知调频的调制信号最高频率为3kHz ，求此调频信号的带宽。 (4)已知信息代码是1100000000100000，请将它编成如下的码型。 (a)AMI 码 (b)HDB3码 (c)数字双相码 (5)在功率谱密度为0 N 2的高斯白噪声干扰下，设计了一个对下图中()s t 匹配的匹配滤波器， 问如何确定最大输出信噪比的时刻。求最大输出信噪比。 二. 已知信号)2cos()]1002cos(1[)(t f t t s c ππ×+=（V ），其中载波1kHz c f = (1)画出信号的幅度谱； )(t s (2)是何种调制方式？请画出它的解调框图。 )(t s 三. 双边功率谱密度为0 N 2的高斯白噪声输入下图所示系统

(1) 求在系统输出端的随机过程的功率谱密度； (2) 求其输出的均值和方差； (3) 写出输出信号的一维概率密度函数表达式。 四. 假定解调器输入端的信号功率比发送端的信号功率低100dB ，信道中加性高斯噪声的双 边功率谱密度为140 10W/Hz 2 N ?=，基带调制信号的最高频率分量为，输出信噪比要求30dB ，试求在下列不同情况下的发送功率应是多少？ 10kHz m f =(1)单边带调幅 (2)双边带调幅； 五. 已知某计算机终端每秒钟输出9600个“0”、“1”等概的符号，符号“1”的波形是 ()()19600g t u t u t ??=???? ??，符号“0”的波形是()g t ?，其中()u t 是单位阶跃函数。求 (1)该终端输出信号的功率谱密度； (2)如果我们需要把该终端的输出通过一个频率范围是0~2400Hz 的基带信道传输，请设计一种可实现的系统，画出系统的示意框图，并给出必要参数，算出此系统的频带利用率。 六. 一个单极性矩形2PAM 序列通过加性白高斯噪声信道传输，接收端通过一个接收滤波器 后进行采样，将采样结果和门限电压2A 比较后给出判决。已知采样点的信号成分以相 等的概率取值于A 、0两个电平，噪声成分的均值为零，方差为2 σ，另外采样点还存在 等概取值于2A 及2A ? 码间干扰。求该系统的平均误比特率。 From https://www.wendangku.net/doc/787207919.html,/myhearty/home

通信原理实验报告(北邮)

通信原理实验 实验报告 实验二抑制载波双边带的产生（DS B SC g e n er at i on）一、实验目的：

1．了解抑制载波双边带（SC-DSB）调制器的基本原理。 2．测试S C-DSB 调制器的特性。 二、实验步骤： 1．将T IMS 系统中的音频振荡器(Audio O scillator)、主振荡器(Master S ignals)、缓冲放大器(Buffer Amplifiers)和乘法器(Multiplier)按图（1）连接。 图（1）抑制载波的双边带产生方法一 2．用频率计来调整音频振荡器，使其输出为1kHz，作为调制信号，并调整缓冲放大器的K1,使其输出到乘法器的电压振幅为1V。 3．调整缓冲放大器的K2，使主振荡器输至乘法器的电压为1V，作为载波信号。 4．测量乘法器的输出电压，并绘制其波形。 5．调整音频振荡器的输出，重复步骤4。 6．将电压控制振荡器（VCO）模快和可调低通滤波器（Tuneable LPF）模块按图（2）连接。 图（2）抑制载波的双边带产生方法二 7．VCO 得频率选择开关器至于“LO”状态下，调整VCO 的Vin（控制电压DC－3V~3V ）使VCO 的输出频率为10kHZ。 8．将可调低通滤波器的频率范围选择范围至“wide”状态，并将频率调整至最大，此时截至频率大约在12kHz 左右。 9．将可调低通滤波器的输出端连接至频率计，其读数除360 就为LPF 的3dB 截止频率。10．降低可调LPF 的截止频率，使SC-DSB 信号刚好完全通过低通滤波器，记录此频率（fh=fc+F）。

11．再降低3dB 截止频率，至刚好只有单一频率的正弦波通过低通滤波器，记录频率（fl=fc-F） 12．变化音频振荡器输出为频率为800Hz、500Hz，重复步骤10、11。 三、实验结果： 1. 音频振荡器输出1KHz 正弦信号作为调制信号。 已调信号波形图： 2. 音频振荡器输出1.5KHz 正弦信号作为调制信号。 已调信号波形图： 3.调整音频振荡器输出2KHz 正弦信号作为调制信号。 已调信号波形图：

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

第一章参考答案 1.1请用列举法给出下列集合。（吴贤珺02282047） ⑴你知道的各种颜色。 解：{红，橙，黄，绿，青，蓝，紫} ⑵大学教师中的各种职称。 解：{助教，讲师，副教授，教授} ⑶你所学过的课程。 解：{语文，数学，英语，物理，化学，生物，历史，地理，政治} ⑷你的家庭成员。 解：{父亲，母亲，妹妹，我} ⑸你知道的所有交通工具。 解：{汽车，火车，飞机，轮船，马车} ⑹字母表{a , b}上长度小于4的串的集合。 解：{a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb} ⑺集合{1,2,3,4}的幂集。 解：{Φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4}, {1,3,4},{2,3,4},{1,2,3,4} } ⑻所有的非负奇数。 解：{1,3,5,7,…} ⑼0～100的所有正整数。 解：{1,2,3, (100) (10) 1～10之间的和为10的整数集合的集合。 解：设所求的集合为A，集合A中的元素为A i（i=1,2,3,…），A i也是集合，A i中的元素在1～10之间，并且和为10。根据集合元素的彼此可区分性，可以计算出A i中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样， A i中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1， 这样相加的和最小，要加到10，元素个数就最多。 求出最大的∣A i∣＝4后，再求出元素个数为3，2，1的集合就可以了。 故A={{10},{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,6},{1,4,5},{2,3,5},{1,2,3,4}} 1.2 请用命题法给出下列集合

形式语言与自动机理论试题

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

、判断(正确的写 T ,错误的写F ) 5x2 1?设R 和R 2是集合{a,b,c,d,e}上的二元关系，则 (R 只2 )民 R R 只只 (T ) 任取(x.,y),其中 x,y {a,b,c,d,e}，使得(x,y) (R R 2)FR 。 不成立，假设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分)。 S aBC|aSBC aB ab bB T bb CB T BC bC T bc C C T cc 推导一： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaabCBCBC =>aaabBCCBC =>aaabbCCBC =>aaabbCBCC z((x, z) R R 2 (z, y) R 3) z {a,b,c,d,e} z((x, z) R 1 (x, z ) R 2 (z, y) R 3) z((x,z) R 1 (z,y) R a ) z((x,z) R 2 (z, y) (x,y) R 1 R 3 (x, y) R 2R 3 (x, y) R 1 R 3 R 2 R 3 2.对于任 ?非空集合A , ①2A (T ) 3.文法G : S f A|AS A —? a|b|c|d|e|f|g 是 RG (F) 型语言 2型语言 1型语言 0型语言 (T ) * (rs+s ) * * r=rr s (rr s ) * (F ) R a )

北邮通信原理实验

北京邮电大学 通信原理 实验报告 学院：电子工程学院班级： 姓名： 班内学号：

实验二抑制载波双边带的产生 一、实验目的 1.了解抑制载波双边带(SC-DSB)调制器的基本原理。 2.测试SC-DSB 调制器的特性。 二、实验步骤 1.将TIMS 系统中的音频振荡器(Audio Oscillator)、主振荡器(Master Signals)、缓冲放大器(Buffer Amplifiers)和乘法器(Multiplier)按下图连接。 图1 实验连接图方式一 2.用频率计来调整音频振荡器，使其输出为1kHz 作为调制信号，并调整冲放大器的K1,使其输出到乘法器的电压振幅为1V。

3.调整缓冲放大器的K2，使主振荡器输至乘法器的电压为1V 作为载波号。 4.测量乘法器的输出电压，并绘制其波形。如下图2所示。 图2 乘法器输出电压波形 5.调整音频振荡器的输出，重复步骤4。如下图3所示。 图3 调整后输出波形 三、思考题 1.如何能使示波器上能清楚地观察到载波信号的变化？

答：可以通过观察输出信号的频谱来观察载波的变化，另一方面，调制信号和载波信号的频 率要相差大一些，可通过调整音频震荡器来完成。 2.用频率计直接读SC—DSB 信号，将会读出什么值。 答：围绕一个中心频率来回摆动的值。 实验三振幅调制（Amplitude modulation） 一、实验目的 1.了解振幅调制器的基本工作原理。 2.了解调幅波调制系数的意义和求法。 二、实验步骤 1.将Tims 系统中的音频振荡器（Audio Oscillator）、可变直流电压（Variable DC）、主振荡器（Master Signals）、加法器（Adder）和乘法器（Multiplier）按图1连接。 图1 振幅调制方法一 2.音频振荡器输出为1kHz，主振荡器输出为100kHz，将乘法器输入耦合开关置DC 状态。 3.将可变直流器调节旋钮逆时针旋转至最小，此时输出为-2.5V，加法器输出为+2.5V。 4.分别调整加法器的增益G 和g，使加法器交流振幅输出为1V，DC 输出也为1V。 5.用示波器观察乘法器的输出(见图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→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组成的所有字符串的集合

北邮通信原理2

多进制数字调制系统 多进制数字调制具有以下两个特点： （1）在相同的码元传输速率下，多进制数字调制系统的信息传输速率比二 进制高。 R b =R B2 bit /s R b =N B R log N bit /s (2) 在相同的信息传输速率下，多进制数字调制系统的码元传输速率比二进制低， 2 B B R R N <, B N ＜B 2 可增加码元的能量,减小干扰的影响。 1. 多进制数字振幅调制(MASK ) (1)多进制数字振幅调制的原理。 ——多进制数字振幅调制又称多电平调制。 *MASK 表示式: (波形) e ASK =t nT t g b c s n n ωcos )(-∑ b n =???????----------------M P M P P 1 (102) 1 P 1+P 2+……..P M =1 (2) 系统的带宽: B ASK = s T 2 (3)单位频带内有超过2bit /s.Hz 的信息传输速率。 2. 进制数字频率调制(MFSK )

(1)多进制数字频率调制的原理 ——MFSK调制简称多频制,是二进制数字频率键控方式的直接推广。(2) 一个多频制系统的组成方框如图: ※带通滤波器的中心频率就是多个载频的频率。 ※抽样判决器-----在给定时刻上比较各包络。 (3) MFSK系统带宽: B FSK=|f M-f l|+Δf Δf单个码元宽度。 3.多进制数字相位调制(MPSK) (1)多进制数字相位调制的原理 ——多进制数字相位调制又称多相制。 *利用载波的多种不同相位(或相位差)表征数字信息的调制方式。也可分为绝对移相(MPSK)和相对(差分)移相(MDPSK)两种。 *多进制相位调制: M=2k K位码元。 一个相位表示K位二进码元. *以四相制为例 (2)QPSK(QDPSK)信号调制的原理 (A)QPSK: 定义:用载波的四种不同相位来表征数列中的信息。 两个信息比特与载波相位 关系如下,分为A方式, B方式。 (B) QDSK: 定义:利用前后码元之间的相对相位变化来表示数字信息。

第二章节形式语言与自动机理论参考测试答案

2．1回答下面的问题： （周期律 02282067） （1）在文法中，终极符号和非终极符号各起什么作用？ ? 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语 言中字符的范围。 ? 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至 少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。 （2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ ? 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式 中关于A 的产生式推导实现的 ? 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ） ={w S T w w **|?∈且} （3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？ ? 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句 型的语言。 （4）文法中的归约和推导有什么不同？ ? 推导：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γαδ在G 中推导出了γβδ。 ? 归约：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γβδ在G 中归约到γαδ。 ? 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下 （从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。 （5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ ? 非空：根据字母表幂的定义：εε,}{0∑=为字母表中０个字符组成的。这样，当字母 表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 ? 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上 我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义