LTE引理

无论命题还是证明。本文证明它并给出它的一些应用。

如何求一个奇素数p在a^n-b^n中的次数。这个引理的证明是完全初等的而且对一般竞赛生不难理解。我们记v[p](n)为p在n中的次数，。或者说如果v[p](n)=a则p^a|n但把a换成更大的就不行。如果n不是p的倍数，v[p](n)=0

容易知道v[p](ab)=v[p](a)+v[p](b)以及v[p](a+b)≥min{v[p](a),v[p](b)}先证明两个小引理（这两个引理中p都是奇素数）

1.如果p|x-y，(p,n)=1，(p,x)=1，那么

v[p](x^n-y^n)=v[p](x-y)

由于x^n-y^n=(x-y)(x^(n-1)+x^(n-2)y+…+y^(n-1))

而在mod p意义下，由于x=y，有

x^(n-1)+x^(n-2)y+…+y^(n-1)=n*x^(n-1)≠0

（每个加项相同，共n项）

因此v[p](x^(n-1)+x^(n-2)y+…+y^(n-1))=0

因此v[p](x^n-y^n)=v[p](x-y)+v[p](x^(n-1)+x^(n-2)y+…+y^(n-1))=v[p](x-y)

2.如果p|x-y，(p,x)=1，那么

v[p](x^p-y^p)=v[p](x-y)+1

假设x=y+k*p^a，其中(k,p)=1，则a=v[p](x-y)

x^p-y^p=(x+k*p^a)^p-x^p

=(x^p+p*x^(p-1)*k*p^a+C(p,2)*x^(p-2)*k^2*p^(2a)+C(p,3)*x^(p-3)*k^2*p^(3a)+…)-x^p

=p^(a+1)*x^(p-1)*k+S

容易验证S的每一项都是p^(2a+1)的倍数

所以这个数是p^(a+1)的倍数但不是p^(a+2)的倍数（S是但p^(a+1)*x^(p-1)*k不是）

故v[p](x^p-y^p)=a+1=v[p](x-y)+1好了，下面献上LTE引理：

如果p是奇素数，p|x-y，(p,x)=1，那么

v[p](x^n-y^n)=v[p](x-y)+v[p](n)

不断把n中的因子p搬到外面变成+1，搬完了就证完了。。。

对于n是奇数，我们还有

v[p](x^n+y^n)=v[p](x+y)+v[p](n)

这是通过把y理解成-y得到的

p=2的情况没啥用处，就不搬运了。。。应用

1.求所有正整数n使得存在正整数x,y,k满足(x,y)=1,k>1使得3^n=x^k+y^k

解答

如果k是偶数，由于x^k和y^k mod 3都是1或0，所以都是0，这与(x,y)=1矛盾

如果k是奇数，则v[3](x^k+y^k)=v[3](k)+v[3](x+y)=v[3](k(x+y))

因此x^k+y^k≤k(x+y)（左边完全是3的幂次，右边还可能有别的），

x^(k-1)-x^(k-2)y+...+y^(k-1)≤k (1)

显然x≠y，不妨设x>y，则

x^(k-1)-x^(k-2)*y=x^(k-2)(x-y)≥x≥2

x^(k-3)-x^(k-4)*y=x^(k-4)(x-y)≥x≥2

总之就是把(1)的前k-1项两两配对，每一对的和都不小于2

又y^(k-1)≥1,全加起来就至少是项数k

而且如果x≥3或者k>3，等号就取不到

因此x=2,y=1,k=3验证知此时n=2

2.已知p是一个奇素数，正整数x,y,m>1，证明：如果(x^p+y^p)/2=((x+y)/2)^m，则m=p

解答

由幂平均不等式m≥p

假设(x,y)=d,x=du,y=dv

则(u^p+v^p)/2=d^(m-p)*((u+v)/2)^m

任取u+v的素因子q

如果q为奇数

则v[p]((u^q+v^q)/2)=v[q](u+v)+v[q](p)≤v[q](u+v)+1≤2v[q](u+v)

而m≥p≥3，有

v[q](d^(m-p)*((u+v)/2)^m)≥v[q](((u+v)/2)^m)=m*v[q](u+v)

矛盾！

如果q只能为2，u+v就是2的幂次，假设u+v=2^a

由于(u,v)=1，u,v均为奇数

又u^(p-1)-u^(p-2)v+…+v^(p-1)共p项，为奇数

有v[2]((u^p+v^p)/2)=v[2]((u+v)/2)=a-1

又v[2](d^(m-p)*((u+v)/2)^m)≥v[2]((u+v)/2)^m)=m(a-1)

因此a=1，u=v=1，这说明x=y，进而m=p

3.求x^2009+y^2009=7^z的全部正整数解

解答

由费马小定理7|(x^2009+y^2009)-(x+y)，故7|(x+y)

故v[7](x^2009+y^2009)=v[7](2009)+v[7](x+y)=v[7](49(x+y))

因此x^2009+y^2009=7^v[7](x^2009+y^2009)=7^v[7](49(x+y))≤49(x+y)

（显然p^v[p](x)≤x）

而不等式x^2009+y^2009≤49(x+y)在x,y不全等于1时显然不成立

而且x=y=1也不成立

因此，无解

4.求所有正整数a使得对所有正整数n，4(a^n+1)是完全立方数

解答

a=1显然可以

若a>1，则a为奇数（偶立方数都是8的倍数）

所以a^2+1是4k+2型数，有一个奇素因数p

假设v[p](a^2+1)=3k

那么v[p](4(a^(2p)+1))=3k+1

这不可能（由于立方数对所有素数的次数都是3的倍数）话说此题还有一个很神奇的做法：如果a>1，(4(a^9+1))/(4(a^3+1))=a^6-a^3+1可以被夹在两个相邻立方数之间……练习题

1.求所有正整数a,b>1使得a^b|b^a-1

2.求(n-1)!+1=n^m的正整数解(n,m)

3.是否存在正整数n使得n|2^n+1且n有恰好10086个素因数

4.实数a,b满足若对所有正整数n，a^n-b^n是整数，证明a,b都是整数

5.正整数a>b>1和n满足b是奇数和a^n|b^n-1，证明：a^b>3^n/n

6.求所有正整数n，使得n^2|2^n+1

7.给定正整数u>1，证明：至多存在有限个三元正整数组(n,a,b)满足n!=u^a-u^b

(1)设p为奇素数，整数a,b均不能被p整除

a-b恰能被p^k整除，k为正整数

n恰能被p^m整除，m为非负整数

则a^n-b^n恰能被p^(m+k)整除

（2）设a,b为奇数，a-b恰能被2^k整除，k为大于1的正整数

n恰能被2^m整除，m为非负整数

则a^n-b^n恰能被2^(m+k)整除

秒杀题目有：

1,求所有正整数n,使得n^2整除2^n+1(31届IMO第3题)

2,求所有正整数n,p,其中p为素数，n^(p-1)整除(p-1)^n+1(40届IMO第4题)

3,已知正整数m,n,k满足3^m,3^n,3^k模10000同余，且m,n,k可以构成三角形三边长，求m+n+k最小值

5,（原创题）：求所有正整数x,y,使x^y整除y^x+1

6,(原创题）：求所有正整数x,y,使x^y整除y^x-1

7,（原创题）:求所有正整数a,使得存在无限多个正整数n,使得n^2整除a^n+1

Rules:

1) Use for typing.

2) Use sum and product notations whenever you can in place of informal ellipses . Use proper indices, cyclic/symmetric notation whenever applicable.

3) Number your results.

4) Name your results if possible.

5) Check previous results to prevent repetition. State special cases or generalizations.

6) Place an empty line between the end of a result and the beginning of another result if you have multiple results in a post.

7) State the domain of your results.

8) Derivations are not necessary as they are mostly intuitive, but go ahead if you want. Hide any posted derivations though.

In general try to stick to non-complex number identities because this is meant for elementary purposes. Also, minimize geometry, combinatorics, number theory, etc. results. Algebra only!

I'll start off with some common ones:

Result 1. - Difference of same powers

for non-negative integers and all reals .

Result 2. - Sum of same odd powers

for non-negative integers and all reals . Result 3. - Special Case of Result 1. - Difference of squares

for all reals .

Result 4. - Special Case of Result 1. - Difference of cubes

for all reals .

Result 5. - Sum of Squares - Different representations

for all reals .

Result 6.

for all reals . Result 7.

for all reals . Result 8.

for all reals .

Result 9.

for all reals .

Result 10.

for all reals .

Result 11.

for all reals .

Result 12.

for all reals .

If you're wondering what else to post, there are the Binomial and Multinomial Theorems for integer exponents, their numerous special smaller cases, The Sophie Germain Factorization and so many more! Have fun.

One we reach a significant number of Results, I will put them into a PDF (with credits given to the respective posters of course) and post it here and in the Olympiad Articles forum.

Note to everyone: If you got a Result specifically from a source like a book, file, person, etc, please give your source credit.

P.S. This is not a thread to collect nice or classical or useful inequalities. This is only for algebraic manipulations, factorizations and such.

Result 13.

for all reals

Result 14.

for all reals

Result 15.

for all reals

Result 16.

for all reals

Result 17.

f or all reals

Result 18.

for all reals

Result 19.

for all reals

Result 20.

for all reals

Result 21.

for all reals

Result 22.

for all reals

Result 23.

for all reals

Result 24.

for all

reals

Last edited by 123steeve on Jul 07, 2011, 9:51 am, edited 3 times in total.

Method of Lagrange for root within another root:

Let this be

Result 24,5

Source: Algebra class

95% of professing Pastafarian teens won't stand up for The Flying Spaghetti Monster. If you are one of the 5% who will, please copy and paste this into your signature.

Last edited by Markomak1 on Jun 09, 2011, 8:01 pm, edited 2 times in total.

Result 25

for all

real

Result 26

for all real

Result 27

for all real

Result 28

for all real

Result 30

tbh I don't really know how that could be remotely useful. You might see it once in like every 12387198739136518742687632

problems, who knows? I just saw and decided to generalize it.

Result 31

Not sure if this one deserves to be called a "result" as it's kind of just a special case of #24. Due to the "-1" at the end, it would

be more applicable to, say, if you were trying to solve a diophantine equation via factoring, where you could just "make" the

necessary "-1" on both sides.

#31 was from a problem by Titu Andreescu:

Find all pairs (x,y) of integers such that(Titu Andreescu)

Result 32.

Result 33

Result 34

-Sophie Germain

What about substitutions? Like:

Result 35

Result 36

for all

reals .

Result 37

for all reals .

Result 38

for all reals .

Result 39: "Lagrange's Identity"

for all reals

Result 40.

, for .

Result 41.

for if and only if one or both of the following conditions are

true: .

Pages 26-29 of Secrets in Inequalities - Volume 2 - Advanced Inequalities by Pham Kim Hung, published by GIL, has some great factorizations. I might post them sometime, but not before I am comfortable with all of them. Anyone else may feel free to post them, since you can't put a copyright on mathematical identities... I think.

Some Substitutions:

Result 42.

for .

Result 43.

If are the sides of a triangle, the identity or inequality can be transformed

to , where . The converse is also true.

(This is somewhat related to geometry, but it allows one to brute-force proof a geometric inequality with algebraic technniques that hold for postiive reals instead of the inconvenient sides of a triangle).

Result 44.

Result 45.

Should be:

Result31:

Moderator Edit:Result 32.

Should be:

Result32

Result 56.

Result 57.

The maximum of

is . Result 58

Result 59

Result 60

Result 61

A useful substitution

Result 62

Result 63

Result 64

Result 65

Result 66

Result 67 :

-

越南数学家Ngo Bao Chau证明的一个基本引理被《时代》杂志列为2009年度十大科学发现

过去三十年相关领域的数学家一致期望Langlands Program中的一个基本引理会被证明的确是精确的。Ngo Bao Chau一位在法国Université Paris-Sud 和普林斯顿Institute for Advanced Study (IAS) 工作的越南数学家（1972年生于越南河内），证明了这一引理，2009年相关领域的数学家验证了他的证明。这一结果被《时代》杂志列为2009年度十大科学发现的第七项。 The Fundamental Lemma, Solved ?????? In 1979 the Canadian-American mathematician Robert Langlands developed an ambitious and revolutionary theory that connected two branches of mathematics called number theory and group theory. In a dazzling set of conjectures and insights, the theory captured deep symmetries associated with equations that involve whole numbers, laying out what is now known as the Langlands program. Langlands knew that the task of proving the assumptions that underlie his theory would be the work of generations. But he was convinced that one stepping stone that needed confirmation — dubbed the "fundamental lemma" — would be reasonably straightforward. He, his collaborators and his students were able to prove special cases of this fundamental theorem. But proving the general case proved more difficult than Langlands anticipated — so difficult, in fact, that it took 30 years to finally achieve. Over the past few years, Ngo Bao Chau, a Vietnamese mathematician working at Université Paris-Sud and the Institute for Advanced Study (IAS) in Princeton, formulated an ingenious proof of the fundamental lemma. When it was checked this year and confirmed to be correct, mathematicians around the globe breathed a sigh of relief. Mathematicians' work in this area in the last three decades was predicated on the principle that the fundamental lemma was indeed accurate and would one day be proved. "It's as if people were working on the far side of the river waiting for someone to throw this bridge across," says Peter Sarnak, a number theorist at IAS. "And now all of sudden everyone's work on the other side of the river has been proven." ? 《时代》杂志列为2009年度十大科学发现 1.??????? Our Oldest Ancestor, "Ardi" 2.??????? The Human Epigenome, Decoded 3.??????? Gene Therapy Cures Color Blindness 4.??????? A Robot Performs Science 5.??????? Breeding Tuna on Land 6.??????? Water on the Moon 7.??????? The Fundamental Lemma, Solved 8.??????? Teleportation! 9.??????? The Large Hadron Collider, Revived 10. ?A New Planet (or Brown Dwarf?) Discovered

可计算性与计算复杂性计算原理答案.doc

1.6 画出识别下述语言的DFA 的状态图。 a){w | w 从1开始以0结束} b){w | w 至少有3个1} c) {w | w 含有子串0101} d) {w | w 的长度不小于3，且第三个符号为0} e) {w | w 从0开始且为奇长度，或从1开始且为偶长度} 或

f) {w | w 不含子串110} g) {w | w 的长度不超过5} i){w | w 的奇位置均为1} j) {w | w 至少含有2个0，且至多含有1个1} k) {ε,0} 0,1 1

l) {w | w 含有偶数个0，或恰好两个1} m) 空集 n) 除空串外的所有字符串 1.29利用泵引理证明下述语言不是正则的。 a. A 1={0n 1n 2n | n ≥0}。 证明：假设A 1是正则的。设p 是泵引理给出的关于A 1的泵长度。 令S=0p 1p 2p , ∵S 是A 1的一个成员且S 的长度大于p ，所以泵引理保证S 可被分成3段S=xyz 且满足泵引理的3个条件。根据条件3，y 中只含0，xyyz 中，0比1、2多，xyyz 不是A 1的成员。违反泵引理的条件1，矛盾。 ∴A 1不是正则的。 b. A 2={www | w ∈{a,b}*}. 证明：假设A 2是正则的。设p 是泵引理给出的关于A 2的泵长度。 令S=a p ba p ba p b, ∵S 是A 2的一个成员且S 的长度大于p ，所以泵引理保证S 可被分成3段S=xyz 且满足泵引理的3个条件。根据条件3，y 中只含a ，所以xyyz 中第一个a 的个数将比后两个a 的个数多，故xyyz 不是A 2的成员。违反泵引理的条件1，矛盾。 ∴A 2不是正则的。

发老师东华大学研究生考试试卷格式(A)答案

东华大学 2012~ 2013学年第一学期研究生期末考试试题参考答案 和评分标准 考试学院：计算机 考试专业：计算机科学与技术 考试课程名称：计算理论导引与算法复杂性 一、单项选择题（每空2分，本题共20分） 1. DFA和NFA的区别在于（B ）。 A、NFA能够识别的语言DFA不一定能够识别 B、对同一个输入串两者的计算过程不同 C、DFA能够识别的语言NFA不一定能够识别 D、NFA比DFA多拥有一个栈 2. 若一个语言A是非正则的，对于个给定的一个泵长p,若存在一个串s=xyz,|s|≥p，则 （A ）。 A、|y|可能大于等于0 B、xz∈A C、xyyz∈A D、|xy|不可能小于等于p 3. 下推自动机与图灵机的不同之处是( B )。 A、下推自动机比图灵机识别的语言多 B、下推自动机比图灵机识别的语言少 C、下推自动机识别的语言是不可判定 D、拥有一个无限的存储带 4. 如果一个语言是图灵可判定的，则（A）。 A、对于一个不属于它串s，图灵机计算s时，一定能够到达拒绝状态 B、对于一个不属于它串s，不一定有一个判定器判定s C、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态 D、对于一个不属于它串s，图灵机计算s时，一定不会停机 5. 一个集合在条件（ C ）下是不可数的。 A、该集合为无限集合 B、组成该集合的元素是实数 C、该集合的规模大于自然数集合的规模 D、该集合是一个有限的集合 6. 对于一个语言，（C ）的说法是正确的。 A、如果它属于Turing-recognizable，那么，一定属于EXPTIME B、如果它是NP-hard，那么，一定属于NP C、如果它是NP-complete，那么，一定属于NP D、它一定能被图灵机识别

零基础数学学高数的方法

零基础数学学高数的方法 零基础数学学高数的方法1、数学基础要打牢 mba数学考试不像高考更不像奥数，要考察某一知识点的延伸，通过研究近几年的真题可以发现，试卷中的大多数题目都是对大纲知识点的直接考察。所以大家一定要把基础打牢，不要盲目追求深度，力争把基础分都拿到。如果连基础分都拿不到，难度分再没搞利索，那就得不偿失了。 那么如何打好数学基础呢?首先要通读教材，整理出大纲要求的知识点，形成知识网络，便于记忆;其次是深究各个知识点，对定义及用法着重分析。最后是对知识点进行融会贯通，通过做习题来巩固。 2、不同阶段，习题量应有所调整 一提起数学，很多人就会想起题海战术，题是需要做，但什么时候做，做多做少都是有讲究的。刚开始复习，基础又不是很好，应该以理论理解为主，先把相关概念弄清楚，可以用少量的习题来辅助理解。习题的选择也要注意，选择一些有针对性的习题来做，真正做到一个题消化一个知识点。 切忌一开始就以做题为主，不但会经常做错，打击信心，还得不到效果，浪费大量的时间。基础打牢之后习题就要多做了。通过做大量的习题来消化和巩固知识点，了解试题考查的维度，熟悉出题规律，另外，还要注意锻炼答题速度。在保证准确性的

基础上，还要提高速度，确实不是一件容易的事，必须通过大量的练习来实现。 3、合理规划复习时间并严格执行有的小伙伴们特别随便......没有一个严格的学习计划，想学了就学点......不想学就就去干别的......甚至学着后面的望着前面的......还有的考生复习之前有一个计划，但一到真正实施就管不住自己了，总是不能保质保量的完成任务。当然，我们也不建议完全脱产学习，但不对自己残忍就是对竞争对手的仁慈，要用对待阶级敌人的态度对待学习任务。 4、心态(老话长谈，但一定要说) 现在大家工作生活上的压力都比较大，每个人在mba复习过程中都会遇到一些困难，情绪上也会出现波动。适当聊聊天喝喝茶散散步是百试不爽的，实在没人聊可以找加油菌，总之要把自己的负面情绪发泄出来。 零基础数学学高数的技巧一、背数学 我曾经有一位学生数学成绩一塌糊涂，甚至都想放弃数学，去参加不要求数学成绩的院校招生。直至一天他想到“背数学”的学习方法，他写到： 这个技巧是：不懂的问题，直接看解答，先背起来再说。如此一来，一题一般只要5分钟便背下来，从量来看，可以追赶得上成绩好的同学。 各位猜猜看看，从开始背数学后，她的成绩变好了吗?结果是，她的成绩进步神速，高中三年级时，数学模拟考试成绩还进入全国排名，并应届考上东京大学医学院。比她小一岁的弟弟采用了

计算复杂性-第一次作业

计算复杂性第一次作业 周雄(1152220101) March21,2018 题目1: ①对于00010,我们有如下瞬间描述迁移序列: q000010B?0q00010B?00q010B?000q010B?0000q10B?00000q1B?000000q2(接受) ②对于001000,我们有如下瞬间描述序列: q0001000B?0q001000B?00q01000B?000q1000B?0000q100B?00000q10B? 000000q1B?0000000q2(接受) ③对于0010001,我们有如下瞬间描述序列: q00010001B?0q0010001B?00q010001B?000q10001B?0000q1001B?00000q101B? 000000q11B(停机) 题目2: start 题目3: ①对于0011,我们有如下瞬间描述迁移序列: q00011B?Xq1011B?X0q111B?Xq20Y1B?q2X0Y1B?Xq00Y1B?XXq1Y1B? XXY q11B?XXq2Y Y B?Xq2XY Y B?XXq0Y Y B?XXY q3Y B?XXY Y q3B? XXY Y Bq4(接受) ②对于0101,我们有如下瞬间描述序列: q00101B?Xq1101B?q2XY01B?Xq0Y01B?XY q301B(停机) ③对于00111,我们有如下瞬间描述序列: q000111B?Xq10111B?X0q1111B?Xq20Y11B?q2X0Y11B?Xq00Y11B?XXq1Y11B?XXY q111B?XXq2Y Y1B?Xq2XY Y1B?XXq0Y Y1B?XXY q3Y1B?XXY Y q31B（停机）题目4: (1)

变分法简介(简单明了易懂)(可编辑修改word版)

? §1 变分法简介 作为数学的一个分支，变分法的诞生，是现实世界许多现象不断探索的结果，人们可以追寻到这样一个轨迹： 约翰·伯努利（Johann Bernoulli ，1667－1748）1696 年向全欧洲数学家挑战，提出一个难题：“设在垂直平面内有任意两点，一个质点受地心引力的作用，自较高点下滑至较低点，不计摩擦，问沿着什么曲线下滑，时间最短？” 这就是著名的“最速降线”问题（The Brachistochrone Problem ）。它的难处在于和普通的极大极小值求法不同，它是要求出一个未知函数（曲线），来满足所给的条件。这问题的新颖和别出心裁引起了很大兴趣，罗比塔（Guillaume Francois Antonie de l'Hospital 1661-1704）、雅可比· 伯努利（ Jacob Bernoulli 1654-1705）、莱布尼茨（ Gottfried Wilhelm Leibniz,1646-1716）和牛顿（Isaac Newton1642—1727）都得到了解答。约翰的解法比较漂亮，而雅可布的解法虽然麻烦与费劲，却更为一般化。后来欧拉（Euler Lonhard ， 1707～1783）和拉格朗日(Lagrange, Joseph Louis ，1736-1813)发明了这一类问题的普遍解法，从而确立了数学的一个新分支——变分学。 有趣的是，在 1690 年约翰·伯努利的哥哥雅可比·伯努利曾提出著名的悬链线问题(The Hanging Chain Problem)向数学界征求答案，即，固定项链的两端，在重力场中让它自然垂下，问项链的曲线方程是什么。在大自然中，除了悬垂的项链外，我們还可以观察到吊桥上方的悬垂钢索，挂着水珠的蜘蛛网，以及两根电线杆之间所架设的电线，这些都是悬链线（catenary ）。 伽利略（Galileo, 1564～1643）比贝努利更早注意到悬链线，他猜测悬链线是抛物线， 从外表看的确象，但实际上不是。惠更斯（Huygens, 1629～1695）在 1646 年（当时 17 岁），经由物理的论证，得知伽利略的猜测不对，但那时，他也求不出答案。到 1691 年，也就是雅可比·伯努利提出悬链线问题的第二年，莱布尼兹、惠更斯（以 62 岁）与约翰·伯努利各自得到了正确答案，所用方法是诞生不久的微积分，具体说是把问题转化为求解一个二阶常微分方程 ? d 2 y ? dx 2 a 1+ ( dy )2 dx ? y (0) = y ? ? ? 解此方程并适当选取参数，得 y '(0) = 0 即为悬链线。 y = 1 2a (e ax + e -ax ) （1） 悬链线问题本身和变分法并没有关系，然而这和最速降线问题一样都是贝努利兄弟间的相互争强好胜、不断争吵的导火索，虽然雅可比·贝努利在解决悬链线问题时略占下风，但他随后所证明的“悬挂于两个固定点之间的同一条项链，在所有可能的形状中，以悬链线的重心最低，具有最小势能”，算是扳回了一局，俩兄弟扯平了！之所以提到悬链线问题，有两方面考虑，其一，这是有关数学史上著名的贝努利家族内的一个趣闻，而这是一个在变分法乃至整个数学物理领域有着巨大贡献的家族，其二，有关悬链线的得几个结论，可以用变 = 0

计算理论课后题及答案2

第三章 上下文无关语言 3.1 略。 3.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例3.20，证明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。 证明：a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →Sc|R|ε R →aRb 由此知 A,B 均为上下文无关语言。 但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B 也为CFL ，且CFL 对并运算封闭，所以B A ?也为CFL ，进而知道B A ?为CFL ，由DeMorgan 定律B A ?＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论矛盾，所以CFL 对补运算不封闭。 3.3 略。 3.4和3.5 给出产生下述语言的上下文无关文法和PDA ，其中字母表∑={0,1}。 a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|ε b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A 0, ε→ε 0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε

计算机科学与技术学科知识体系

计算机科学与技术学科知识体系 下面是14个知识领域（area）及其中的知识单元（llnits）和知识点（topiCS）的描述：1离散结构（DS） 1.1函数、关系和集合（核心）DS1 1.1.1函数DS11 1.1.1.1满射 1.1.1.2到的映射 1.1.1.3逆函数 1.1.1.4复合函数 1.1.2关系 1.1. 2.1自反 1.1. 2.2对称 1.1. 2.3传递 1.1. 2.4等价关系 1.1.3集合 1.1.3.1文氏图 1.1.3.2补集 1.1.3.3笛卡儿集 1.1.3.4幂集 1.1.4鸽笼原理 1.1.5基数性和可数性 1.2基本逻辑（核心） 1.2.1命题逻辑 1.2.2逻辑连接词 1.2.3真值表 1.2.4式 1.2.4.1合取式 1.2.4.2析取式 1.2.5永真性 1.2.6谓词逻辑 1.2.7全称量词和存在量词 1.2.8假言推理、否定式推理 1.2.9谓词逻辑的局限性 1.3证明技巧（核心） 1.3.1蕴涵、逆、逆反、置换、非、永假等概念 1.3.2形式证明结构 1.3.3直接证明 1.3.4反例证法 1.3.5逆反式证明法 1.3.6反证法 1.3.7数学归纳法 1.3.8强归纳法 1.3.9递归数学定义 1.3.10良序 1.4计数基础（核心） 1.4.1计数变元

1.4.2求和与相乘的规则 1.4.3包含排斥 1.4.4算术和几何级数 1.4.5斐波那契（Fibonacci）数列 1.4.6排列组合 1.4.7基本定义 1.4.8恒等式 1.4.9二项式定理 1.4.10递归关系 1.4.11实例 1.4.12 Master原理 1.5图与树（核心） 1.5.1树 1.5.2无向图 1.5.3有向图 1.5.4生成树 1.5.5遍历策略 1.6离散概率 1.6.1有限概率空间、概率度量、事件1.6.2条件概率、独立性、贝叶斯规则1.6.3 整型随机变量、期望 2程序设计基础（PF） 2.1程序设计基本结构（核心） 2.1.1变量、类型、表达式和语句 2.1.2高级语言的基本语法和语义 2.1.3输人和输出基础 2.1.4顺序、条件和循环控制结构 2.1.5函数定义、函数调用和参数传递2.1.6程序结构分解基础 2.2算法与问题求解（核心） 2.2.1问题求解策略 2.2.2问题求解算法 2.2.3算法实现策略 2.2.4调试策略 2.2.5算法的概念和特性 2.3基本数据结构（核心） 2.3.1基本类型 2.3.2数组 2.3.3记录 2.3.4字符串和字符串处理 2.3.5数据在存储器中的表示 2.3.6静态分配、栈式分配和堆式分配2.3.7运行时的存储器管理 2.3.8指针和引用 2.3.9链式结构 2.3.10栈、队列和哈希表的实现策略2.3.11树和图的实现策略

初等数论中的几个重要定理 引理 和推论

初等数论中的几个重要定理 基础知识 定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若＝1，则有且仅有一个是对模的剩余，即。并定义中和互质的数的个数， 称为欧拉（Euler）函数。 这是数论中的非常重要的一个函数，显然，而对于，就是1,2，…， 中与互素的数的个数，比如说是素数，则有。 引理：；可用容斥定理来证（证明略）。 定理1：（欧拉（Euler）定理）设＝1，则。 分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于＝1，从而 也是与互质的个数，且两两余数不一样，故 （），而（）＝1，故。 证明：取模的一个既约剩余系，考虑，由 于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系 是一一的，从而，。

，，故。证毕。 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。 定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。 设为质数，若是的倍数，则。若不是的倍数，则 由引理及欧拉定理得，，由此即得。 定理推论：设为质数，是与互质的任一整数，则。 定理3：（威尔逊（Wilson）定理）设为质数，则。 分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。 证明：对于，在中，必然有一个数除以余1，这是因为 则好是的一个剩余系去0。 从而对，使得； 若，，则，，故 对于，有。即对于不同的对应于不同的，即 中数可两两配对，其积除以余1，然后有，使，即与它自己配对，这时，，或， 或。 除外，别的数可两两配对，积除以余1。故。

计算机研究生《计算理论》复习题

1、请你从形式定义、计算过程和对应的语言特点关系等诸方面综合比较DFA、PDA和图灵机 2、对于简单文法（正则语言、上下文无关语言），能够根据其产生式写出其语言 3、正则语言泵引理和上下文无关语言泵引理的理解、相互比较和应用 4、最简DFA、最简PDA的概念；DFA和PDA的简化过程；（带ε和不带ε的）NFA化简成最简DFA的过程 5、图灵机的Golder编码和通用图灵机的编码 6、上下文无关文法的乔姆斯基范式 7、DFA的计算过程 8、上下文无关文法的推导过程以及其歧义相关概念及分析 9、关于四类乔姆斯基语言及其对应的自动机类型特点分析 10、四类乔姆斯基语言的各种运算类型并形式化表示 11、关于CFG和DFA的若干判定问题 12、关于若干渐进符号：同阶渐进符号Θ、大O、小O和大Ω符号的含义和用法 13、请从NP类问题、P类问题、确定型单带TM、确定型多带TM、非确定型TM等角度综述 时间复杂性规律 相关例题： 1、请你综合比较DFA、PDA和图灵机 2、请写出下列表达式生成的正则语言 1）设有文法G=(V,T,P,S)，其中V={S,A,B}，T={a,b}，P：S→aB；S→bA；A→bAA；A →a；A→aS；B→b；B→bS；B→aBB 请写出L(G)= 2）设一个有穷自动机M=(Q,∑,δ,q0,F)，其中Q={q0,q1,q2,q3)，∑={0,1}, F={q0}，δ如下： δ(q0,0)=q2, δ(q0,1)=q1, δ(q1,0)=q3, δ(q1,1)=q0 δ(q2,0)=q0, δ(q2,1)=q3, δ(q3,0)=q1, δ(q3,1)=q2 请写出L(M)= 3）设有文法G=({S,A},{a,b,c,d};R,S)，其中R：S→aSd|aAd， A→bAc|bc 请写出L(G)= 3、用泵引理证明下列论点 1）A1={a n b n c n|n≥0}不是正则语言 2）D={ww|w∈{0，1}*}不是上下文无关语言 4、把下面状态转换图代表的DFA变化成最简DFA

CHAP2new

2.1 略。 2.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例 3.20，证明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。 证明：a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →Sc|R|ε R →aRb 由此知 A,B 均为上下文无关语言。 但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B 也为CFL ，且CFL 对并运算封闭，所以B A ?也为CFL ，进而知道B A ?为CFL ，由DeMorgan 定律B A ?＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论矛盾，所以CFL 对补运算不封闭。 2.3 略。 2.4和2.5 给出产生下述语言的上下文无关文法和PDA ，其中字母表∑={0,1}。 a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|ε b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A d. {w | w 的长度为奇数且正中间的符号为0} S →0S0|1S1|0S1|1S0|0 0, ε→ε 0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε

自动机习题中文解答全

第二章习题解答 习题2.2.4 a) b) c) 习题2.2.9 a) 对|w|作归纳法。当|w|=1时w 为一字符，由题设已成立。设),(?),(?0w q w q f δδ=， 则对任一字母a ，有 ).,(?)),,(?(?)),,(?(? ),(?00wa q a w q a w q wa q f f δδδδδδ=== b) 对k 作归纳法。k=1时，由题设命题已成立。设x k ∈ L(A)，即f k q x q =),(?0δ。 于是 f f k k q x q x x q x q ===+),(?)),,(?(? ),(?010δδδδ，即x k ＋1∈ L(A)，证毕。 习题2.2.10 1) 将DFA 改写成转移图形式： 2）观察上图，知其接受的语言应为 L ＝{ w ∈{0,1}*: w 含奇数个1 }. 3) 用数学归纳法证明2）中的断言： 当|w|=1时，若w ＝0则DFA 不接受w ，若w ＝1则DFA 接受w ，此时命题成立。设w 时命题成立，即当w 中含偶数个1时DFA 不接受w ，当w 中含奇数个1时DFA 接受w 。 0,1 0,1

对于任一字符c ： 若c=0，则当w 中含偶数个1时由于DFA 不接受w ，故A w q =),(?0 δ，从而A wc q =),(?0δ；当w 中含奇数个1时由于DFA 接受w ，故B w q =),(?0δ，从而B wc q =),(?0 δ。 若c=1，则当w 中含偶数个1时由于DFA 不接受w ，故A w q =),(?0 δ，从而B wc q =),(?0δ；当w 中含奇数个1时由于DFA 接受w ，故B w q =),(?0δ，从而A wc q =),(?0 δ。 总之，当wc 中含偶数个1时DFA 不接受wc ，当wc 中含奇数个1时DFA 接受wc 。 命题得证。 习题2.2.11 1) 将DFA 改写成转移图形式： 2）观察上图，知其接受的语言应为 L ＝{ w ∈{0,1}*: w 不含子串00 }. 3) 用数学归纳法证明2）中的断言，过程与前题类似。 习题2.3.2 0, 1 0 1 →{p} {q, s} {q } *{q, s } {r} {p, q, r} *{q} {r} {q, r} {r} {s} {p} *{q, r} {r, s} {p, q, r} *{s} ? {p} *{r, s} {s} {p} *{p, q, r } {q, r, s} {p, q, r} *{q, r, s} {r, s} {p, q, r} ? ? ?

变分原理与变分法

第一章 变分原理与变分法 1.1 关于变分原理与变分法（物质世界存在的基本守恒法则） 一、 大自然总是以可能最好的方式安排一切，似乎存在着各种安排原理： 昼/夜，日/月，阴/阳，静止/运动 等矛盾/统一的协调体； 对静止事物：平衡体的最小能量原理，对称/相似原理； 对运动事物：能量守恒，动量（矩）守恒，熵增原理等。 变分原理是自然界静止(相对稳定状态)事物中的一个普遍适应的数学定律，获称最小作用原理。 Examples : ① 光线最短路径传播； ② 光线入射角等于反射角，光线在反射中也是光传播最短路径（Heron ）； ③ CB AC EB AE +>+ Summary : 实际上光的传播遵循最小能量原理； 在静力学中的稳定平衡本质上是势能最小的原理。 二、变分法是自然界变分原理的数学规划方法（求解约束方程系统极值的数学方 法），是计算泛函驻值的数学理论 数学上的泛函定义 定义：数学空间（集合）上的元素（定义域）与一个实数域间（值域）间 的（映射）关系 特征描述法：{ J :R x R D X ∈=→?r J )(|} Examples : ① 矩阵范数：线性算子（矩阵）空间数域 ‖A ‖1 = ∑=n i ij j a 1 max ；∑=∞=n j ij i a A 1max ；21 )(11 2 2∑∑===n j n i ij a A ② 函数的积分： 函数空间数域

D ?=?n b a n f dx x f J )( Note : 泛函的自变量是集合中的元素（定义域）；值域是实数域。 Discussion ： ① 判定下列那些是泛函： )(max x f f b x a <<=； x y x f ??) ,(； 3x+5y=2； ?+∞∞-=-)()()(00x f dx x f x x δ ② 试举另一泛函例子。 物理问题中的泛函举例 ① 弹性地基梁的系统势能 i. 梁的弯曲应变能： ?=∏l b dx dx w d EJ 02 22)(21 ii. 弹性地基贮存的能量： dx kw l f ?=∏0 221 iii. 外力位能： ?-=∏l l qwdx 0 iv. 系统总的势能： 00 0;})({2 2122202 1===-+=∏?dx dw w x dx qw kw dx w d EJ l 泛函的提法：有一种梁的挠度函数（与载荷无关），就会有一个对应的系 统势能。 泛函驻值提法：在满足位移边界条件的所有挠度函数中，找一个w (x ),使 系统势能泛函取最小值。 ② 最速降线问题 问题：已知空间两点A 和B ,A 高于B ，要求在两点间连接一条曲线，使 得有重物从A 沿此曲线自由下滑时，从A 到B 所需时间最短（忽略摩擦力）。 作法： i. 通过A 和B 作一垂直于水平面的平面，取坐标系如图。B 点坐标(a , b ),设曲线为y = y (x ),并已知：x = 0,y = 0；x = a ,y = b ii. 建立泛函： x

上下文无关语言和非上下文无关语言

8 上下文无关语言和非上下文无关语言 8.1 上下文无关语言的泵引理 从第6章到第7章，我们给出了两种描述CFL的模型，CFG和PDA。这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。然而，正如例子6.7对自然语言的一个简单考察，我们发现CFG存在描述能力的局限。本节中，我们精确定义和讨论CFL的一个性质，它类似于正则语言的泵引理。利用这个性质能够发现许多不是CFL的语言。 正则语言的泵引理基于这样的事实，如果一个足够长的输入字符串x导致FA在状态转移中，到达某个状态超过一次，即接受路径上存在回路，根据回路容易将x分成三部分，u是回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重复，得到的新的字符串也应该被FA接受，即对任意的m>=0，uv m w被FA接受。如果我们用CFG生成（而不是PDA移动）CFL，容易得到类似的观察。设CFG G的一个推导出现同一个非终结符的嵌套重复，如下面的形式， S?*vAz?*vwAyz?*vwxyz 其中，v, w, x, y, z∈∑*。推导过程中，出现了A?*wAy，我们可以多次重复这个推导过程，如 S?*vAz?*vwAyz?*vw2Ay2z?*vw3Ay3z?*...?*vw m Ay m z 又由于A?*x，因此所有这类字符串vxz, vwxyz, vw2xy2z, ..., vw m xy m z都输入语言L(G)。 为了将上面的观察总结成CFL的泵引理，我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。同时我们也尽量发现分解得到的5个子串：v, w, x, y, z，的一些性质。这类似于我们处理正则语言的泵引理。 在6.6节，我们证明了所有的CFG产生式都可以改写成Chomsky范式，而不会影响CFG 接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。因此我们的讨论可以局限在Chomsky范式（CNF）表示的CFG，显然这类文法得到的推导树都是二叉树，即每个父节点至多有两个子节点。 我们先定义几个与二叉树相关的概念。路径是一串节点组成的序列，前后节点之间有父子关系；路径的长度是路径包含的节点的个数；二叉树的高度是最长路径的长度。由于非终结符数目有限，如果推导树足够高，那么存在一个路径，某个非终结符在该路径上出现了两次，即出现了前面提到的嵌套重复现象。 引理8.1 任给h>=1，如果二叉树的叶结点个数>2h-1，那么该二叉树的高度>h。 证明：这是一个数学问题。我们用数学归纳法证明它的逆反命题：如果二叉树的高度<=h，那么二叉树的叶节点个数<=2h-1。 1.归纳基础，h=1，此时二叉树只有一个根节点，它也是唯一的叶结点，命题成立。 2.归纳推理，设k>=1时，命题成立。要证明k+1时，命题也成立。设二叉树T的高度为 k+1，则它的根节点的两个子树（以子节点为跟的二叉树）的叶节点数都<=2k-1，因此T 的叶节点数<=2k-1+2k-1=2k。得证。 定理8.1 G=(V, ∑, S, P)是形式为CNF的CFG，共有p个非终结符，则对每个长度>=2p+1的属于L(G)的字符串，都能找到5个字符串v, w, x, y, z满足下面的条件： u=vwxyz |wy|>0 |wxy|<=2p+1 vw m xy m z∈L(G), ?m>=0 证明：根据引理8.1，任何一个生成u的推导树高度>=p+2，即至少存在一个长度>=p+2的路径，不妨设d是其中的一个，显然d的最底部是一个终结符，其上的符号都是非终结符，共

Matlab建模教程-变分法简介

§1 变分法简介 作为数学的一个分支，变分法的诞生，是现实世界许多现象不断探索的结果，人们可以追寻到这样一个轨迹： 约翰·伯努利（Johann Bernoulli ，1667－1748）1696年向全欧洲数学家挑战，提出一个难题：“设在垂直平面内有任意两点，一个质点受地心引力的作用，自较高点下滑至较低点，不计摩擦，问沿着什么曲线下滑，时间最短？” 这就是著名的“最速降线”问题（The Brachistochrone Problem ）。它的难处在于和普通的极大极小值求法不同，它是要求出一个未知函数（曲线），来满足所给的条件。这问题的新颖和别出心裁引起了很大兴趣，罗比塔（Guillaume Francois Antonie de l'Hospital 1661-1704）、雅可比·伯努利（Jacob Bernoulli 1654-1705）、莱布尼茨（Gottfried Wilhelm Leibniz,1646-1716）和牛顿（Isaac Newton1642—1727）都得到了解答。约翰的解法比较漂亮，而雅可布的解法虽然麻烦与费劲，却更为一般化。后来欧拉（Euler Lonhard ，1707～1783）和拉格朗日(Lagrange, Joseph Louis ，1736-1813)发明了这一类问题的普遍解法，从而确立了数学的一个新分支——变分学。 有趣的是，在1690年约翰·伯努利的哥哥雅可比·伯努利曾提出著名的悬链线问题 (The Hanging Chain Problem)向数学界征求答案，即，固定项链的两端，在重力场中让它自然垂下，问项链的曲线方程是什么。在大自然中，除了悬垂的项链外，我們还可以观察到吊桥上方的悬垂钢索，挂着水珠的蜘蛛网，以及两根电线杆之间所架设的电线，这些都是悬链线（catenary ）。 伽利略（Galileo, 1564～1643）比贝努利更早注意到悬链线，他猜测悬链线是抛物线，从外表看的确象，但实际上不是。惠更斯（Huygens, 1629～1695）在1646年（当时17岁），经由物理的论证，得知伽利略的猜测不对，但那时，他也求不出答案。到1691年，也就是雅可比·伯努利提出悬链线问题的第二年，莱布尼兹、惠更斯（以62岁）与约翰·伯努利各自得到了正确答案，所用方法是诞生不久的微积分，具体说是把问题转化为求解一个二阶常微分方程 解此方程并适当选取参数，得 )(21ax ax e e a y -+= （1） 即为悬链线。 悬链线问题本身和变分法并没有关系，然而这和最速降线问题一样都是贝努利兄弟间的相互争强好胜、不断争吵的导火索，虽然雅可比·贝努利在解决悬链线问题时略占下风，但他随后所证明的“悬挂于两个固定点之间的同一条项链，在所有可能的形状中，以悬链线的重心最低，具有最小势能”，算是扳回了一局，俩兄弟扯平了！之所以提到悬链线问题，有两方面考虑，其一，这是有关数学史上著名的贝努利家族内的一个趣闻，而这是一个在变分法乃至整个数学物理领域有着巨大贡献的家族，其二，有关悬链线的得几个结论，可以用变 ???????='=+=0)0()0()(102 2 2y y y dx dy a dx y d

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

形式语言与自动机理论试题答案解析 一、按要求完成下列填空 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 ? ( 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 |→

3、上下文无关语言练习

第3章、上下文无关语言习题解答 - 练习 3.1 回忆一下例3.3中给出的CFG G 4。为方便起见，用一个字母重新命名它的变元如下： E →E ＋T|T T →T ×E|F F →（E ）|a 给出下述字符串的语法分析树和派生。 a. a b. a+a c. a+a+a d. ((a)) 答： a. E T F a ??? b. E E T T F F a a a ?+?+?+?+ c. E E T E T F T F a F a a a a a ?+?++?++?++?++ d. ()()()(())(())(())(())E T F E T F E T F a ????????? 3.2 a. 利用语言A={a m b n c n | m,n ≥0}和B={a n b n c m | m,n ≥0}以及例3.20(语言B={a n b n c n | n ≥0}不是上下文无关的)，证明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。 证明： a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1 S →aS|T|ε T →bTc|ε //生成b n c n 对B,构造CFG C 2 S →Sc|R|ε R →aRb |ε //生成a n b n 由此知 A,B 均为上下文无关语言。 由例3.20, A ∩B={a n b n c n |n ≥0}（假设m ≤n ）不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。

b. 用反证法。 假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B 也为CFL 。因为CFL 对并运算封闭，所以A B U 也为CFL ，进而知道A B U 为CFL 。由DeMorgan 定律A B A B =U I ，得出A B I 是CFL 。 这与(a)的结论矛盾，所以CFL 对补运算不封闭。 3.3 设上下文无关文法G ： R →XRX|S S →aTb|bTa T →XTX|X|ε X →a|b 回答下述问题： a. G 的变元和终结符是什么？起始变元是哪个？ 答：变元是：R ，X ，S ，T ；起始变元是R 。终结符是：a ，b ，ε b. 给出L(G)中的三个字符串。答：ab ，ba ，aab 。 c. 给出不在L(G)中的三个字符串。答：a ，b ，ε。 d. 是真是假：T aba ?。答：假 e. 是真是假：* T aba ?。答：真 f. 是真是假：T T ?。答：假 g. 是真是假：* T T ?。答：假 h. 是真是假：* XXX aba ?。答：真 i. 是真是假：* X aba ?。答：假 j. 是真是假：* T XX ?。答：真 k. 是真是假：* T XXX ?。答：真 l. 是真是假：*X ε?。答：假 m. 用普通的语言描述L(G)：