[音乐]
嗨,欢迎回来!我们接下来呢来介绍一些形式语言上的一些基本的一些概念和定义
那么按照什么是语言 按照我们说现代语言学家Chomsky他的定义是说
他是说只要是按着一定的规律来构成的这个句子和符号串
的一个集合,不管它是有限的集合或者是说无限的集合的话,那么就把这个
字符串的集合就称之为语言。
那么我们说形式语言呢就是主要研究一个 语言描述的问题。
就是如何描述这个一个语言 那么作为一个集合来说,我们说描述的方法有很多,比如说穷举法来描述
那么这个呢只适合于这个句子的数目有限的这些语言,我们可以把它
所有的字符串,所有的句子全都列举出来,穷举法
第二种呢是用语法描述的方法,那么所谓的语法呢就是一些
规则,我们通过一些有限的 替换规则,这个规则的数目是有限的,但是通过规则生成的
这个句子可能会是无穷多的,那么它可以用来生成,这些规则呢就
可以生成语言当中一些合格的句子,所谓的合乎语法的这些句子 那么第三种这个段描述法呢是所谓的检验。
我不是说 去生成它,而是说你给我一个串,或者说给我一个字符串,给我一个句子 我能够用一些算法或者用一些机器
自动机可以把它进行计算了以后,告诉你说哪
这些句子是不是属于这个语言,也就是是不是属于这个集合的这个合法的句子
那么我们下面来看看形式语言里头一些基本的概念
那么它主要是包含了字符串和词的这些概念 我们首先呢假设V是一个有限集合,把V当中的元素呢
就称之为字符,那既然是字符呢我们可以想象它可能
一般来讲,就是像ABCD这样子的字符,所谓的 字符。
当然它这当中的这个元素不一定是说我们看起来 说只有单个的这个字母,拉丁字母这样的形式就称之为这个字符
它当然也可以是个其他的一些,其它的形式,这个形式本身并不是特别的重要
只要它这个有一些元素,然后我们就可以把这些元素称之为字符 那么我们说由这个V当中字符相连起来的
比如说字符A,字符B然后连起来就是AB了 那么连起来这个有限的一个序列,这个序列呢就称之为
一个叫做字符串,那么字符串这个概念我们挺容易理解的,在
做学程序设计的时候,c语言编程的时候,它就有很多字符串,是吧
那么其中呢我们把不包含任何字符的这种串呢就称之为空串,记做ε
这个也容易理解就是一个空的 那么字符串所包含的字符的个数,它有几个,也就是称之为字符串的长度
那么记做s,然后两个竖杠。
那么 特别的呢空串的长度就为零,那么 我们把这个包含空串的V上的字符串的全体
就记做为V*,那么我们可见的只要这个V它是一个有限集合,而且它如果
至少包含了一个元素的话,一个字符的话,那么这个V*呢 它都是一个无穷的集合,因为它这个有限序列呢
即便你这个V当中只包含一个字符A,那么也可以是A,然后AA
AAA,AAAA,四个A,五个A,六个A,那么它也是一个无穷集合 这些全体我们就叫做V*
那么作为字符串呢有一些操作,比如说连接操作 我们可以把这个字符串呢做连接,比如说s=ab t
呢等于两个g gg,然后s这个字符串呢和t这个字符串进行连接,连接了以后呢实际上就是
把它们的所拥有的字符前后按照顺序给它放好,a bgg,这样的所谓的字符串连接的运算
那么字符串基于这个连接运算呢就有一个n次幂
那么n次幂呢就是对,s的n次幂就是s自身连接n次 那么我们特别的规定s的0次幂就等于空串,等于ε
那这样呢一次幂就等于自己,两次幂呢就等于自己呢再重复一次
那么对于字符串呢有这个连接和幂的 运算,对于字符串所构成的集合也有这个运算
我们说首先第一个呢就是乘积的运算,把两个字符串集合,A和B的集合
它的乘积呢就定义为s和t两个字符串的连接,其中呢s这个字符串来自于A t
呢来自于B,那这个乘积这个概念实际上我们看起来 很类似于这个两个集合的笛卡尔积的那种做法
只不过是说笛卡尔积呢是由两个元素然后构成的一个二元组,而这个字符串集合的这个乘积
它是把两个字符串呢连接在一起了,而且呢它的连接顺序是
这个A的字符串在左边,在前边,B的字符串在右边,在后边
这样的所谓的一个乘积,所以呢我们说无论是字符串的连接也好
字符串的集合的乘积也好当然肯定都不满足这个交换率,对吧
那么基于字符串集合的乘积呢它也有字符串集合的这个幂运算的概念
那么幂运算呢,A的n次幂就定义为A的负一次幂 和A的这个乘积,当然我们相应的规定A的0次幂
它的0次幂,这个字符串集合的0次幂呢就等于一个空串的集合 就是什么都没有。
那么例如,像A是 {aa, bb}。
然后B这个字符串上的集合呢包括了三个字符串{cc, dd,
ee} 那么我们这两个字符串集合的乘积呢它就是有六个字符串,其中呢
前面,左边就来自于A,右边来自于B,比方说aacc,是吧,aadd
然后或者说最后呢bbee,那么这样呢就是A的乘积 那么A的二次幂呢就是自身和自身进行做乘积
那么它就会有aaaa,然后aabb,bbaa和bbbb这四个字符串
那么关于这个字符串的这个 乘积它的幂运算以及呢如果把它的所有的可能
这个幂全部都做一个并集,那么就叫做一个闭包
那么称之为A的*,A*,那这是我们要注意这个跟那个V*还是不太一样的
这个A*呢这个A是字符串的集合,那么所以呢A*呢就等于A的0次幂
那A的0次幂就只包含一个空串,并集并上A的一次幂
这是这个A里头的所有的字符串,然后二次幂自己和自己连接一次 三次幂连接两次,然后这样的各种的这种组合
那么这种就称之A的闭包A* 那么如果把这个A的0次幂,这个空串排除在外的话
那么这就叫做正闭包,就叫A+,A+,这是一个正闭包的概念
那么对于字符串的集合呢,我们有一些描述的方法
比如说有限集合我们可以用列举法来把它进行描述
那当然如果你有一些,字符串集合有一些明显的 模式,我们也可以用一些另外的一手段来描述这个字符串的集合
那么我们这里介绍一个其中一种,我们非常常用的一种 手段,叫做正则表达式,英语叫做Regular
Expression 那既然它会叫做表达式,那我们肯定会想到它表达式是有,有值的,对吧
那你想的是没错的,那这个表达式它的值或者说它所对应的
是一个字符串的集合,但是这个表达式本身是有一些构造的条款的
首先呢它有几条这个规则 第一条规则说,ε这就是一个正则式
正则表达式,它所对应的这个字符串的集合呢就是有一个空串的集合 就是它自己代表自己。
那么第二条说x属于V,也就是说x呢是一个字符
它是一个单个的字符的话,它也,本身也是一个正则表达式,那么它对应的正则集呢就是
x单个字符所构成的长度为1的字符串所 形成的这个集合。
然后下面几条呢就是说是 是这个归纳条款哈,我们说一二呢都是属于这个基础条款
那我们其实可以把它看待说是一个这个归纳定义,那么它 是说如果α、
β都是正则表达式的话,那么α、 β把它放到一起 也是一个正则表达式。
那么它所对应的正则集合呢,就是α所对应的字符上集合A 和β所对应的字符上的集合B的乘积,乘积
第四条呢是说α、 β都是正则表达式的话,那么α、 β
当中加一个竖杠然后加一个括号,那么它也是这个正则表达式 那么它对应的正则集合呢,就是α所对应的集合A
和β所对应的集合B,它的两个集合的并集 它的并集。
第五呢是说如果α是 一个正则表达式,那么α加括号然后加一个星号
那么这个呢也是一个表达式,那么它所对应的正则集合呢 就是α所对应的那个字符串集合的闭包
它的闭包A*,那我们知道闭包呢就是空串再加上
A上的所有的字符串,再加上跟自身的连接,一次连接,两次连接 然后有限多次的连接已至于无穷,这样子的
所以呢这五条就构成了这个正则表达式 那么我们说在V上一个字符集
的V上的正则表达式它就对应和描述了V*的一个子集
那么也就是说所谓的V*的子集其实就是字符串的一个集合了,就是一个字符串集合
那么这个集合呢可能是有限的也可能是无限的,总之呢 既然是字符上的集合,那就是语言,对吧?按照我们的形式语言的定义它就是一个语言
那么我们特别呢把这个正则表达式所对应和描述的这种字符上的集合呢
就称之为正则子集,正则集合 比如说V是由两个字符a,b所对应的
构成的一个字符集,那么我们这些呢,就可以看到一些正则表达式
比如说ab*b这个正则表达式它就描述了a
然后b*呢,它因为它是从,可以是b的零次或多次重复,所以呢
它可以首先呢可以没有中间那个b,所以呢就是a和后边的那个b
那么b*呢就会重复一个abb,两个b就是abb,然后后面还有一个b,所以呢
它所描述的集合呢是a开始b结尾然后中间呢有
若干个b的这么一个模式的所有的这些字符串所构成的一个集合
第二个正则表达式呢ab*,那么它就描述的是以a开头
然后呢后面呢有零个或多个b的这样的字符串,所有的字符串构成的集合
那么a*b*那么它就描述了
首先呢它空串是有的,然后呢a没有b
或者说单有b没有a,那么后边的整个的如果归纳起来的就是说
如果要么呢你就是只有a,要么只有b
如果你同时有a和b的话,那么它的模式就是a呢会在b的左边
就是说它们两个呢是有一个呢泾渭分明的一个分界 你如果有a,就a呢必须都排在这个b的左边
然后有b,b呢就必须排在a的右边,那a和b的这个数量
它们相对的数量是没有任何限制的,它是描述这么一个字符串的集合
那么最后一个例子就是ab*,那么ab*呢就是a,b这个这个
字符串呢它会重复若干遍,那么比如说零次那么就是一个空串 一次呢就是ab,然后两次呢就是abab
那我们注意呢是ab这个模式的重复噢,重复若干多次 所以呢它描述了这么一个集合