形式语言与自动机 第四章 正则表达式 南京航空航天大学 计算机科学与技术学院 关东海

Presentation on theme: "形式语言与自动机 第四章 正则表达式 南京航空航天大学 计算机科学与技术学院 关东海"— Presentation transcript:

1 形式语言与自动机 第四章 正则表达式 南京航空航天大学 计算机科学与技术学院 关东海 dhguan@nuaa.edu.cn
第四章 正则表达式 南京航空航天大学 计算机科学与技术学院 关东海 2015年春季学期

2 第四章 正则表达式 1.1 正则表达式的定义 1.2 正则表达式和有穷自动机的关系 1.3 正则表达式的等价变换 1.4 正则表达式的应用
第四章 正则表达式 1.1 正则表达式的定义 1.2 正则表达式和有穷自动机的关系 1.3 正则表达式的等价变换 1.4 正则表达式的应用 正则表达式[1]的“鼻祖”或许可一直追溯到科学家对人类神经系统工作原理的早期研究。美国新泽西州的Warren McCulloch和出生在美国底特律的Walter Pitts这两位神经生理方面的科学家，研究出了一种用数学方式来描述神经网络的新方法，他们创造性地将神经系统中的神经元描述成了小而简单的自动控制元，从而作出了一项伟大的工作革新。 在1956 年,出生在被马克·吐温（Mark Twain）称为“美国最美丽的城市之一”的哈特福德市的一位名叫Stephen Kleene的数学科学家，他在Warren McCulloch和Walter Pitts早期工作的基础之上，发表了一篇题目是《神经网事件的表示法》的论文，利用称之为正则集合的数学符号来描述此模型，引入了正则表达式的概念。正则表达式被作为用来描述其称之为“正则集的代数”的一种表达式，因而采用了“正则表达式”这个术语。 之后一段时间，人们发现可以将这一工作成果应用于其他方面。Ken Thompson就把这一成果应用于计算搜索算法的一些早期研究，Ken Thompson是 Unix的主要发明人，也就是大名鼎鼎的Unix之父。Unix之父将此符号系统引入编辑器QED，然后是Unix上的编辑器ed，并最终引入grep。Jeffrey Friedl 在其著作《Mastering Regular Expressions (2nd edition)》（中文版译作：精通正则表达式，已出到第三版）中对此作了进一步阐述讲解，如果你希望更多了解正则表达式理论和历史，推荐你看看这本书。 自此以后，正则表达式被广泛地应用到各种UNIX或类似于UNIX的工具中，如大家熟知的Perl。Perl的正则表达式源自于Henry Spencer编写的regex，之后已演化成了pcre（Perl兼容正则表达式Perl Compatible Regular Expressions），pcre是一个由Philip Hazel开发的、为很多现代工具所使用的库。正则表达式的第一个实用应用程序即为Unix中的 qed 编辑器。 然后，正则表达式在各种计算机语言或各种应用领域得到了广大的应用和发展，演变成为计算机技术森林中的一只形神美丽且声音动听的百灵鸟。 以上是关于正则表达式的起源和发展的历史描述，如今正则表达式在基于文本的编辑器和搜索工具中依然占据这一个非常重要的地位。 在最近的六十年中，正则表达式逐渐从模糊而深奥的数学概念，发展成为在计算机各类工具和软件包应用中的主要功能。不仅仅众多UNIX工具支持正则表达式，近二十年来，在WINDOWS的阵营下，正则表达式的思想和应用在大部分 Windows 开发者工具包中得到支持和嵌入应用！从正则式在Microsoft Visual Basic 6 或 Microsoft VBScript到.NET Framework中的探索和发展，WINDOWS系列产品对正则表达式的支持发展到无与伦比的高度，几乎所有 Microsoft 开发者和所有.NET语言都可以使用正则表达式。如果你是一位接触计算机语言的工作者，那么你会在主流操作系统（*nix[Linux, Unix等]、Windows、HP、BeOS等）、主流的开发语言（PHP、C#、Java、C++、VB、Javascript、Ruby以及python等）、数以亿万计的各种应用软件中，都可以看到正则表达式优美的舞姿。

3 1.1 正则表达式定义 正则表达式（Regular Expression:Regex）的由来
人类神经系统如何工作的早期研究: Warren McCulloch 和 Walter Pitts 两位神经生理学家研究出一种数学方式来描述这些神经网络; 1956 年, 一位Stephen Kleene 的数学家在 McCulloch 和 Pitts 早期工作的基础上，发表了标题为“神经网事件的表示法”的论文，引入了正则表达式的概念; Ken Thompson 是 Unix 的主要发明人;正则表达式的第一个实用应用程序就是 Unix 中的 qed 编辑器; Jeffrey Friedl 在其著作《Mastering Regular Expressions 》（中文版译作：精通正则表达式，第三版） 正则表达式[1]的“鼻祖”或许可一直追溯到科学家对人类神经系统工作原理的早期研究。美国新泽西州的Warren McCulloch和出生在美国底特律的Walter Pitts这两位神经生理方面的科学家，研究出了一种用数学方式来描述神经网络的新方法，他们创造性地将神经系统中的神经元描述成了小而简单的自动控制元，从而作出了一项伟大的工作革新。 在1956 年,出生在被马克·吐温（Mark Twain）称为“美国最美丽的城市之一”的哈特福德市的一位名叫Stephen Kleene的数学科学家，他在Warren McCulloch和Walter Pitts早期工作的基础之上，发表了一篇题目是《神经网事件的表示法》的论文，利用称之为正则集合的数学符号来描述此模型，引入了正则表达式的概念。正则表达式被作为用来描述其称之为“正则集的代数”的一种表达式，因而采用了“正则表达式”这个术语。 之后一段时间，人们发现可以将这一工作成果应用于其他方面。Ken Thompson就把这一成果应用于计算搜索算法的一些早期研究，Ken Thompson是 Unix的主要发明人，也就是大名鼎鼎的Unix之父。Unix之父将此符号系统引入编辑器QED，然后是Unix上的编辑器ed，并最终引入grep。Jeffrey Friedl 在其著作《Mastering Regular Expressions (2nd edition)》（中文版译作：精通正则表达式，已出到第三版）中对此作了进一步阐述讲解，如果你希望更多了解正则表达式理论和历史，推荐你看看这本书。 自此以后，正则表达式被广泛地应用到各种UNIX或类似于UNIX的工具中，如大家熟知的Perl。Perl的正则表达式源自于Henry Spencer编写的regex，之后已演化成了pcre（Perl兼容正则表达式Perl Compatible Regular Expressions），pcre是一个由Philip Hazel开发的、为很多现代工具所使用的库。正则表达式的第一个实用应用程序即为Unix中的 qed 编辑器。 然后，正则表达式在各种计算机语言或各种应用领域得到了广大的应用和发展，演变成为计算机技术森林中的一只形神美丽且声音动听的百灵鸟。 以上是关于正则表达式的起源和发展的历史描述，如今正则表达式在基于文本的编辑器和搜索工具中依然占据这一个非常重要的地位。 在最近的六十年中，正则表达式逐渐从模糊而深奥的数学概念，发展成为在计算机各类工具和软件包应用中的主要功能。不仅仅众多UNIX工具支持正则表达式，近二十年来，在WINDOWS的阵营下，正则表达式的思想和应用在大部分 Windows 开发者工具包中得到支持和嵌入应用！从正则式在Microsoft Visual Basic 6 或 Microsoft VBScript到.NET Framework中的探索和发展，WINDOWS系列产品对正则表达式的支持发展到无与伦比的高度，几乎所有 Microsoft 开发者和所有.NET语言都可以使用正则表达式。如果你是一位接触计算机语言的工作者，那么你会在主流操作系统（*nix[Linux, Unix等]、Windows、HP、BeOS等）、主流的开发语言（PHP、C#、Java、C++、VB、Javascript、Ruby以及python等）、数以亿万计的各种应用软件中，都可以看到正则表达式优美的舞姿。

4 正则表达式示例 例4.1 在字母表{0，1}上，0*1+1*0表示： 例4.2 在字母表{a，b}上，(a+b)*aaa(a+b)*表示：
例4.1 在字母表{0，1}上，0*1+1*0表示： 出现若干个0后以一个1结尾，或者出现若干个1后以一个0结尾的一切字符串的集合。 用集合的表示形式就是{0}*{1}∪{1}*{0}； 例4.2 在字母表{a，b}上，(a+b)*aaa(a+b)*表示： 字符串中至少要连续出现三个a。 用集合的表示形式就是{a,b}*{aaa}{a,b}* 正则表达式和它所代表的集合形式上有很大的相似性。大致上，正则表达式的“+”相当于集合中的并运算符“∪”，正则表达式的“*”与集合中的闭包运算符一致，正则表达式的“连接”相当于集合的连接运算。 正则表达式和它所代表的集合形式上有很大的相似性。大致上，正则表达式的“+”相当于集合中的并运算符“∪”，正则表达式的“*”与集合中的闭包运算符一致，正则表达式的“连接”相当于集合的连接运算。

5 正则表达式的递归定义 定义 4.1 设∑是一个字母表，∑上的正则表达式以及由它们代表的集合，递归定义如下：
定义 4.1 设∑是一个字母表，∑上的正则表达式以及由它们代表的集合，递归定义如下： (1) φ是一个正则表达式，代表空集。 (2) ε是一个正则表达式，代表集合{ε}。 (3) 对于∑中每个符号a , a是正则表达式，代表集合{a}。 (4) 如果r和s是正则表达式，分别代表集合R和S，则 (r+s),(rs)和(r*)是正则表达式，分别代表集合R∪S, RS和R*。 正则表达式R代表的字符串集合记为L(R)。 正则表达式一般用粗体来表示。 正则表达式与其所代表的语言集合之间的关系其实就是一种语法与语义的关系。

6 正则表达式示例 例4.3 给出∑={a，b},则对∑上的一些正则表达式与它们各自所代表的集合列表示于图4.1中： 正则表达式r
代表的集合L(r) φ ε a b (a+b) (ab) （a*） ((a+b)*) (a(b*)) ((((a*)b)(a*))) {ε} {a} {b} {a,b} {ab} {a}* {a,b}* {a}{b}* {a}*{b}{a}*

7 正则表达式表示的约定 为了尽量减少括号，做如下的约定： （1）每个正则表达式最外层的一对括号可以省略。
（2）规定正则表达式构造的优先次序为： ① * 最高级 ② 连接（如 rs ） 次高级 ③ 最低级 凡是符合此种顺序的，括号可以省略。 （3）同一种构造（如同为 +，连接或 *）连续出现时，规定从左到右依 次构造，中间的括号可以省略。 例如（（0（1*））+0）就可写成01*+0，(((a*)(b)(a*))就可写成a*ba*。但是，(a+b)* 不可写成a+b*，因为前者表示先构造(a+b)，后构造(a+b)*，结果代表集合{a,b}*；而后者根据优先次序的约定，表示先构造b*, 再构造a+b*，结果代表集合{a,{b*}}；这两个集合显然是不相等的。

8 正则表达式的示例 例4.5 构造一个正则表达式，使它能代表如下的集合S：S的每个元素都是倒数第十个字符是1的0、1串。
即使构造一个NFA接受这个S，也要设11个状态和20个δ函数，若是用DFA那就更复杂了。 要用一个正则表达式来代表S，就简单多了： (0+1)*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)

9 正则表达式 ---> 字符串集合 S = {0, 1} 01* = 0(1*) = {0, 01, 011, 0111, …}
0 后面跟上任意多个1 (01*)(01) = {001, 0101, 01101, , …} 0后面跟上任意多个1，然后以01结尾

10 正则表达式 ---> 字符串集合 0+1 = {0, 1} 长度为1的字符串集合 (0+1)*
= {e, 0, 1, 00, 01, 10, 11, …} 任意的字符串 (0+1)*010 以 010 结尾的字符串 (0+1)*01(0+1)* 包含 01 的所有字符串集合

11 正则表达式 ---> 字符串集合 ((0+1)(0+1))*+((0+1)(0+1)(0+1))* 所有字符串长度是偶数或3的倍数
= 串长为 0, 2, 3, 4, 6, 8, 9, 10, 12, ... ((0+1)(0+1))* 串长为偶数 (0+1)(0+1) 串长为2 ((0+1)(0+1)(0+1))* 串长为3的倍数 (0+1)(0+1)(0+1) 串长为3

12 正则表达式 ---> 字符串集合 ((0+1)(0+1)+(0+1)(0+1)(0+1))* 字符串可以划分为长度为2或3的子串
长度为2或3的串 (0+1)(0+1) 长度为2的串 (0+1)(0+1)(0+1) 长度为 3的串

13 正则表达式 ---> 字符串集合 011010110 ((0+1)(0+1)+(0+1)(0+1)(0+1))*
字符串可以划分为长度为2或3的子串 e ✓ 1 ✗ 10 ✓ 011 ✓ 00110 ✓ ✓ 包括了所有的字符串，除了长度为1的串 ((0+1)(0+1)+(0+1)(0+1)(0+1))* = 除了0，1之外的所有的字符串

14 正则表达式 ---> 字符串集合 (1+01+001)*(+0+00) 0110010110 0010010 最多两个 0
在两个1之间的最多只有两个0； 永远不能出现连续的三个0 结论：( )*(+0+00) = {x:|x 不包含子串 000} e 00

15 字符串集合-->正则表达式 构造一个包含连续两个0的字符串集合的正则表达式. S = {0, 1}
(任意符号串) 00 (任意符号串) (0+1)*00(0+1)*

16 字符串集合-->正则表达式 构造一个不包含两个连续0的字符串集合的正则表达式： 1110110101101010 S = {0, 1}
开始的的 时候可能有多个1 每个0后面跟上 至少一个1 结尾有可能是一个0 (011*) ... every middle每个0后面跟上至少一个1 (e + 0) ... 在末尾最多只能有一个0 1*(011*)*(e + 0)

17 字符串集合-->正则表达式 构造一个字符串中包含偶数个0的集合的正则表达式： S = {0, 1}
偶数个0 = (包含两个0的子串)* 包含两个0的串 = 1*01*01* (1*01*01*)*

18 1.2 正则表达式和有穷自动机的关系 定理4.1 设r是一个正则表达式，则存在一个具有ε-转移的有穷自动机接受L（r）。
证明 ： （结构归纳法） 归纳基础 设构成r的构造数目为0，即r是没有经过任何“+”、“连接”和“*”构造的正则表达式，因此它只能是 φ，ε 或 ∑中的某个符号a，下面针对这三种情况分别讨论。 （1）r=φ, 对应的 NFA M是： 不能从初始状态q0到达终结状态qf ，所以这个NFA 只能接受空集。

19 正则表达式 -->有穷自动机 （2）r=ε, 对应的 NFA M是：
正则表达式 -->有穷自动机 （2）r=ε, 对应的 NFA M是： 因为q0既是初始状态，又是终结状态，同时M也没有其他转移动作，所以这个NFA 只能接受{ε}。 （3）r=a (a∈∑), 对应的 NFA M是： 因为这个NFA只有一个转移r函数δ(q0 ,a)={qf},而qf又是终结状态，所以这个NFA 只接受{a}。

20 正则表达式-->有穷自动机 归纳步骤 设对少于i(i≥1)次构造构成的正则表达式命题成立，现在的正则表达式r由i次构造构成。根据r最后一次构成的形式，分三种情况讨论： 情况1 r = r1 + r2 。这里r1 和r2都是由少于i次构造构成的正则表达式，所以根据归纳法假设，存在NFA M1 =（ Q1 ,∑1 ,δ1 ,q1 ,{f1}）,使得L(M1)=L(r1)；存在NFA M2 =（ Q2 ,∑2 ,δ2 ,q2 ,{f2}）,使得L(M2)=L(r2)。不妨假定Q1 , Q2不相交，现构造新的NFA M = (Q1 ∪ Q2∪{q0 ,f0}, ∑1∪∑2 ,δ,q0 ,{f0}),其中δ定义为： （1）δ(q0 ,ε)={q1 ,q2}； （2）对于Q1-{f1}中的q ,∑1∪{ε}中的a： δ(q ,a)= δ1(q ,a)； （3）对于Q2-{f2}中的q ,∑2∪{ε}中的a：δ(q ,a)= δ2(q ,a)； （4）δ(f1 ,ε)={f0},δ(f2 ,ε)={f0}。

21 正则表达式-->有穷自动机 对于新构造的这个ε-NFA M，用图表示如下：
M从它的初始状态q0出发，不用读任何符号即可同时进入M1和M2，然后，完全模拟M1和M2的动作，直到达到它们各自的终结状态f1和f2 。M在这两个状态上，也不用读任何符号即可进入它自己的终结状态f0 。显然，M接受的集合恰好是M1和M2接受的集合的并集，即L(M)= L(M1)∪L(M2)。

22 正则表达式-->有穷自动机 情况2 r = r1 r2 。设M1和M2与在情况1中的表示相同，仍假定Q1 , Q2不相交，现构造新的NFA M = (Q1 ∪ Q2 , ∑1∪∑2 ,δ,q1 ,{f2}),其中δ定义为： (1)对于Q1-{f1}中的q ,∑1∪{ε}中的a， δ(q ,a)= δ1(q ,a)； (2)δ(f1 ,ε)={q2}； (3) 对于Q2中的q ,∑2∪{ε}中的a， δ(q ,a)= δ2(q ,a)。 可以看出，M从它的初始状态q1（也是M1的初始状态）出发，开始模拟M1的动作，到达M1的终结状态f1以后，不用读任何符号马上转移到M2的初始状态q2 ，然后继续模拟M2的动作，到达M2的终结状态f2，也就是到达了M的终结状态。显然，M接受的集合恰好是M1接受的集合和M2接受的集合的连接，也就是L(M)= L(M1)L(M2)。

23 正则表达式-->有穷自动机 情况3 r = r1* 。r1是由少于i次构造构成的正则表达式，所以根据归纳法假设，存在NFA M1 =（ Q1 ,∑1 ,δ1 ,q1 ,{f1}）,使得L(M1)=L(r1)。现在构造ε-NFA M =（Q1 ∪{q0,f0},∑1 ,δ1 ,q0 ,{f0}）,其中δ定义为： (1)δ(q0 ,ε)={q1,f0}； (2)对于Q1-{f1}中的q ,∑1∪{ε}中的a， δ(q ,a)= δ1(q ,a)； (3)δ(f1,ε)={q1,f0}。 可以看出，M从q0出发有两个ε转移，一个是进入M1的初始状态q1 ，开始模拟M1的动作；另一个是直接到M的终结状态f0，使M能接受空串ε。当M1到达它的终结状态f1后，又有两个ε转移，一个是返回到M1的初始状态q1，继续模拟M1的动作，以保证M能重复接受M1所能接受的一切字符串；另一个是到M的终结状态f0，结束M的动作。因此，M所接受的集合恰好是 M1所接受集合的闭包，即L(M)=L(M1)*。定理证完。 考虑陈景润的说法，取*的情况为0,,1,2的时候分别考虑，再引申到一般情况。

24 正则表达式-->有穷自动机： Æ q0 q0 e q0 q1 a a  S RS q0 q1  NFAR NFAS

25 正则表达式-->有穷自动机： NFAR q0 q1  R + S NFAS q0 q1  R* NFAR

26 正则表达式-->有穷自动机 例4.6 根据定理4.1给出的构造方法，对正则表达式10*+0构造一个对应的NFA。

27 Road map  regular expression NFA

28 Road map regular expression NFA 2-state GNFA GNFA

29 有穷自动机-->正则表达式 定理4.2 如果L被一个DFA接受，则L可用一个正则表达式代表。
证明 设DFA: A =({q1,q2,…,qn},∑,δ,q1 ,F)中的状态进行1,2,3,...,n编号。编号可以是任意的，但是编号一旦定好，在定理证明过程中不能改变；其中1表示起始状态。 引入记号R（k)ij ,是字符串的集合，具体定义如下： R（k）ij ={x|δ(qi ,x)=qj ,且中间仅经过编号<= k的任何状态，i,j可以大于k。} (任何一个Rkij都可以构造一个正则表达式) 几何对称差代表 A并B-A交B

30 有穷自动机-->正则表达式 对Rkij的k取值进行归纳证明：（k取值从0开始） basis：（k=0） 当i≠j： 当i=j ：
induction: 解释为什么考虑k=0，因为存在自环、中间不经过任何点（直接连接）的情况。

31 有穷自动机-->正则表达式 例4.6 给出一个由图4.2表示的DFA M，按照定理4.2中的方法，构造一个正则表达式代表L(M)。
对于所有的i和j,以及k=0,1,2, rkij的值列在图4.3中。其中某些正则表达式已被化简。例如，根据定理4.2中的（4-1）式，r122 = r021(r011)* r012 + r022 = 0(ε)*0+ε,显然可以化简为00+ε。又例如，r213= r112（r122）* r123 + r113 =0(ε+ 00)*(1+01)+1,由于(ε+ 00)*可以化简成(00)*，(1+01)可以写成(ε+0)1，我们可以有r213=0(00)*(ε+0)1+1。更进一步，由于(00)*(ε+0)可以化简为0*，于是r213可以化简为00*1+1，最后化简为0*1。

32 有穷自动机-->正则表达式 k=0 k=1 k=2 rk11 rk12 rk13 rk21 rk22 rk23 rk31 rk32
图4.2中DFA的rkij表 k=0 k=1 k=2 rk11 rk12 rk13 rk21 rk22 rk23 rk31 rk32 rk33 ε 1 Φ 0+1 ε+00 1+01 (00)* 0(00)* 0*1 (0+1)(00)*0 (0+1)(00)* ε+(0+1)0*1

33 正则表达式的等价变换 "+"操作的交换律: R+S = S+R。因为：R+S代表集合L(R)∪L(S),而S+R代表集合L(S)∪L(R)，集合的并运算是满足交换律的; "+"操作的结合律: (R+S)+T = R+(S+T)； “连接”构造的结合律： (RS)T = R(ST)。 “连接”构造不满足交换律： 对于一般的正则表达式R和S，不能写RS = SR。 反例，如：R=1,S=0,它们分别代表集合{1}和{0}，RS代表集合{10}，而SR代表集合{01}，显然这两个集合是不相等的。

34 正则表达式的化简： φ+R = R+φ = R。根据正则表达式与它们所代表的集合的对应关系，等式正确; φ是构造符“+”的单位元。
φR = Rφ=φ。代表集合{}L(R)或L(R){}，任何集合与空集的连接结果都是空集。这就说明φ是连接构造的零元。 R(S+T)=RS+RT。 这一条称为“连接”对于“+”的左分配律。 (S+T)R=SR+TR。 这一条称为“连接”对于“+”的右分配律。 (R*)* = R* ； φ* =ε； ε* =ε； 扩充定义R+：代表集合：L(R)+ 。定律：①ε+ R+ = R* ，② R+ = RR*

35 发现正则表达式定律的一般方法 考虑一条所谓的定律：(R+S)* =(R* S*)* 这里R，S是任意两个正则表达式。
一般方法：将每个变量都当做一个不同的符号，即可将任何带变量的一般的正则表达式都看做一个具体的正则表达式，即一个没有变量的正则表达式。 例如，把表达式(R+S)*中的变量R和S分别换成符号a和b,就得出正则表达式(a+b)*。而这个正则表达式所代表的语言L((a+b)*)，显然是字符a和b组成的一切串的集合。另一方面，把表达式(R* S*)*的变量R和S也分别换成符号a和b, 就得出正则表达式(a* b*)*。而这个正则表达式所代表的语言L((a* b*)*)，显然也是字符a和b组成的一切串的集合。左右相等成立。 定理 4.4 设E是带有变量V1，V2，…Vm 的正则表达式，通过把Vi的每次出现，都换成符号ai（i=1，2，…,m）得到具体的表达式C。则从每个属于L(C)的串a1a2…ak出发，把每个符号ai（1≤i≤k）都换成对应语言L(Vi)，就构造出L(E)。

36 1.4 正则表达式的应用 UNIX中的正则表达式 词法分析 查找文本中的模式 ......