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
∑
=为字母表中０个字符组成的。这样，当字母
表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 ? 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上
我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义
（6）任意给定一个字母表
∑
，该字母表上的语言都具有有穷描述吗？为什么？
? 错误，因为一个字母表上有不可数无穷多个语言，而有穷表示只可能是可数无穷多个，
又因为不可数无穷集和可数无穷集不是一一对应的，所以存在这样的语言，他不存在有穷表示。
（7）请总结一下，在构造文法时，可以从哪几个方面入手？ ? 我们可以将其类比于软件工程中的概念:-)
? 首先，也是最重要的一点，需求分析，我们需要知道需要构造的语言的特点，具体表现
形式，以及一些需要注意的细节，通过一些特例提炼特点。
? 其次，概要设计，将语言从具体中抽象到符号上，按照其特性将其划分类别。 ? 再次，详细设计，将每一部分抽象的成果具体化，将所有细节符号化 ? 再次，编码，将详细设计的结果用文法符号的语言表示出来 ? 最后，测试，找出边缘数据，特殊数据进行测试。
（8）按照文法的乔姆斯基体系，文法被分为几类？各有什么样的特点？ 分为四类：
? 文法G = {V ，T ，P ，S}，对应的Ｌ（Ｇ）则为０型文法或短语结果文法。 ? 如果对于P ∈→?βα，均有
αβ≥成立，则称Ｇ为１型文法或上下文有关文法，对应的Ｌ（Ｇ）称为１型语言。 ? 如果对于P ∈→?βα，均有
αβ≥成立，且V ∈α成立，则称Ｇ为２型文法，或
上下文无关文法，对应的Ｌ（Ｇ）为２型语言。
? 如果对于P ∈→?βα，所有βα→均有：wB A w A →→或成立，其中
,,,+∈∈T w V B A 则称Ｇ为３型文法，或正则文法，对应的Ｌ（Ｇ）称３型语言。
（9）什么叫左线性文法？什么叫右线性文法？什么叫线性文法
? 文法G = {V ，T ，P ，S}，如果对于P ∈→?βα，所有βα→均有：wBx
A w A →→或成立，,,,,*
T w x V B A ∈∈则称Ｇ为线性文法。
? 文法G = {V ，T ，P ，S}，如果对于P ∈→?βα，所有βα→均有：wB
A w A →→或成立，其中,,,+∈∈T w V
B A 则称Ｇ为右线性文法。
? 文法G = {V ，T ，P ，S}，如果对于P ∈→?βα，所有βα→均有：Bw
A w A →→或成立，其中,,,+∈∈T w V
B A 则称Ｇ为左线性文法。
（10）既然已经定义2-10中允许RL 包含空语句ε，那么定理2-6和定理2-7还有什么意义？
?此为定义与定理的区别，定义2-10是针对文法Ｇ是ＲＧ的情况下，定义其产生式加上ε
S后仍为ＲＧ，Ｇ的语言仍为ＲＬ，而定理2-6和定理2-7针对的前提条件是如果→
Ｌ为ＲＬ，他们都是通过定义2-10证明得到的，可以在以后的推论中直接应用的。
******************************************************************************* 2. 设L = { 0n | n ≥1 },试构造满足要求的文法G.
(1)G是RG.
(2)G是CFG, 但不是RG.
(3)G是CSG, 但不是CFG.
(4)G是短语结构文法,但不是CSG.
解答：
1：S→0|0S
2：S→0|0S|SS
3：S→0|0S|AS
AS→SA
AS→0A
0A→S0
0AS→00
4：S→0|0S|AS
AS→SA|ABB
ABB→AS
AB→A|ε
******************************************************************************* 3.设文法G的产生式集如下，试给出句子id+id*id的两个不同的推导和两个不同的归约
E→id|c|+E|-E|E+E|E-E|E*E|E/E|E**E|Fun(E) （褚颖娜02282072）推导：
(1)E=>E+E=>E+E*E=>E+E*id=> E+id*id=>id+id*id
(2)E=>E*E=>E*id=>E+E*id=>E+id*id=>id+id*id
归约：
(1)id+id*id<= E+id*id<= E+E*id<= E+E*E <=E+E<=E
(2)id+id*id<= E+id*id<= E+E*id<=E*id<= E*E<=E
****************************************************************************** 2.4 设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导和至少两个不同的归约（02282081刘秋雯）bB→bb
CB→BC
bC→bc
cC→cc
解：推导一：
S→aBC|aSBC
aB→ab
S=>aSBC
=>aaSBCBC
=>aaaBCBCBC
=>aaabCBCBC
=>aaabBCCBC
=>aaabbCCBC
=>aaabbCBCC
=>aaabbBCCC
=>aaabbbCCC
=>aaabbbcCC
=>aaabbbccc
推导二：
S=>aSBC
=>aaSBCBC
=>aaaBCBCBC
=>aaaBBCCBC
=>aaaBBCBCC
=>aaabbCBCC
=>aaabbBCCC
=>aaabbbCCC
=>aaabbbcCC
=>aaabbbccc
归约一、归约二分别为推导一和推导二的逆过程
******************************************************************************* 5 句子abeebbeeba的一个推导如下：（陈伟芳学号？？）S=>aAa 使用产生式S→aAa
=>aSSa 使用产生式A→SS
=>abAbSa 使用产生式S→bAb
=>abSSbSa 使用产生式A→SS
=>abeSbSa 使用产生式S→e
=>abeebSa 使用产生式S→e
=>abeebbAba 使用产生式S→bAb
=>abeebbSSba 使用产生式A→SS
=>abeebbeSba 使用产生式S→e
=>abeebbeeba 使用产生式S→e
不能给出abeebbeeb的归约，因为由文法G中产生式推出的句子只有三种情况：头尾都是a,头尾都是b，或者只有一个e，而abeebbeeb上面三个条件都不符合，所以它不是文法G 的一个句子，当然也就不能给出它的一个归约了。*******************************************************************************
2.6 设文法G的产生式集如下,请给出G的每个语法范畴代表的集合.
S→aSa|aaSaa|aAa
A→bA|bbbA|bB
B→cB|cC
C→ccC|DD
D→dD|d
解:
set(D)={d}+
set(C)={ c 2n d m | m ≥2 n ≥0} set(B)={ c n d m |m ≥2 n ≥1}
set(A)={ b p c n d m | p ≥1, m ≥2, n ≥1}
set(S)={ a q b p c n d m a q | p ≥1 ,m ≥2, n ≥1, q ≥1}
******************************************************************************* 7．给定如下文法，请用自然语言描述它们定义的语言。 （吴贤珺 02282047） ⑴ A →aaA │aaB B →Bcc │D#cc D →bbbD │#
解：该语言由四部分组成：第一部分是偶数个a （至少有两个），第二部分是3的倍数个b （可以是0个），第三部分是两个“#”号，第四部分是偶数个c （至少有两个）。 ⑵ A →0B │1B │2B B →0C │1C │2C
C →0
D │1D │2D │0│1│2 D →0B │1B │2B
解：该语言的句子是字母表∑＝{0,1,2}上所有长度为3的倍数的字符串，且非空。 ⑶ A →0B │1B │2B B →0C │1B │2B
C →0E │1
D │2D │0│1│2 D →0C │1B │2B
E →0E │1D │2D │0│1│2
解：观察发现C 和E 所对应产生式右部是相同的。所以将文法化简成如下的形式：
A →0
B │1B │2B B →0
C │1B │2B
C →0C │1
D │2D │0│1│2 D →0C │1B │2B 作出状态图如下：
可以看出从初始状态A 到终态F ，至少要经过A →B →C →F 的过程，所以字符串的长
度至少为3。而且，到F 只能经过C ，如果到达C 后走其它的路径，那么所经过的弧上A B C
D
0, 1, 2
1, 2
1, 2
1, 2
0 0, 1, 2
F
的字符串都是以0为结尾，也就是要回到C，最后一个字符一定是0。这样，该文法所确定的语言就是所有倒数第2个字符是0的串。
⑷ S→aB│bA
A→a│aS│BAA
B→b│bS│ABB
解：由于该文法所确定的语言一时不易看出，可以先考虑简单的形式：
S→aB│bA
A→a│aS
B→b│bS
不难看出，该文法所确定的语言为所有由ab和ba组成的串，且非空。这些串有一个特点，就是a和b的个数相等。然后，把产生式A→BAA 和B→ABB加回到原来的文法中，并且可以把这两个产生式看成是在左部的符号前分别加上串BA和AB。不妨把它们看成一个符号C和D。这样原文法可以改造成如下形式：
S→aB│bA
A→a│aS│CA
B→b│bS│DB
C→BA
D→AB
发现插入的C和D所导入的A和B是成对的，原文法所确定的语言可能就是字母表∑＝{a,b}上所有含有相同个a和b的字符串，且非空。从上面简单形式的文法中已经看到，它所确定的字符串比a和b个数相同的所有串少的只是多个a或b连续的情况。
而加上产生式A→BAA 和B→ABB后则刚好满足。
例如：由S推出aB后，在B前“插入”D（即AB），可由AB中的A推出a，就得到aaBB，如此类推，最终可得该文法所接受的语言为：字母表∑＝{a,b}上所有a和b个数相等的非空字符串。
******************************************************************************* 8．设∑={0,1},请给出∑上的下列语言的文法
(1)所有以0开头的串
S→0A|0
A→0|1||0A|1A
(2)所有以0开头以1结尾的串
S→0A
A→1|0A|1A
(3)所有以11开头以11结尾的串
S→11A|11
A→11|0A|1A
(4)所有最多有一对连续的0或者最多有一对连续的1
1：x中既没有成对的0，也没有成对的1
2：x有一对连续的0
3：x有一对连续的1
4：x中既有一对连续的0，也有一对连续的1
S→A|B|C|D
A→ε|A’|A”
A’→0|01|01A’
A”→1|10|10A”
B→B’00B”
B’→1|01|1B’|01B’
B”→1|10|1B”10B”
C→C’11C”
C’→0|10|0C’|10C’
C”→0|01|0C”|01C”
D→E00F11H|P11G00K
E→1|1E’|E’
E’→01E’|E’
F→ε|10|10F // F 以1开头，以0结尾；不含连续0和连续1 H→0|H’0|H’
H’→01|01H’
P→0|0P’|P’
P’→10P’|10
G→ε|01|01G // G 以0开头，以1结尾；不含连续0和连续1 K→1|K’1|K’
K’→10|10K’
(5) 所有最多有一对连续的0而且最多有一对连续的1
1：x中既没有成对的0，也没有成对的1
2：x只有一对连续的0，没有连续的1
3：y只有一对连续的1，没有连续的0
4：x中既有一对连续的0，也有一对连续的1
S→A|B|C|D
A→ε|A’|A”
A’→0|01|01A’
A”→1|10|10A”
B→B’00B”’
B’→ε|1|01|01B’’|1 B’’// B’是不含连续0，也不含连续1的串B’’→01|01 B’’
B”’→ε|1|10|10B””// B””是不含连续0，也不含连续1的串B””→10|10 B””
C→C’11C”’// C’是不含连续1，也不含连续0的串C’→ε|0|10|0C”|10C”
C”→10|10 C”
C”’→ε|0|01|01C””// C””是不含连续1，也不含连续0的串C””→01|01 C””
D →E00F11H|P11G00K
E →1|1E ’|E ’ E ’ →01E ’|E ’
F →ε|10|10F // F 以1开头，以0结尾；不含连续0和连续1 H →0|H ’0|H ’ H ’ →01|01H ’ P →0|0P ’|P ’ P ’ →10P ’|10
G →ε|01|01G // G 以0开头，以1结尾；不含连续0和连续1 K →1|K ’1|K ’ K ’ →10|10K ’
(6)所有长度为偶数的串
S →01|10|00|11|01S|10S|00S|11S (7)所有包含子串01011的串 S →X01011Y X →ε|0X|1X Y →ε|0Y|1Y
(8)所有含有3个连续0的串 S →X000Y X →ε|0X|1X Y →ε|0Y|1Y
******************************************************************************* 2.9 设},,,{c b a =∑，构造下列语言的文法。 (1) }0|{1≥=n b a L n
n 。
解答：)},|{},,{},({1S aSb S b a S G ε→=。 (2) }1,|{2≥=m n b a L m
n 。
解答：)},|,|,|{},,{},,,({2S b bB B a aA A B A S b a B A S G →→→=。
(3) }1|{3≥=n a b a L n
n n 。
解答：),},,{},,,({33S P b a B A S G = :3P S →aAB|aSAB
BA →AB
aB →ab
bB →bb bA →ba
aA →aa
(4) }1,,|{4≥=k m n a b a L k
m n 。
解答：)},|,|,{},,{},,({4S b bB B a aA A ABA S b a A S G →→→=。
(5) },|{5+
∑∈∑∈=w a awa L 。
解答：)},|||||,{},,,{},,({5S c b a cW bW aW W aWa S c b a W S G →→=。
(6) },|{6+
∑∈=w x xwx L T 。
解答：),},,,{},,({66S P c b a W S G = :6P cWc bWb aWa S ||→ c b a cW bW aW W |||||→。
(7) },|{7+
∑∈==w w w w L T 。
解答：}},|||||{},,,{},,{{7S c b a cWc bWb aWa S c b a W S G →=。
(8) },|{8+
∑∈=w x w xx L T 。
解答：),},,,{},,,({88S P c b a X W S G = XW S P →:8
c b a cXc bXb aXa X |||||→ c b a cW bW aW W |||||→。
******************************************************************************* 第10题参见下题：
11、给定RG
11111(,,,)G V T P S = 2222,2(,,)G V T P S =
试分别构造满足下列要求的RG G ，并证明你的结论。
12(1)()()()L G L G L G =
{}()
{}{}
{}
()()()()()()
1212121212
332111
*12122121111*2222 V V S V V G S V V T T P P P S P S S T S S S
S x L G S x
x L G L G L G L G x S S x x x x T x L G S x G P x L ωωωααεεεεεεω+++=??==→∈?→→→∈?=∈∈∈≠→=∈∈?∈解：
不妨假设，并且，令，，，其中，
且证明：
（1）设，则若，因为，，所以成立若，由产生式，不妨设，其中，则，因为的产生式包括，所以()()()()()()
()(){}
()()()(){}()()2121212****1212111122221321112121212*1312*2221 G x x x L G L G L G L G L G x L G L G x x x x T S x x T S x x P S S T S S x S x x x x L G L G L G L G x P S S S x x S S x x L G L G L G εωωωεααεε++++=∈?∈=∈?∈?≠→∈???∈?=→→?=→?∈，可知所以 （1）设，不妨设，其中，，，时，由中且，则所以，时，由中时，由，得所以()()()()()
212L G L G L G L G ?=综上，
12(2)()()()L G L G L G =
{}()
{}()()()()()()()()()()()1212121212
3312*
1211*12***312*111 V V S V V G S V V T T P P P S P S S S x L G L G x L G S x
G S x x L G L G L G L G x L G S x P S x S x S x x L G L G L G ααα=??==→→→∈∈??∈?∈????∈?解：
不妨假设，并且，令，，，其中，
或证明：
（1）设不妨设那么可知由构造方法可知，且即（2）设则，由知，或不妨设则，同理()()()()()()()()
21212 L G L G L G L G L G L G L G L G ??=则 所以
{}
12
(3)()(),(),
L G L G a b L G a
=其中，b是两个不同的终极符号
{}
()
{}{}
()
()()
{}
1212
1212123
**
322111
*
212
**
11221122
1212121
(),() ()
V V S V V
G S V V T T P P P S
P S aS bS T S S S
x L G S x S aS x a
T S L G L G
x a L G a b L G b L G
ωωωωαα
ωωω
ωωωω
ωωωω
=??
=
=→∈?→→
∈?→=
∈?∈∈
=∈∈
解：
不妨假设，并且，令
，，，
其中，
其中且
证明：
（1）设则由产生式，不妨设
则，则，
所以同理{}
{}
{}
{}()
{}
2
12
12
**
1211221122
*
31212
12
12
,()
()(),()
(),()
()()
(),()
()(),()
a b L G
L G L G a b L G
x L G a b L G
x a L G L G S S
P S aS a
L G a b L G L G
L G L G a b L G
ωωωωωω
ωωω
?
∈
=∈∈??
??
?
=
可得
（2）设
不妨设其中，即，
由中产生式
所以
综上可得，
*
1
(4)()()
L G L G
=
解：
P={S→α|S1→α∈P1}∪{S→ε}∪{S→αS|S1→α∈P1}
证明略。
1
(5)()()
L G L G+
=
解：
P={S→α|S1→α∈P1}∪{S→αS|S1→α∈P1}
证明略。
******************************************************************************* 12．设文法G有如下产生式：（吴贤珺02282047）S→aB│bA
A →a │aS │bAA
B →b │bS │aBB
证明L(G)＝{ω│ω中含有相同个数的a 和b ，且ω非空}。
证：观察发现A 的产生式A →bAA 中的bA 可以用S 来代替，同样B 的产生式B →aBB 中
的aB 也可以用S 代替。这样原来的文法可以化为如下的形式： S →aB │bA
A →a │aS │SA
B →b │bS │SB
进一步地，可以把产生式A →aS 中的S 代换，把文法化为如下的形式： S →aB │bA
A →a │aa
B │abA │SA B →b │baB │bbA │SB
下面，我们就对字符串ω的长度施归纳，同时证明以下三个命题成立。 ⑴ *?S ωiff ω中含有相同个数的a 和b ，且ω非空。 ⑵ *?A ωiff ω中含有a 的个数比b 的个数恰好多一个。 ⑶ *?B ωiff ω中含有a 的个数比b 的个数恰好少一个。
第一步，由于只有A 和B 可以直接推出终结符，当ω的长度为1时，直接用A 推出a 或直接用B 推出b 。
直接用A 推出a 时，ω中a 的长度为1，b 的长度为0，含有a 的个数比b 的个数恰好多一个。
直接用B 推出b 时，b 的长度为1，a 的长度为0，ω中含有a 的个数比b 的个数恰好少一个。
这样，由S →aB │bA ，知S 推出的最短串，分别是ab 和bb ，其长度是2，并且a 和b 的个数相等。
第二步，假设上面的三个命题对长度为x 的串成立。对S ，x ＝2n(n ≥1)；对A 和B ，x ＝2n ＋1(n ≥0)。我们可以看到，由A 或B 推出的串长度如果要变长的话，必须把A 或B 用其除A →a 或B →b 之外的产生式代替。 i ）.考虑代替A 的情形。
若A 用aaB 代替，由假设B 中a 的个数比b 的个数恰好少一个，则aaB 中a 的个数比b 的个数恰好多一个。
若A 用abA 代替，由假设A 中a 的个数比b 的个数恰好多一个，则abA 中a 的个数比b 的个数恰好多一个。
若A 用SA 代替，由假设A 中a 的个数比b 的个数恰好多一个，而S 中a 和b 的个数相等，则SA 中a 的个数仍然比b 的个数恰好多一个。
ii ）.考虑代替B 情形。
若B 用baB 代替，由假设B 中a 的个数比b 的个数恰好少一个，则baB 中a 的个数比b 的个数也恰好少一个。
若B 用bbA 代替，由假设A 中a 的个数比b 的个数恰好多一个，则bbA 中a 的个数比b 的个数恰好少一个。
若B 用SB 代替，由假设B 中含有a 的个数比b 的个数恰好少一个，而S 中a 和b 的个数相等，则SB 中a 的个数仍然比b 的个数恰好少一个。 这样，命题
*?A ωiff ω中含有a 的个数比b 的个数恰好多一个。 *?B ωiff ω中含有a 的个数比b 的个数恰好少一个。
就得到了证明。又由于S的产生式只有S→aB│bA，由以上两个命题，显然有命题
Sωiffω中含有相同个数的a和b，且ω非空。
*
成立。
形式语言与自动机的发展和在计算理论中的作用 2015060104020王桢 形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构 理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形 式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称 为字母表，用∑表示。又用∑*表示∑中字母组成的所有符号串的集合。∑*的每个子集都是∑上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林在研究神经细跑中，建立 了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能 用O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它 就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数 学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为BNF 范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF 范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。 形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计算机学科里重要的分支。 19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,
形式语言与自动机课后习题答案 第二章 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.给出集合{Φ,{Φ}}和集合{ε,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
计算机专业导论 学生学院____计算机学院_______ 专业班级____ _____ 学号____ _______学生姓名______ _________ 成绩_____________________ 2013年11月30日
专业导论（论文） 在当今世界，几乎所有专业都与计算机息息相关。所以计算机的发明无疑是20世纪最卓越的成就之一。时至今日，计算计的广泛应用极大的促进了生产力的发展，它在当今信息化的社会中已经成为必不可少的工具。 我对计算机及计算机学科体系的理解 实际上，计算机是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和储存的系统。计算机科学是对计算机进行学术研究的传统称谓。主要研究计算技术和执行特定任务的高效算法。该门学科为我们解决确定一个问题在计算机领域内是否可解，如可解其效率如何，以及如何作成更加高效率的程序。时至今日，在计算机科学内已经衍生了许多分支，每一个分支都针对不同类别的问题进行深入研究。 计算机工程学是电子工程的一个分支，主要研究计算机软硬件和二者间的彼此联系。 软件工程学着重于研究开发高质量软件系统的方法学和实践方式，并试图压缩并预测开发成本及开发周期。 信息系统，在一个广泛的有组织环境（商业为主）中的计算机应用。
计算机系统 一个计算机系统包括硬件和软件两大部分。硬件是由电子的、磁性的、机械的器件组成的物理实体，包括运算器、存储器、控制器、输入设备与输出设备等5个基本组成部分。软件则是程序和有关文档的总称，包括系统软件、应用软件和工具软件三类。 硬件系统的五个部分中控制器是指挥计算机的各个部件按照指令的功能要求协调工作的部件，是计算机的“神经中枢”。{控制器的主要特点是采用内存程序控制方式，即在使用计算机时，必须预先编写（或由编译程序自动生成）由计算机指令组成的的程序并存入内存储器，由控制器依次读取并执行}控制器由程序计数器（PC）、指令寄存器（IR）、指令译码器（ID）、时序控制电路以及微操作控制电路等组成。 软件系统包括系统软件、应用软件和工具软件三大类。由于软件的内容非常多，在此只作简单的说明。系统软件是为了对计算机的软硬件资源进行管理、提高计算机系统的使用效率和方便用户的各种通用软件，一般由计算机生产商提供。常用的系统软件有操作系统、程序设计语言翻译系统和实用程序（如驱动程序、连接程序、诊断程序等）。应用软件是专门为某一应用目的而编制的软件系统，常用的应用软件有字处理软件、表处理软件、统计分析软件、数据库管理系统、计算机辅助软件、实时控制与处理软件以及其它应用于国名经济各行的应用程序。工具软件主要包括下载、文件传输协议（FTP）、图像、浏览、截图压缩、防病毒等常用软件。
形式语言与自动机课后作业答案 第二章 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组成的所有字符串的集合
专业导论（论文） 谈谈你对计算机专业的认识及四年学习的设想 学院计算机学院 专业软件工程 年级2007级 姓名李云松 学号3107006836 教师傅秀芬 2007年12月12日 广东工业大学计算机学院制
专业导论论文 计算机的发明是20世纪最卓越的成就之一。计算计的广泛应用极大的促进了生产力的发展，它在当今信息化的社会中已经成为必不可少的工具。 什么是计算机 实际上，计算机是一种能够按照事先存储的程序，自动、高速地对数据进行输入、处理、输出和储存的系统。一个计算机系统包括硬件和软件两大部分。硬件是由电子的、磁性的、机械的器件组成的物理实体，包括运算器、存储器、控制器、输入设备与输出设备等5个基本组成部分。软件则是程序和有关文档的总称，包括系统软件、应用软件和工具软件三类。 计算机硬件系统 下面简单介绍一下硬件系统的5个部分。 硬件系统的五个部分中控制器是指挥计算机的各个部件按照指令的功能要求协调工作的部件，是计算机的“神经中枢”。{控制器的主要特点是采用内存程序控制方式，即在使用计算机时，必须预先编写（或由编译程序自动生成）由计算机指令组成的的程序并存入内存储器，由控制器依次读取并执行}控制器由程序计数器（PC）、指令寄存器（IR）、指令译码器（ID）、时序控制电路以及微操作控制电路等组成。 运算器是对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令，完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算。运算器由算术、逻辑部件（ALU）、寄存器等组成。 存储器是用来存储数据和程序的部件。由于计算机的信息都是以二进制形式表示的，所以必须使用具有两种稳定状态的物理器件来存储信息。根据功能不同，存储器一般可分为内存储器和外存储器两种类型。内存储器（又称为主存储器，又称为内存或主存）用来存放现行程序的指令和数据，具有存取速度快、可直接与运算器及控制器交换信息等特点，但其容量一般不大。外存储器（又称为辅助存储器，简称为外存或辅存）用来存放需要长期保存的信息。其特点是存储容量大、成本低。不能直接和运算器、控制器交换信息，需要时可成批的和内存储器交换信息。外存储器主要有软磁盘、硬磁盘以及光盘等。
形式语言与自动机理论试题答案解析 一、按要求完成下列填空 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
《编译原理》课程论文 编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。从功能上讲，一个编译程序就是一个语言翻译程序。语言翻译程序把一种源语言书写的程序翻译成另一种目标语言的等价程序，所以总的说编译程序是一种翻译程序，其源程序是高级语言，目标语言程序是低级语言。 编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成几个阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程是词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。 编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机工作者的职业生涯中，本书中的原理和技术都会反复用到。在这本书中，向我们介绍了文法的概念，在讲词法分析的章节中讲述了构造一个有穷自动机的方法，以及如何将一个不确定的有穷自动机转化成确定的有穷自动机和有穷自动机的最小化等方法。 词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。 词法分析中的重点是有穷自动机DFA的生成以及DFA和正规式与正规文法的关系。还要熟练掌握NFA转换为DFA的方法及DFA的化简。 词法分析的核心应该是构建DFA，最后维护一个状态转移表。通过转态转移的结果来识别词性。DFA的思想和字典树很像。NFA通过求每个状态的闭包后构造出的自动机与DFA等价。正则表达式闭包，连接，或三种操作都有相应的NFA与其等价。所以正则表达式==NFA==DFA。DFA状态最小化算法化简DFA。LL(1)文法主要就是根据FIRST集判断向哪条路径走，来避免回溯；LR(0)文法构造项
专业导论（论文） 学院计算机学院 专业 班级 姓名 学号 2012年11月27日 广东工业大学计算机学院制
我对所学专业的认识及我大学四年的规划与设想 对计算机及计算机科学体系的理解 计算机 现代社会快速发展，计算机已经走进千家万户，越来越普及。并且它在日常生活以及工业方面发挥的作用越来越大。在诞生初期，计算机主要是用来科学计算。如今，它快速发展，可以对数字、文字、图形、图像及声音等进行处理。 计算机是一种能够按事先存储的程序，自动、高速地对数据进行输入、处理、输出和存储的系统。计算机由运算器、存储器、控制器、输入和输出设备五大部分组成。以上为硬件部分，还有软件，软件则由系统软件、应用软件和工具软件三大部分组成。 计算机的发展非常迅速。最初的计算机是电子管计算机，然后由电子管计算机发展成晶体管计算机，进而发展成大规模和超大规模的集成电路计算机。 计算机具有如下特点：1.运算速度快2.运算精度高3.具有记忆力4.具有逻辑判断力5.存储程序。 计算机的用途：1.科学计算2.数据处理3.实时监控4.人工智能5.计算机辅助工程和辅助教育6.娱乐和游戏等。 计算机学科体系 计算机学科体系包含了计算机理论、硬件、软件、网络及应用等领域。计算机理论的研究内容：1.离散数学 2.算法分析理论 3.形式语言及自动机理论4.程序设计理论语言5.程序设计方法学。计算机硬件的研究内容：1.元器件与存储介质 2.微电子技术 3.计算机组成原理 4.微型计算机技术 5.计算机体系结构。计算机软件的研究内容：1.程序设计语言的设计 2.数据结构与算法 3.程序
设计语言翻译系统 4.操作系统 5.数据库系统 6.算法设计与分析7.软件工程学8.可视化技术。计算机网络的研究内容：1.网络结构2.数据通信与网络协议3.网络服务 4.网络安全。计算机应用的研究内容：1.软件开发工具 2.完善既有的应用系统3.开拓新的应用领域4.人——机工程。 计算机科学体系中包含了大量的内容，各部分内容看似互不关联，实际上却是联系在一起的。由于它的领域太广泛，所以我们要学懂各个部分，然后专门深入研究某一领域的应用。 只有这样，我们才能有自己的专长，并且对其他方面也有了解,日后才能更好地找到工作。 计算机系统 硬件 计算机由五大部分组成。其中控制器和运算器是核心部分，成为中央处理器，简称CPU。对于微型机，其系统由系统单元、输入输出系统、输入设备、输出设备和辅助存储设备组成。 微型计算机的系统单元包括：系统主办与时钟频率、电子数据与指令、微处理器、主存储器。 系统主板又称底板或母板，它是整个计算机系统的通信网，系统单元的每个元器件直接连接到系统主板，它们通过系统主板进行数据的交换。 系统时钟用于控制计算机操作的速度，这个速度用兆赫（MHz）表示。 微处理器接收来自各种输入设备的数据，并处理、输出这些数据。微处理器具有两个基本部件：控制单元和算术/逻辑单元。 主存储器又称为内存储器或内存，是指能够通过指令中的地址直接访问的存储器，它被用来存储正在被CPU使用的程序和数据。
西安交通大学计算机硕士培养方案
西安交通大学 《计算机科学与技术》学科攻读硕士学位研究生 培养方案 一、培养目标 1．培养德、智、体全面发展，具有强烈的社会责任感、能为社会主义市场经济和现代化建设服务的高级科学技术专门人才。 2．在计算机科学与技术领域具有坚实的理论基础和系统的专门知识，具有较强的综合分析和独立解决实际问题的能力以及从事科学技术研究、教学及开发应用的能力。 3．具有求实严谨的科学态度，为科学事业勇于创新的精神以及团结协作的团队作风。 二、学科设置 计算机科学与技术为一级学科，下设三个二级学科：“计算机系统结构”、“计算机软件与理论”、“计算机应用技术”。硕士研究生按一 级学科培养。 三、研究方向 本专业目前有下列研究方向： 1.高性能计算机系统 2.计算机网络 3.分布式系统与中间件技术 4.数据库系统 5.信息与网络安全技术 6.人工智能与智能计算机系统 7.程序设计语言的理论与实现 8.面向对象的软件开发方法和技术 9.数据挖掘与知识发现 10. 基于Internet的信息处理系统 11. 多媒体技术与科学计算可视化 12. 人机交互技术 13. 计算机模拟仿真 四、培养方式 1．为了保证硕士生新生入学时教学计划及时执行，在研究生录取工作结束后、研究生进校之前，由导师先制订硕士生第一学期的选课 计划。原则上第一学期（秋上）的课程均为学位课；硕士生进校后1 周内由导师与硕士生共同商定制订全面培养计划。 2. 对硕士生的培养采取课程学习和论文工作并重的方式，论文工作时 间不得少于一年。 3. 整个培养过程应贯彻理论联系实际的方针，使硕士生掌握本专业的
信息学院本科指导性教学计划(公共课) 第一学年秋季学期 课号课程名学 分 周 学 时 考试或 考查 说明及主要先修课 1061002 2 思想道德修养 2 2 考查 1064043 3 英语选修 2 2 考查 1042087 4 一元微积分 4 4 考试 1042068 4 几何与代数（1） 4 4 考试 20240013 离散数学（1） 3 3 考试 20230093 计算机语言与程序 计 3 3 考试 30250023 计算机语言与程序 计 3 3 考试 30240233 程序设计基础 3 3 考试四选一 3410006 3 程序设计基础 3 3 考试 30210041 信息科学技术概论 1 1 考查 春季学期 00501622 毛泽东思想概论 3 2 考试 1064044 3 英语选修 2 2 考查 1042088 4 多元微积分 4 4 考试一元微积分 1042069 2 几何与代数(2) 2 2 考试几何与代数(1) 二选一 1042091 3 几何与代数(2) 3 3 考试几何与代数(1) 1043048 4 大学物理B(1) 4 4 考试一元微积分 1043034 4 大学物理 (1)(英) 4 4 考试一元微积分三选一 1043052 5 大学物理A(1) 5 5 考试一元微积分 2022021 4 电路原理 4 4 考试 2022022 1 电路原理实验 1 1 考查
第二学年秋季学期 课号课程名学 分 周 学 考试或 考查 说明及主要先修课 10420753 高等微积分 2 2 考试一元微积分 10420252 复变函数引论 2 2 考试一元微积分二选一复变函数 3 3 考试一元微积分 10430535 大学物理A(2) 5 5 考试大学物理A(2) 20250093 电子技术基础 3 3 考试电路原理二选 一 30230563 数字逻辑电路 3 3 考试电路原理 电子技术基础实验 2 2 考查跨学期课，本学期完成1学分10420262 数理方程引论 2 2 考查不修该课程 20130342 工程图学基础 2 2 考试 春季学期 10420243 随机数学方法 3 3 考试二选一 10420803 概率论与数理统 计 3 3 考试 数字逻辑电路 3 3 考试电路原理电子技术基础 电子技术系列实 验 2 2 考查跨学期课，本学期完成1学分30230104 信号与系统 4 4 考试微积分电路复二选一40250144 信号与系统分析 4 4 考试变几何与代数 40240013 系统分析与控制 3 3 考试微积分电路复二选一40250074 自动控制理论(1) 4 4 考试变几何与代数 3025 数据结构 3 3 考试四选一34100044 数据结构与算法 4 4 考试 微电子学导论 3 3 考试 半导体器件与集成 电路 3 3 考试三选一 集成电路原理与设 计 3 3 考试 物理、生物类课程≥ 2 2 20240023 离散数学（2）（选）3 3 考试 夏季学期 电子技术课程设计 3 3 考查电子技术基础 Java语言（选） 2 2 考查计算机语言与程序设计二选一 语言（选） 2 2 考查计算机语言与程序设计
编译原理心得 编译原理是计算机及相关专业的一门重要专业课程，在计算机科学中有很重要的地位和作用，已被国内外高校列为计算机专业的主要课程。它主要介绍了高级程序设计语言编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具。通过该课程的学习，对提高学生计算机软件素质，使学生真正认识计算机信息处理实质并综合运用所学的软件设计技术来分析问题等具有很大作用。 该课程理论性与实践性都很强，我们在学习是普遍感到内容非常抽象，不易理解，内容多且繁琐，难以完整、全面地掌握编译原理的有关知识，更不用说灵活运用编译原理知识从事相关设计或应用于其他领域。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对我们提供了系统而有效的训练，有利于提高软件人员的素质和能力。 采用有用的资助手段增强课堂教学效果。基于Internet网络和多媒体技能，资助手段有种种千般的情势，可以借用有：讨论学习模式、探索学习模式、提供种种资源库的网上资助教学应用模式。在Internet上实现讨论学习的要领有多种，最简略实用的是使用现有的电子通告牌体系（BBS）,这种体系具有用户管理、讨论管理、文章讨论、实时讨论，用户留言、电子信件等诸多功效。编译原理在学习历程，门生题目难点不能逐一与老师举行面临面举行，那末议决网络，可以题目果然，老师创建相应的主题，门生可以在自己学习的特定地域发言，门生之间可以举行交换，全部的题目都果然化。 探索学习模式。这种模式一样平常都是由某些教诲机构设立一些适当特定门生工具的题目，议决Internet向门生公布，要求门生解答；同时提供大量的、与题目相干的信息资源供门生在解决题目历程中查阅。这种模式彻底转变了传统教学历程中门生被动继承的状态，而使门生处于积极自动的职位地方，因而能有用地引发门生的学习兴趣和创造性。 在我们学习编译原理以前，都认为编译原理只能应用在写程序语言的编译器上,觉得用处不大,学习兴趣不高。而在后来的学习中，我们逐渐认识到计算机专业的学生，除了要会编写程序语言之外，还应该了解它是如何被计算机所识别，这才是真正并且透彻地学习软件。另外，编译器中每一个模块的编写，都能对我们的编程能力的提高有很大帮助。在今后若从事软件工程，这门课程也能够对编写程序有所帮助。 为了能够系统掌握这门专业课，我们把编译原理分为以下几个模块：（1）语言和文法；（2）词法分析；（3）语法分析；（4）语义分析和中间代码生成；（5）代码优化和目标代码生成；（6）关于实践。 在学习的开始，我们需要掌握什么是编译，编译分为哪些阶段，编译程序和解释程序的区别等等。在做好了这些方面的准备后，开始了系统的学习。 语言和文法 语言和文法部分的知识包括文法基本概念及文法的二义性。基本概念有文法定义、推导、句型、句子等等。二义性文法是通过画语法树的方法来证明。 词法分析 词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编
软件工程（一级学科）专业 博士生培养方案 一、培养目标 培养适应建设有中国特色社会主义需要的、热爱祖国、遵纪守法、德智体全面发展、具备严谨科学态度和敬业精神的软件工程专业人才。通过博士阶段的学习，具有软件工程学科内全面而扎实的基础理论知识，有一定的独立见解，教学、科学及组织能力较强，掌握某一方向的最新技术，能较好地从事该方向的教学、科研与开发工作。学位论文应具有一定的创造性或较大的应用价值。 二、研究方向 本学科博士生的培养主要包括软件工程理论与方法、软件工程技术、软件服务工程、领域软件工程等专业领域。研究方向包括：（1）复杂软件理论与自动化（2）软件分析与测试技术（3）分布式软件与领域工程（4）形式化方法与技术（5）领域软件工程与信息系统（6）网构软件与服务工程（7）软件自适应（8）软件测试技术与过程管理（9）社会网络技术（10）软件数据挖掘等。 三、招生对象 通过学校组织的博士生人数考试招收合格的博士生源有： 1．应届硕士毕业生 2．提前攻博硕士生 3．往届硕士或同等学历 四、学习年限 1．一般情况下，学习年限为四年 2．特别优秀者可适当提前 3．来不及完成博士论文者可适当延长 五、课程设置 现代科学技术革命与马克思主义 第一外语 第二外语 软件工程方法与技术进展 软件自动化 软件工程改进 软件可靠性方法 先进操作系统 经验软件工程方法 软件形式化方法 软件需求工程 机器学习与数据挖掘 多媒体技术进展 六、培养方式 博士生招生录取时明确导师，由导师负责成立指导小组，制定培养计划。由博士生导师和培养小组负责全部培养工作。 公共课以讲授为主，辅以自学。根据研究方向和科研工作的需要，选读若干门专业选修课。专业课以讲授、自学、讨论相结合的形式，要求博士生阅读有关的专业文献，参加讨论班、学术报告等各种学术活动。
第一章参考答案 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 请用命题法给出下列集合
电梯建模 姓名：*** 学号：******** 班级：***** 引文：自然语言描述对电梯系统的要求：在一幢m层的大厦中需要一套控制n部电梯的产 品，要求这n部电梯按约束条件c1，c2和c3在楼层间移动。对此要求进行建模。 一、电梯按钮 C1：每部电梯内有m个按钮，每个按钮代表一个楼层。当按下一个按钮时该按钮指示灯亮，同时电梯驶向相应的楼层，到达相应的楼层时指示灯熄灭。 C2：除了大厦的最底层与最高层之外，每层楼都有两个按钮分别请求电梯上行和下行。这两个按钮之一被按下是相应的指示灯亮，当电梯到达此楼层时灯熄灭，电梯向要求的方向移动。 C3：当对电梯没有请求时，它关门并停在相应的楼层。 现在使用一个扩展的有穷状态机对本产品进行规格说明。这个问题中有两个按钮集。N部电梯中的每一部都有m个按钮，一个按钮对应一个楼层。因为这m*n个按钮都在电梯中，所以称他们为电梯按钮。此外，每层楼有两个按钮，一个请求向上，另一个请求向下，这些按钮称为楼层按钮。 电梯按钮的状态转换图 令EB(e,f)表示按下电梯e内的按钮并请求到f层去。EB(e,f)有两个状态： EBON(e,f)：电梯按钮（e,f）打开 EBOFF(e,f)：电梯按钮（e,f）关闭 如果电梯按钮（e,f）发光且到f层，该按钮将熄灭。相反如果按钮熄灭，则按下它时，按钮将发光。上述两个描述中包含了两个事件，它们分别是： EBP(e,f)：电梯按钮（e,f）被按下 EBP(e,f)：电梯e到达f层 为了定义这些事件和状态相联系的状态转换规则，需要一个谓词V(e,f)，它的含义如下： V(e,f)：电梯e停在f层 如果电梯按钮（e,f）处于关闭状态【当前状态】，而且电梯按钮（e,f）被按下【事件】，而且电梯e不再f层【谓词】，则该电梯按钮打开发光【下个状态】。状态转换的形式化描述如下：EBOFF(e,f)+EBP(e,f)+notV(e,f)=>EBON(e,f) 反之，如果电梯到达f层，而且电梯按钮是打开的，于是它就会熄灭。这条转换规则可以形式化描述为： EBON (e,f)+EAF(e,f) =>EBOFF(e,f) 二、楼层按钮 令FB（d,f）表示f层电梯向d方向的按钮，如图：