形式语言与自动机-基本概念

集合

集合的性质

(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)

    AB的并(union)是一个集合,该集合中的元素要么是A的元素,要么是B的元素,记作AB

   

 集合AB中都有的所有元素放在一起构成的集合为AB的交 ,记作AB

   

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

    对称差

 属于A但不属于B,属于B但不属于A的所有元素组成的集合叫AB的对称差,记作AB

    笛卡尔积

   AB的笛卡儿积(Cartesian product)是一个集合,该集合是由所有这样的有序对(ab)组成的:其中aAbB ,记作A×B

    幂集

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

    补集

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


二元关系

    二元关系

   任意的RÍA×BRAB的二元关系。

   (ab) R,也可表示为:aRb

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

   A=B时,则称RA上的二元关系。

    二元关系的性质

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

    三歧性

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

    等价关系(equivalence relation)

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

    等价类 (equivalence class)

    S的满足如下要求的划分:S1S2S3Sn称为S关于R的等价划分,Si称为等价类。

    .S= S1S2S3Sn

    .如果i≠j,则Si∩Sj=Φ

    .对任意的iSi中的任意两个元素abaRb恒成立;

    .对任意的iji≠jSi中的任意元素aSj中的任意元素baRb恒不成立

    指数 (index)

    .RS分成的等价类的个数称为是RS上的指数。如果RS分成有穷多个等价类,则称R具有有穷指数;如果RS分成无穷多个等价类,则称R具有无穷指数。

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

    关系的合成 (composition)

       R1ÍA×BAB的关系、R2ÍB×CBC的关系,R1R2的合成R1R2AC的关系:R1R2={(ac)| $(ab) R1(bc) R2

     R1R2≠R2R1

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

     (R1R2)R3=R1R3R2R3   (右分配率)

     R3(R1R2)=R3R1R3R2   (左分配率)

     (R1∩R2)R3ÍR1R3∩R2R3

     R3(R1∩R2)ÍR3R1∩R3R2

    递归定义(recursive definition)

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

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

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

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

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

    归纳证明

  与递归定义相对应。

  归纳证明方法包括三大步:

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

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

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

   

RS上的关系,我们递归地定义Rn的幂:

R0={(aa)|aS}

Ri=Ri-1R  (i=1,2,3,4,5,…)


关系的闭包

    闭包(closure)

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

    正闭包(positive closure)

(1)RÍR+

(2)如果(ab)(bc)R+ (ac)R+

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

 

    传递闭包(transitive closure)

  具有传递性的闭包。

  R+具有传递性。

可以证明,对任意二元关系RR+= RR2R3R4

而且当S为有穷集时:R+= RR2R3R|S|

    克林闭包(Kleene closure) R*

      (1)  R0Í R*,RÍ R*

    (2)  如果(ab)(bc)R* (ac)R*

      (3) (1)(2)外,R*不再含有其他任何元素。

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

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

 

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

        R*= R0R+

        R* =R0RR2R3R4

而且当S为有穷集时:

        R*= R0RR2R3R|S|

    闭包的相关性质

    R1R2S上的两个二元关系

       (1) Φ+=Φ

       (2) (R1+)+= R1+

       (3) (R1*)*= R1*

       (4) R1+R2+Í(R1R2)+

       (5)  R1*R2*Í(R1R2)*

                                                                                      

    无向图(undirected graph)

  V是一个非空的有穷集合,EÍV×VG=(VE)称为无向图(undirected graph)。其中V中的元素称为顶点(vertexnode)V称为顶点集,E中的元素称为无向边(undirected edge)E为无向边集。

    图表示

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

    (path)

如果对于0≤i≤k-1k≥1,均有(vivi+1)E,则称v0v1vkG=(VE)的一条长为k的路。

    回路或圈(cycle)

  当路v0v1vkv0=vk时,v0v1vk叫做一个回路或圈(cycle)

    顶点的度数

对于vV|{v|(vw)E}|称为无向图G=(VE)的顶点v的度数,记作deg(v)

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

2.png

    连通图

  如果对于"vwVv≠wvw之间至少有一条路存在,则称G=(VE)是连通图。

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

    有向图(directed graph)

  G=(VE)

  V:顶点(vertexnode)集。

  (v1v2)E:顶点v1到顶点v2的有向边(directed edge),或弧(arc)v1称为前导(predecessor)v2称为后继(successor)

    有向路(directed path)

  如果对于0ik-1k1,均有(vivi+1)E,则称v0v1vkG的一条长为k的有向路。

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

  对于0ik-1k1,均有(vivi+1)E v0=vk,则称v0v1vkG的一条长为k的有向路为一个有向回路。

  有向回路又叫有向圈。

    有向图的图表示

  G的图表示是满足下列条件的:其中V中称为顶点v的元素用标记为v的小圈表示,E中的元素(v1v2)用从标记为v1的顶点到标记为v2的顶点的弧表示。

    顶点的度数

  入度()ideg(v)=|{v|(wv)E}|

  出度()odeg(v)= |{v|(vw)E}|

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

 2.png

    定义

满足如下条件的有向图G=(VE)称为一棵(有序、有向)(tree)

  (root) v:没有前导,且v到树中其他顶点均有一条有向路。

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

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

    树的基本概念

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

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

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

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

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

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

    树的层

  根处在树的第1(level)

  如果结点v处在第i(i1),则v的儿子处在第i+1层。

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

    二元树

  如果对于"vVv最多只有2个儿子,则称G=(VE)为二元树(binary tree)

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

  3.png

语言

4.png

    对语言研究的三个方面

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

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

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

    字母表(alphabet)

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

  非空性。

  有穷性。

例如:

        {abcd}

        { abcz}

        {0,1}

    字符的两个特性

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

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

例(续)

        {aa′bb′}

        {aaabbb}

                       {∞,∧,∨,≥,≤}

 

    字母表的乘积(product)

        ∑12={ab|a1b2}

例如:

{0,1}{0,1}={00011000}

{0,1}{abcd}={0a0b0c0d1a1b1c1d}

{abcd}{0,1}={a0a1b0b1c0c1d0d1}

{aaabbb}{0,1}={ aa0aa1ab0ab1bb0bb1}

    字母表∑的n次幂

   ∑0={ε}

   ∑n=∑n-1

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

    的正闭包

              ∑+=∑∑2∑3∑4

    的克林闭包

              ∑*=∑0+=∑023

    结论:

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

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

    句子(sentence)

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

    句子相等。

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

    别称

                (word)(字符、符号)(line)(字符、符号)(string)

    出现(apperance)

xy∑*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)

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

xn次幂

    x0

    xn=xn-1x

 

    *上的并置运算性质

结合律:(xy)z=x(yz)

左消去律:如果xy=xz,则y=z

右消去律:如果yx=zx,则y=z

惟一分解性:存在惟一确定的a1a2an,使得x= a1a2…an

单位元素:εx=xε=x

    前缀与后缀

xyzwv∑*,且x=yzw=yv

(1) yx的前缀(prefix)

(2)如果z≠ε,则yx的真前缀(proper  prefix)

(3) zx的后缀(suffix)

(4) 如果y≠ε,则zx的真后缀(proper suffix)

(5) yxw的公共前缀(common Prefix)

(6)如果xw的任何公共前缀都是y的前缀,则yxw的最大公共前缀。

(7) 如果x=zyw=vy,则yxw的公共后缀(common suffix )

(8)如果xw的任何公共后缀都是y的后缀,则yxw的最大公共后缀。

 

    结论

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

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

|{w|wx的后缀}|=|{w|wx的前缀}|

|{w|wx的真后缀}|=|{w|wx的真前缀}|

  {w|wx的前缀}={w|wx的真前缀}{x}

     |{w|wx的前缀}|=|{w|wx的真前缀}|+1

  {w|wx的后缀}={w|wx的真后缀}{x}

      |{w|wx的后缀}|=|{w|wx的真后缀}|+1

  对于任意字符串ww是自身的前缀,但不是自身的真前缀;w是自身的后缀,但不是自身的真后缀。

   对于任意字符串wεw的前缀,且是w的真前缀;εw的后缀,且是w的真后缀

 

    约定

(1)用小写字母表中较为靠前的字母abc表示字母表中的字母。

 (2)用小写字母表中较为靠后的字母xyz表示字母表上的句子。

 (3)用xT表示x的倒序。例如,如果x=abc,则xT=cba

 

    子串(substring)

wxyz∑*,且w=xyz,则称yw的子串。

    公共子串(common substring)

tuvwxyz∑*,且t=uyvw=xyz,则称ytw的公共子串(common substring)。如果y1y2……yntw的公共子串,且max{|y1||y2||yn|}=|yj|,则称yjtw的最大公共子串。

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

 

 

    语言(language)

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

例:{01}上的不同语言

  {0011} {01}

  {010011} {0100110110}

  {0011}*{0110}*{00011011}*

  {0}{01}*{1}{01}*{111}{01}*

    语言的乘积(product)

L1Í∑1*L2Í∑2*,语言L1L2的乘积是一个语言,该语言定义为:

L1L2={xy| xL1yL2}

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

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

上述所有语言都是L4的子集(子语言)

L1L2是有穷语言;其他为无穷语言;其中L1是∑上的所有长度为1的句子组成的语言,L2是∑上的所有长度为2的句子组成的语言;

L3L4分别是∑的正闭包和克林闭包;

L5L7L6,但L5L7= L8;同样L9L10,但是我们有:L6ÌL5L7L9ÌL10

 

L6={0n1n|n1}中的句子中的01的个数是相同的,并且所有的0在所有的1的前面,L11={x|x∈∑+x01的个数相同}中的句子中虽然保持着0的个数和1的个数相等,但它并没要求所有的0在所有的1的前面。例如,01011100L11,但是0101Ï L61100ÏL6。而对"xL6,有xL11。所以,L6 ÌL11

 

   

"L∈∑*Ln次幂是一个语言,该语言定义为

n=0是,Ln={ε}

n1时,Ln= Ln-1L

    正闭包

   L+=LL2L3L4

    克林闭包

   L*= L0LL2L3L4

 

 

 

 


首页 所有文章 机器人 计算机视觉 自然语言处理 机器学习 编程随笔 关于