轨迹

集合

集合的性质

（1）A=B 则AÍB且BÍA。

⑵ 如果AÍB，则|A|≤|B|。

⑶ 如果AÌB，则|A|≤|B|。

⑷ 如果A是有穷集，且AÌB，则|B|>|A|。

⑸ 如果AÍB，则对"x∈A，有x∈B。

⑹ 如果AÌB，则对"x∈A，有x∈B并且$x∈B，但xÏA。

⑺ 如果AÍB且BÍC，则AÍC。

⑻ 如果AÌB且BÌC，或者AÍB且BÌC，或者AÌB且BÍC，则AÌC。

⑼ 如果A=B，则|A|=|B|。

集合的运算

• 并(union)

A与B的并(union)是一个集合，该集合中的元素要么是A的元素，要么是B的元素，记作A∪B。

• 交

集合A和B中都有的所有元素放在一起构成的集合为A与B的交，记作A∩B。

• 差

属于A，但不属于B的所有元素组成的集合叫做A与B的差，记作A-B。

• 对称差

属于A但不属于B，属于B但不属于A的所有元素组成的集合叫A与B的对称差，记作A⊕B。

• 笛卡尔积

A与B的笛卡儿积(Cartesian product)是一个集合，该集合是由所有这样的有序对(a，b)组成的：其中a∈A，b∈B ，记作A×B。

• 幂集

A幂集(power set)是一个集合，该集合是由A的所有子集组成的，记作2^A。

• 补集

A是论域U上的一个集合，A补集是由U中的、不在A中的所有元素组成的集合，记作

二元关系

• 二元关系

– 任意的RÍA×B，R是A到B的二元关系。

– (a，b) ∈R，也可表示为：aRb。

– A称为定义域(domain)，B称为值域(range)。

– 当A=B时，则称R是A上的二元关系。

• 二元关系的性质

– 自反(reflexive)性、反自反(irreflexive)性、对称(symmetric)性、反对称(asymmetric)性、传递(transitive)性。

• 三歧性

– 自反性、对称性、传递性。

• 等价关系(equivalence relation)

– 具有三歧性的二元关系称为等价关系。

• 等价类 (equivalence class)

S的满足如下要求的划分：S₁、S₂、S₃、…、S_n…称为S关于R的等价划分，S_i称为等价类。

１.S= S1∪S2∪S3∪…∪Sn∪…；

２.如果i≠j，则Si∩Sj=Φ；

３.对任意的i，Si中的任意两个元素a、b，aRb恒成立；

４.对任意的i，j，i≠j，Si中的任意元素a和Sj中的任意元素b，aRb恒不成立

• 指数　(index)

ａ.把R将S分成的等价类的个数称为是R在S上的指数。如果R将S分成有穷多个等价类，则称R具有有穷指数；如果R将S分成无穷多个等价类，则称R具有无穷指数。

ｂ.给定集合S上的一个等价关系R，R就确定了S的一个等价分类，当给定另一个不同的等价关系时，它会确定S的一个新的等价分类。

• 关系的合成 (composition)

设R1ÍA×B是A到B的关系、R2ÍB×C是B到C的关系，R1与R2的合成R1R2是A到C的关系：R1R2={(a，c)| $(a，b) ∈R1且(b，c) ∈R2 。

⑴ R1R2≠R2R1。

⑵ (R1R2)R3=R1(R2R3)。 (结合率)

⑶ (R1∪R2)R3=R1R3∪R2R3。 (右分配率)

⑷ R3(R1∪R2)=R3R1∪R3R2。 (左分配率)

⑸ (R1∩R2)R3ÍR1R3∩R2R3。

⑹ R3(R1∩R2)ÍR3R1∩R3R2。

• 递归定义(recursive definition)

– 又称为归纳定义(inductive definition)，它来定义一个集合。

– 集合的递归定义由三部分组成：

• 基础(basis)：用来定义该集合的最基本的元素。

• 归纳(induction)：指出用集合中的元素来构造集合的新元素的规则。

• 极小性限定：指出一个对象是所定义集合中的元素的充要条件是它可以通过有限次的使用基础和归纳条款中所给的规定构造出来

• 归纳证明

– 与递归定义相对应。

– 归纳证明方法包括三大步：

• 基础(basis)：证明最基本元素具有相应性质。

• 归纳(induction)：证明如果某些元素具有相应性质，则根据这些元素用所规定的方法得到的新元素也具有相应的性质。

• 根据归纳法原理，所有的元素具有相应的性质。

• 幂

设R是S上的关系，我们递归地定义Rⁿ的幂：

⑴ R⁰={(a，a)|a∈S}。

⑵ Rⁱ=R^i-1R (i=1,2,3,4,5,…)。

关系的闭包

• 闭包(closure)

– 设P是关于关系的性质的集合，关系R的P闭包(closure)是包含R并且具有P中所有性质的最小关系。

• 正闭包(positive closure)

(1)RÍR+。

(2)如果(a，b)，(b，c)∈R+ 则(a，c)∈R+。

(3)除(1)、(2)外，R+不再含有其他任何元素。

• 传递闭包(transitive closure)

– 具有传递性的闭包。

– R⁺具有传递性。

可以证明，对任意二元关系R，R+= R∪R2∪R3∪R4∪…

而且当S为有穷集时：R+= R∪R2∪R3∪…∪R|S|

• 克林闭包(Kleene closure) R^*

(1) R⁰Í R^*,RÍ R^*。

　 (2) 如果(a，b)，(b，c)∈R^* 则(a，c)∈R^*。

(3) 除(1)、(2)外，R^*不再含有其他任何元素。

• 自反传递闭包(reflexive and transitive closure)

R^*具有自反性、传递性。

可以证明，对任意二元关系R，

R*= R0∪R+

R* =R0∪R∪R2∪R3∪R4∪…

而且当S为有穷集时：

R*= R0∪R∪R2∪R3∪…∪R|S|

• 闭包的相关性质

R1、R2是S上的两个二元关系

(1) Φ+=Φ。

(2) (R1+)+= R1+ 。

(3) (R1*)*= R1*。

(4) R1+∪R2+Í(R1∪R2)+。

(5) R1*∪R2*Í(R1∪R2)*。

图

• 无向图(undirected graph)

– 设V是一个非空的有穷集合，EÍV×V，G=(V，E)称为无向图(undirected graph)。其中V中的元素称为顶点(vertex或node)，V称为顶点集，E中的元素称为无向边(undirected edge)，E为无向边集。

• 图表示

V中称为顶点v的元素用标记为v的小圈表示，E中的元素(v1，v2)用标记为v1，v2的顶点之间的连线表示。

• 路(path)

如果对于0≤i≤k-1，k≥1，均有(vi，vi+1)∈E，则称v0，v1，…，vk是G=(V，E)的一条长为k的路。

• 回路或圈(cycle)

– 当路v₀，v₁，…，v_k中v₀=v_k时，v₀，v₁，…，v_k叫做一个回路或圈(cycle)。

• 顶点的度数

对于v∈V，|{v|(v，w)∈E}|称为无向图G=(V，E)的顶点v的度数，记作deg(v)。

对于任何一个图，图中所有顶点的度数之和为图中边的2倍。

• 连通图

– 如果对于"v，w∈V，v≠w，v与w之间至少有一条路存在，则称G=(V，E)是连通图。

– 图G是连通的充要条件是G中存在一条包含图的所有顶点的路。

• 有向图(directed graph)

– G=(V，E)。

– V：顶点(vertex或node)集。

– (v₁，v₂)∈E：顶点v₁到顶点v₂的有向边(directed edge)，或弧(arc)，v₁称为前导(predecessor)，v₂称为后继(successor)。

• 有向路(directed path)

– 如果对于0≤i≤k-1，k≥1，均有(v_i，v_i+1)∈E，则称v₀，v₁，…，v_k是G的一条长为k的有向路。

• 有向回路或有向圈(directed cycle)

– 对于0≤i≤k-1，k≥1，均有(v_i，v_i+1)∈E，且v₀=v_k，则称v₀，v₁，…，v_k是G的一条长为k的有向路为一个有向回路。

– 有向回路又叫有向圈。

• 有向图的图表示

– 图G的图表示是满足下列条件的“图”：其中V中称为顶点v的元素用标记为v的小圈表示，E中的元素(v₁，v₂)用从标记为v₁的顶点到标记为v₂的顶点的弧表示。

• 顶点的度数

– 入度(数)：ideg(v)=|{v|(w，v)∈E}|。

– 出度(数)：odeg(v)= |{v|(v，w)∈E}|。

• 对于任何一个有向图，图中所有顶点的入度之和与图中所有顶点的出度之和正好是图中边的个数

•

树

• 定义

满足如下条件的有向图G=(V，E)称为一棵(有序、有向)树(tree)：

– 根(root) v：没有前导，且v到树中其他顶点均有一条有向路。

– 每个非根顶点有且仅有一个前导。

– 每个顶点的后继按其拓扑关系从左到右排序。

• 树的基本概念

(1) 顶点也可以成为结点。

(2) 结点的前导为该结点的父亲(父结点father)。

(3) 结点的后继为它的儿子(son)。

(4) 如果树中有一条从结点v1到结点v2的路，则称v1是v2的祖先(ancestor), v2是v1的后代(descendant)。

(5) 无儿子的顶点叫做叶子(leaf)。

(6) 非叶结点叫做中间结点(interior)。

• 树的层

– 根处在树的第1层(level)。

– 如果结点v处在第i层(i≥1)，则v的儿子处在第i+1层。

– 树的最大层号叫做该树的高度(height)。

• 二元树

– 如果对于"v∈V，v最多只有2个儿子，则称G=(V，E)为二元树(binary tree)。

– 对一棵二元树，它的第n层最多有2^n-1个结点。一棵n层二元树最多有个2^n-1叶子。

– ３.png

语言

４.png

• 对语言研究的三个方面

– 表示(representation)—— 无穷语言的表示。

– 有穷描述(finite description) ——研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。

– 结构(structure)——语言的结构特征。

• 字母表(alphabet)

– 字母表是一个非空有穷集合，字母表中的元素称为该字母表的一个字母(letter)。又叫做符号(symbol)、或者字符(character)。

– 非空性。

– 有穷性。

例如：

{a，b，c，d}

{ a，b，c，…，z}

{0,1}

• 字符的两个特性

– 整体性(monolith)，也叫不可分性。

– 可辨认性(distinguishable)，也叫可区分性。

例（续）

{a，a′，b，b′}

{aa，ab，bb}

{∞，∧，∨，≥，≤}

• 字母表的乘积(product)

∑₁∑₂={ab|a∈∑₁，b∈∑₂}

例如：

{0,1}{0,1}={00，01，10，00}

{0,1}{a，b，c，d}={0a，0b，0c，0d，1a，1b，1c，1d}

{a，b，c，d}{0,1}={a0，a1，b0，b1，c0，c1，d0，d1}

{aa，ab，bb}{0,1}={ aa0，aa1，ab0，ab1，bb0，bb1}

• 字母表∑的n次幂

∑⁰={ε}

∑ⁿ=∑^n-1∑

ε是由∑中的0个字符组成的。

• ∑的正闭包

∑+=∑∪∑2∪∑3∪∑4∪…

• ∑的克林闭包

∑^*=∑⁰∪∑⁺=∑⁰∪∑∪∑²∪∑³∪…

• 结论：

∑^*={x|x是∑中的若干个，包括0个字符，连接而成的一个字符串}。

∑⁺={x|x是∑中的至少一个字符连接而成的字符串}。

• 句子(sentence)

∑是一个字母表，"x∈∑*，x叫做∑上的一个句子。

• 句子相等。

两个句子被称为相等的，如果它们对应位置上的字符都对应相等。

• 别称

字(word)、(字符、符号)行(line)、(字符、符号)串(string)。

• 出现(apperance)

x，y∈∑*，a∈∑，句子xay中的a叫做a在该句子中的一个出现。

当x=ε时，a的这个出现为字符串xay的首字符

如果a的这个出现是字符串xay的第n个字符，则y的首字符的这个出现是字符串xay的第n+1个字符。

当y=ε时，a的这个出现是字符串xay的尾字符

例：abaabb。

• 句子的长度(length)

"x∈∑*，句子x中字符出现的总个数叫做该句子的长度，记作|x|。

长度为0的字符串叫空句子，记作ε。

例如：

|abaabb|=6

|bbaa|=4

|ε|=0

|bbabaabbbaa|=11

• 注意事项

ε是一个句子。

{ε}≠Φ。这是因为{ε}不是一个空集，它是含有一个空句子ε的集合。|{ε}|=1，而|Φ|=0。

并置(concatenation)

x，y∈∑*，x，y的并置是由串x直接相接串y所组成的。记作xy。并置又叫做连结。

串x的n次幂

x⁰=ε

xⁿ=x^n-1x

• ∑^*上的并置运算性质

⑴ 结合律：(xy)z=x(yz)。

⑵ 左消去律：如果xy=xz，则y=z。

⑶ 右消去律：如果yx=zx，则y=z。

⑷ 惟一分解性：存在惟一确定的a1，a2，…，an∈∑，使得x= a1a2…an。

⑸ 单位元素：εx=xε=x。

• 前缀与后缀

设x，y，z，w，v∈∑*，且x=yz，w=yv

(1) y是x的前缀(prefix)。

(2)如果z≠ε，则y是x的真前缀(proper prefix)。

(3) z是x的后缀(suffix)；

(4) 如果y≠ε，则z是x的真后缀(proper suffix)。

(5) y是x和w的公共前缀(common Prefix)。

(6)如果x和w的任何公共前缀都是y的前缀，则y是x和w的最大公共前缀。

(7) 如果x=zy，w=vy，则y是x和w的公共后缀(common suffix )。

(8)如果x和w的任何公共后缀都是y的后缀，则y是x和w的最大公共后缀。

• 结论

⑴ x的任意前缀y有惟一的一个后缀z与之对应，使得x=yz；反之亦然。

⑵ x的任意真前缀y有惟一的一个真后缀z与之对应，使得x=yz；反之亦然。

⑶ |{w|w是x的后缀}|=|{w|w是x的前缀}|。

⑷ |{w|w是x的真后缀}|=|{w|w是x的真前缀}|。

⑸ {w|w是x的前缀}={w|w是x的真前缀}∪{x}，

|{w|w是x的前缀}|=|{w|w是x的真前缀}|+1。

⑹ {w|w是x的后缀}={w|w是x的真后缀}∪{x}，

|{w|w是x的后缀}|=|{w|w是x的真后缀}|+1。

⑺ 对于任意字符串w，w是自身的前缀，但不是自身的真前缀；w是自身的后缀，但不是自身的真后缀。

⑻ 对于任意字符串w，ε是w的前缀，且是w的真前缀；ε是w的后缀，且是w的真后缀

• 约定

（１）用小写字母表中较为靠前的字母a，b，c，…表示字母表中的字母。

（２）用小写字母表中较为靠后的字母x，y，z，…表示字母表上的句子。

（３）用xT表示x的倒序。例如，如果x=abc，则xT=cba。

• 子串(substring)

w，x，y，z∈∑*，且w=xyz，则称y是w的子串。

• 公共子串(common substring)

t，u，v，w，x，y，z∈∑*，且t=uyv，w=xyz，则称y是t和w的公共子串(common substring)。如果y1，y2，……，yn是t和w的公共子串，且max{|y1|，|y2|，…，|yn|}=|yj|，则称yj是t和w的最大公共子串。

两个串的最大公共子串并不一定是惟一的。

• 语言(language)

"LÍ∑*，L称为字母表∑上的一个语言(language)，"x∈L，x叫做L的一个句子。

例：{0，1}上的不同语言

{00，11} ，{0，1}

{0，1，00，11} ， {0，1，00，11，01，10}

{00，11}*，{01，10}*，{00，01，10，11}*，

{0}{0，1}*{1}，{0，1}*{111}{0，1}*

• 语言的乘积(product)

L1Í∑1*，L2Í∑2*，语言L1与L2的乘积是一个语言，该语言定义为：

L1L2={xy| x∈L1，y∈L2}

是字母表∑1∪∑2上的语言。

• 上述几个语言的部分特点及相互关系

上述所有语言都是L₄的子集(子语言)；

L₁，L₂是有穷语言；其他为无穷语言；其中L₁是∑上的所有长度为1的句子组成的语言，L₂是∑上的所有长度为2的句子组成的语言；

L₃，L₄分别是∑的正闭包和克林闭包；

L₅L₇≠L₆，但L₅L₇= L₈；同样L₉≠L₁₀，但是我们有：L₆ÌL₅L₇，L₉ÌL₁₀_。

L₆={0ⁿ1ⁿ|n≥1}中的句子中的0和1的个数是相同的，并且所有的0在所有的1的前面，L₁₁={x|x∈∑⁺且x中0和1的个数相同}中的句子中虽然保持着0的个数和1的个数相等，但它并没要求所有的0在所有的1的前面。例如，0101，1100∈L₁₁，但是0101Ï L₆，1100ÏL₆。而对"x∈L₆，有x∈L₁₁。所以，L₆ ÌL₁₁_。