正规表达式与正规集在线视频

同学们

我们在利用计算机处理问题的时候

总是会问

什么样的东西才能够被

有效地自动计算呢

经验告诉我们

首先需要对问题

进行形式化的描述

在前几节当中

我们讨论的正规文法

和有限状态自动机

都是正规语言的形式化描述模型

正则文法定义了语言

有限状态自动机去识别这样的语言

这一节我们将讨论的是正规式

正规式是更简单 更容易处理

而且更接近语言集合一种表示方法

首先 正规表达式和正则文法

都是描述正规语言的

而状态转换图可以构造词法分析程序

但是它属于非形式化的描述

对于同一等价的正规语言

正规式 正则文法 有限状态自动机之间

是可以等价转换的

正则表达式

我们简称为正规式

是单词识别的形式化表示方法

所谓形式化的方法

就是指用一整套带有严格规定的

符号体系来描述问题的方法

它的优点就是可以让问题

更加的清晰和准确

正则文法描述的是正则语言

与正规式描述的正规集是等价的

假设Σ是语言的有限字母表

我们辅助的字母表

Σ’={Φ ,ε , | , · , * , ( )

在Σ上面的正规式和正规集

可以按照下面的规则来进行递归定义

如果ε和Φ 是Σ上面的正规式

那么他们所表示的正规集

分别是{ε}和{Φ}

对于字母表上面的任何输入符号a∈∑

a都是∑上的一个正规式

它所表示的正规集呢

就是集合当中有一个符号{a}

接下来我们就可以按照

下面的这些归纳规则

根据已有的正规式和正规集

来生成对应的正规式和正规集

假设U和V都是Σ上面的正规式

它们所表示的正规集分别为L(U)和L(V)

那么U | V U·V (U)* 也是正规式

它们所表示的正规集分别是

L(U)∪L(V)

L(U)L(V)

还有就是(L(U))*

这个当中我们会发现

有一些正规式的运算

正规式的运算优先级依次为

*(闭包) ?(连接)和| (或)

它们的结核性都是左结合

这样 书写正规式的时候

可以省去括号

不致于造成混淆

仅由有限次使用规则(1)和规则(2)

得到的表达式是Σ上面的正规式

它所表示的集合是Σ上面的正规集

这就是正规式递归定义的终止规则

假设R S T是正规式

正规式是服从这些代数规则的

首先 “或”服从交换律

其次“或”还服从结合率

“连接”也服从结合率

正规式还满足分配运算

比如说R(S | T) = RS | RT

还有就是同一律

比如说εR = Rε = R

那么ε就是“连接”的恒等元素

正规式的运算也满足抽取律

比如说r | r=r

r*=ε|r|rr|…

或更多的r的连接

有了正规式和正规集的定义

我们可以来描述正规式对应的正规集

例如我们来看下这个例子

正规式ba*

那么对应的正规集就是

在字母表上面所有的以b为首的

并且后面跟着若干个a的字

第二个例子 a(a|b)*

那么它对应的正规集就是在

符号表上面所有以a为首的字

第三个例子当中呢

(a|b)* (aa|bb) (a|b)*

它描述的字符串它的特点是

在字母表上面所有含着连续两个

aa或者是bb的字

接下来我们来再看下这个例子

假设字母表上面只有两个字母a和b

那么正规式是a(a | b)*

那么这个正规式

描述的正规集是什么呢

我们根据正规集的定义

那么根据正规集的定义

L(R)=L(a(a | b)*)

根据连接运算的规则

它就等于L(a)L((a | b)*)

再根据闭包运算的规则

可以将刚才的式子转换成

L(a)(L(a | b))*

经过推导就可以得到这个正规式

定义的正规集了

那么我们发现了

如果a代表的是字母

而b代表是数字的话

正规式就变成了字母(字母|数字) *

它所表示的正规集当中的

每个单词的模式

是以字母开头的字母和数字的符号串

这就是多数程序设计语言允许的

标识符它的词法规则

我们再来看下这个例子

对于Σ上面的正规式R和S

如果它们正规集满足L(R)=L(S)

那么我们就说R和S是等价的

以及我们可以记作R=S

那么接下来我们判断一下

这几个正规式它是否等价呢

首先我们来看一下第一个例子当中的

(a | b)* 它所对应的正规集是

a和b可以交替出现的

这样的一个字符串

比如说abbaaaba…

而 a* | b* 这个正规式

所描述的正规集

只可能出现任意多个a

或者是任意多个b

那么因为两个正规式

它所对应的正规集并不等价

所以这两个正规式也并不是等价的

接下来我们来看一下

第二个例子当中

(ab)*所描述的正规集

这个正规集它有一个特点

就是任意个ab对出现

比如说像这样的一个字符串ababab…

而a*b*这个正规式

所对应的正规集则是

先出现任意多个a

后面接着出现任意多个b

那么因此这两个正规式也并不等价

在这一小节当中

我们主要是讨论了另一种

描述语言的形式化方法

就是正规式

我们从正规式和正规集的递归定义说起

讨论了正规式它的等价性问题

今天的课就到这里

谢谢大家