正则表达式和有限自动机

《正则表达式和有限自动机》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、语言与计算理论导引正则表达式和有限自动机第二部分正规语言和有限自动机语言往往是无限集，但描述的方法往往是有限的，一种方法是描述如何通过字符串操作由简单的字符串产生整个语言，或者描述如何通过集合操作由简单语言产生复杂语言。另一种方法是描述识别字符串是否属于某个语言的机制，也就是描述一个算法过程。本书考察的最简单的语言类是正规语言，正规语言能够通过应用有限次的某个标准操作从一元语言产生。正规语言能够被有限自动机识别，有限自动机是空间严格受限的简单机器。在第二部分，我们还考察正规语言的另外一些特点：1）导出将一种语言的描述翻译

2、成另一种语言的描述的算法；2）使用形式化方法描述语言；3）正规语言在实际中的应用。3正则表达式和有限自动机3.1正则语言和正则表达式注意：regularlanguage和regularexpression有时也翻译成正规语言和正规表达式。正则语言可以从非常简单的表达式得到，初始语言的字符串为空或单字母，仅使用合并、连接和Kleene连接运算，因此正则语言可用一个清楚的表达式描述，通常用小括号()代替大括号{}，+代替È，称为正则表达式。下面是一些定义在字母表{0,1}上的正则表达式，通过这些例子，能够感受到书写正则表达式

3、的一些规律。语言相应的正则表达式{L}L{0}0{001}或{0}{0}{1}001{0,1}或{0}È{1}0+1{0,10}或{0}È{10}0+10{1,L}{001}(1+L)001{110}*{0,1}(110)*(0+1){1}*{10}1*10{10,111,11010}*(10+111+11010)*{0,10}*({11}*È{001,L})(0+10)*((11)*+001+L)我们认为正则表达式表示的是相应语言的“最典型的字符串”，比如，1*10表示一个字符串，它以10结束，前面可以有任意多个数目的

4、1。我们在前面将正则语言描述成：在最简单的语言上仅仅使用三种运算合并、连接、Kleene连接所得到的语言。这种描述预示了正则语言的递归定义（参见2.4节）。下面递归定义不仅定义了语言，而且定义了正则表达式。定义3.1字母表å上正则语言类R，及其相应的正则表达式定义如下：14陶晓鹏Copyright2003语言与计算理论导引正则表达式和有限自动机1.空集f（即空语言）是正则语言，表达式是f。2.{L}仅有空串的语言是正则语言，表达式是L。3.每个aÎå，{a}是正则语言，表达式是a。4.如果L1和L2是正则语言，表达式是r

5、1和r2，则(a)L1ÈL2是正则语言，表达式是r1+r2。(b)L1L2是正则语言，表达式是r1r2。(c)L1*是正则语言，表达式是r1*。只有应用上面4条规则产生的语言才是字母表å上的正则语言。对上面的解释做些解释。为了保持一致性和连贯性，空语言被认为是正则语言。后面许多地方将提到这样的说法：对于每个…，都对应一个正则语言。如果空语言不属于正则语言，那么每个这样的说法还需要排除空语言这种特殊情况，带来不简洁的说法。为了书写简洁，省去大量的括号，我们规定正则表达式中运算符的优先级次序是Kleene*、连接、合并。同时

6、我们借用一些代数表达式的符号，如指数幂等。原表达式简洁表达式(rr)r2(a+((b*)c))a+b*c((r*)r)r+同样借助代数学的记号，两个表示不同语言的正则表达式可以使用符号¹，比如：(a+b)*¹a+b*我们还可以借用符号=来化简正则表达式，如正则表达式的化简1*(1+L)=1*1*1*=1*0*+1*=1*+0*(0*1*)*=(0+1)*(0+1)*01(0+1)*+1*0*=(0+1)*其中一些化简用到的规则可以从集合运算规则得到，但另有一些是字符串运算特有的，目前我们还没有发现这种化简的系统的方法（或

7、形式化方法），但上面的例子预示了化简的巨大作用。比如最后一行的例子，两个看似很复杂的语言，它们的并集却很简单。问题：存不存在化简正则表达式的形式化方法（既是否存在化简正则表达式的通用算法）？是否存在最简洁的正则表达式？朱洪来信：我的印象中，它是NP-完全的问题。PleaselookatGareyandJohnson'sbook:computerandintractibility.14陶晓鹏Copyright2003语言与计算理论导引正则表达式和有限自动机例子3.1语言LÍ{0,1}*，由所有长度为偶数的字符串组成，（由于

8、0是偶数，因此空串L属于L），问：L是否是正则语言？如果是，L对应的正则表达式是什么？解答：任何一个偶数长度的字符串都由多个（或0个）长度为2的字符串连接而成，而字母表{0,1}上的长度为2的字符串只可能是4个：00、01、10、11，因此L可定义如下：L={00,01,10,11}*它的正则表达式是：(00+01+