1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory教师教师：胡：胡春明、赵永望春明、赵永望第四章第四章 正则表达式与正则语言正则表达式与正则语言 http:/ 正则表达式正则表达式正则表达式的引入正则表达式的引入正则表达式的定义及性质正则表达式的定义及性质正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与正则文法等价正则表达式与正则文法等价正则语言等价描述模型总结正则语言等价描述模型总结正则表达式的引入正则表达式的引入有穷自动机描述模型：有穷自动机描述模型：例：设正则语言例：设正则语言： anbmck | n, m, k1 a
2、icnbxam | i0, n 1, m 2, x 是由是由 d 和和 e 组成的字符串组成的字符串 正则表达式的引入正则表达式的引入 FA 各状态对输入字符串的存储功能：各状态对输入字符串的存储功能：由于由于,所以所以,正则表达式的引入正则表达式的引入正则语言：正则语言：正则表达式：正则表达式：r = a+ b+ c+ + a*c+ b( d + e )*a+ a = a a*bb*cc* + a*cc*( d + e )*aaa*第四章第四章 正则表达式正则表达式正则表达式的引入正则表达式的引入正则表达式的定义及性质正则表达式的定义及性质正则表达式与有限自动机等价正则表达式与有限自动机等价
3、正则表达式与正则文法等价正则表达式与正则文法等价正则语言等价描述模型总结正则语言等价描述模型总结定义定义4-1：设字母表为：设字母表为 ，正则表达式递归定义如下：，正则表达式递归定义如下：正则表达式的定义及性质正则表达式的定义及性质例：设例：设 = 0，1 ， 中部分正则表达式及其对应语言如下：中部分正则表达式及其对应语言如下：正则表达式的定义及性质正则表达式的定义及性质定义定义4 - 2：设设 r 是字母表是字母表上的正则表达式，上的正则表达式，r 的的 n 次幂定义为：次幂定义为：满足性质：满足性质：L（r n）= （L（r）n,rn r m = r n + m, n, m0正则表达式的定
4、义及性质正则表达式的定义及性质表达式简化约定：表达式简化约定： - 减少括号减少括号1、r 的正闭包：的正闭包：2、运算符的优先级：、运算符的优先级： 闭包运算闭包运算 乘运算乘运算 加运算加运算 正则表达式的定义及性质正则表达式的定义及性质(0+1)*)000)(0+1)*) = (0+1)*000(0+1)*(0+1)*)(0+1)(0+1)*) = (0+1)*(0+1)(0+1)*表达式的简化约定：表达式的简化约定：3、意义明确时，正则表达式、意义明确时，正则表达式 r 表示的语言记为表示的语言记为 L（r），）， 也可直接记为也可直接记为 r。4、无扩号说明时，加、乘、闭包运算执行左
5、结合规则。、无扩号说明时，加、乘、闭包运算执行左结合规则。 例：例： R1 R2 R3 = （R1 R2）R3 R1 R2 R3 = （R1 R2）R3 正则表达式的定义及性质正则表达式的定义及性质定义定义4 - 3： 设设 r, s 分别为字母表分别为字母表 上的正则表达式上的正则表达式 ，如果，如果 L ( r ) = L ( s ), 则称表达式则称表达式 r 与与 s 相等（或等价），记作相等（或等价），记作 r = s。正则表达式的定义及性质正则表达式的定义及性质例：设例：设 = 0，1 ，上上正则表达式以及其表示的语言如下：正则表达式以及其表示的语言如下：1、L ( 00 )2、L
6、( 0+1 )* 00 (0+1)*) 3、L( 0+1 )*1 ( 0+1 )9)4、L（( 0+1 )*011）5、 L ( 0+1+2+ )6、 L ( 0*1*2* )7、 L ( 1 ( 0+1 )* 1 + 0 ( 0+1 )*0 )正则表达式表示的正则语言：正则表达式表示的正则语言：正则表达式的定义及性质正则表达式的定义及性质例：设例：设 = 0，1 ，上上正则表达式以及其表示的语言如下：正则表达式以及其表示的语言如下：1、L ( 00 ) =2、L( 0+1 )* 00 (0+1)*) = 3、L( 0+1 )*1 ( 0+1 )9) =4、L（( 0+1 )*011）=5、
7、L ( 0+1+2+ ) =6、 L ( 0*1*2* ) =7、 L ( 1 ( 0+1 )* 1 + 0 ( 0+1 )*0 ) =正则表达式表示的正则语言：正则表达式表示的正则语言：正则表达式的定义及性质正则表达式的定义及性质 00 。 x | x 是至少含两个连续是至少含两个连续 0 的串的串 x | x 是倒数第十个字符为是倒数第十个字符为 1 的串的串 x | x 是是 011 结尾的串结尾的串 。 0n 1m 2k | n, m, k1 。 0n 1m 2k | n, m, k0 。习题：习题：p.153, 2. 理解正则表达式理解正则表达式正则表达式的定义及性质正则表达式的定义
8、及性质习题：习题：p.153, 1. 写写出下列语言的表达式出下列语言的表达式正则表达式的定义及性质正则表达式的定义及性质可以证明，字母表可以证明，字母表 上上正则表达式正则表达式 r, t, s 及相关语言满足以下等式：及相关语言满足以下等式：正则表达式的定义及性质正则表达式的定义及性质例例1- 证证16式：式：L ( (r*) )* = L (r)*，其对应语言集合，其对应语言集合 ( R* )* = R*。证：施归纳于集合证：施归纳于集合 R 乘积的个数，求证乘积的个数，求证 （ R* )n = R* ( n 0 )。基础语句：基础语句： 设设 n = 0，1，（ R* )0 = ，（
9、R* )1 = R*，结论成立。，结论成立。归纳语句：设归纳语句：设 n 1,（ R* )n = R* 结论成立，证结论成立，证 ( R* )n+1 = R* 时结论成立时结论成立 ( R* )n+1 = ( R*)n R* = R*R*由归纳假设由归纳假设 = , R, R2, R3, , R, R2, R3, = , R, R2, R3, = R*正则表达式的定义及性质正则表达式的定义及性质由归纳原理可知，对任意整数由归纳原理可知，对任意整数 n, 有有 ( R* )n = R*; 因此，有，因此，有， ( R* )* = ( R* )0，( R* )1，( R* )2， ( R* )n，
10、 = ，R* = R* 证毕。证毕。例例2- 证证 ( 17 ) 式：式：L ( r s ) = L ( r + s ) 设设A、B为表达式为表达式 r、s 对应的正则集合，利用下列集合性质对应的正则集合，利用下列集合性质： ( 1 ) 若若A B 和和 C D，则，则 AC BD ； ( 2 ) An A ，n 0 （3） A A B ( 4 ) A B A （5） 若若 A B，则，则 A B ( 6 )（A ） = A A = A 正则表达式的定义及性质正则表达式的定义及性质证证 i : （ A B ） （ A B ） 由由 A A B 和（和（5）有：）有： A （A B ) 和和 B
11、 （ A B ) 由由 （1）有：）有： A B ( A B ) （ A B ) 由（由（ 6）有：）有： A B ( A B ) 由（由（5） 有：有：（A B ) ( ( A B ) ) 由（由（6 ）有：）有：（A B ) ( A B ) （ i 得证得证 )证证 ii：（：（ A B ） （ A B ） 由（由（2）有：）有： A A ， B B 由（由（3）有：）有： A A B 由（由（4）有：）有： B A B 由由(2)(3)(4)和传递率：和传递率： A B A B A B = A B 由（由（5）有：）有： （ A B ） （A B ） 由于集合（由于集合（A B ） 的正
12、则表达式为的正则表达式为 ( r*s* ) *； 集合（集合（A B） 的正则表达式为的正则表达式为 ( r + s ) * ； 所以有：所以有： ( r*s* ) * = ( r + s )* 由由 i 和和 ii 得：得： （A* B* ）* =（A B）* 正则表达式的定义及性质正则表达式的定义及性质（ii 得证）得证）（证毕）（证毕）习题：习题：p.154, 4. 正则表达式的定义及性质正则表达式的定义及性质第四章第四章 正则表达式正则表达式正则表达式的引入正则表达式的引入正则表达式的定义及性质正则表达式的定义及性质正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与正则文
13、法等价正则表达式与正则文法等价正则语言等价描述模型总结正则语言等价描述模型总结定义定义4-4： 称正则表达式称正则表达式 r 与自动机与自动机 FA 等价，如果有等价，如果有 L（r）= L（M）。）。正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与有限自动机等价定理定理 4-1： 正则表达式表示的语言是正则语言。正则表达式表示的语言是正则语言。证明思路：证明思路： 对字母表对字母表 上任意正则表达式上任意正则表达式 r，构造相应的，构造相应的 FA M，使得，使得 L（r）= L（M）；）； 1、归纳证明：施归纳于正则表达式运算符、归纳证明：施归纳于
14、正则表达式运算符 (+、连接、连接、*) 的个数的个数 2、构造、构造 FA M 的终止状态。的终止状态。 基础：基础： 设正则表达式运算符的个数设正则表达式运算符的个数 n = 0，构造，构造 FA 存在以下三种情况：存在以下三种情况： r =：有：有 - NFA 满足要求。满足要求。 r = ：有：有 - NFA 满足要求。满足要求。 r = a：有：有 - NFA 满足要求。满足要求。 结论对结论对 n = 0 成立。成立。正则表达式与有限自动机等价正则表达式与有限自动机等价1、对于、对于 r = r1 + r2，构造相应，构造相应-NFA。 假设假设 M1 = ， M2 = ，使得，使
15、得 L（M1）= L（r1），），L（M2）= L（r2）；并设）；并设 Q1 Q2 = 。 构造构造 FA M = , 其中其中 q0, f Q1 Q2， 定义：定义：1）( q0, ) = q01, q02 ， 2）对）对 q Q1 - f1 ，a ：( q, a ) = 1 ( q, a ) ； 对对 q Q2 - f2 ，a ：( q, a ) = 2 ( q, a ) ； 3） ( f1, ) = f ； ( f2, ) = f 由于由于1( f1, ) = 2( f2, ) = 归纳：归纳：设结论对运算符个数为设结论对运算符个数为 n k ( k0 )的表达式成立，证当的表达式成立
16、，证当 n = k + 1 时，结论仍然成立。添加运算符时时，结论仍然成立。添加运算符时, 存在存在 r1 + r2, r1r2, r* 三种情况。三种情况。正则表达式与有限自动机等价正则表达式与有限自动机等价1、构造与表达式、构造与表达式 r = r1 + r2 等价的等价的-NFA 的图示：的图示：正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与有限自动机等价1、对于、对于 r = r1 + r2，求证：，求证：L（r1 + r2）= L（M）。）。由归纳假设：由归纳假设： L（r1）= L（M1），）， L（r2）= L（M2）；）； 由正则表达
17、式性质：由正则表达式性质： L ( r1 + r2 ) = L ( r1 ) L ( r2 ) = L ( M1 ) L ( M2 )需证：需证： L（M1） L（M2）= L（M） 。 （ “ ” ）设设 x L（ M1 ） L（ M2 ），应有），应有 x L（ M1 ）或）或 x L（ M2 ），），假设假设 x L（M1），即，），即，1 ( q01, x ) = f1 ，于是有：，于是有：即有，即有，x L ( M )同理可证：同理可证： x L ( M2 ) 时，时，有有 x L（ M ）。）。正则表达式与有限自动机等价正则表达式与有限自动机等价设设 x L（M），即，），即， (
18、 q0, x ) = f ；由；由 M 定义：定义：证：证： L（M）= L（M1） L（M2） 。 （ “ ” ）1、求证：、求证： L（M）= L（r1+r2） 。由于已设由于已设 ( q0, x ) f 成立成立, 并且并且, 有有 f = 1 ( f1, ) = 2 ( f2, )必有，必有，1( q01, x ) = f1 ( x L( M1 ) 或者或者 2 ( q02, x) = f2 ( x L(M2) )故有，故有， x L（M1） x L（M2）。）。 （“ M 与与 r 等价等价 ” 证毕证毕 ）正则表达式与有限自动机等价正则表达式与有限自动机等价例例4： 给定正则表达式
19、给定正则表达式 r1 = 01* ，r2 = ( 01 )*，以及与其等价的，以及与其等价的 FA M1、M2 如下，构造与表达式如下，构造与表达式 r = r1 + r2 等价的等价的- NFA Mq02q2201q12q0110M1M21q0q12q02q2201q010qf解：解：正则表达式与有限自动机等价正则表达式与有限自动机等价2、对于、对于 r = r1r2，构造相应，构造相应-NFA。 假假设设 M1 = ，M2 = ，使得，使得 L（M1）= L（r1），），L（M2）= L（r2）；并设）；并设 Q1 Q2 = 。 构造构造 FA M = , 定义：定义：1）对）对 q Q1
20、 - f1 ，a ，( q, a ) = 1 ( q, a ) ； 2）对）对 q Q2， a ，( q, a ) = 2 ( q, a ) ； 3）( f1, ) = q02 ； 设设 ( f1, ) = ( f2, ) = 。归纳：归纳：设结论对运算符个数为设结论对运算符个数为 n k ( k0 )的表达式成立，证的表达式成立，证 n= k+ 1 时结论时结论仍然成立。由正则表达式定义仍然成立。由正则表达式定义, 存在存在 r1 + r2, r1r2, r* 三种情况。三种情况。正则表达式与有限自动机等价正则表达式与有限自动机等价2、构造与表达式、构造与表达式 r = r1r2 等价的等价
21、的-NFA 的图示：的图示：设设 x L（M1）L（M2），）， x = x1x2，有有 x1 L（M1）并且）并且 x2 L（M2 )；由于由于 q Q1, a, 由定义由定义( q, a ) = 1 ( q, a )故有故有( q01, x1 ) = 1 ( q01, x1 ) = f1 ；由于由于 qQ2, a , 由定义由定义( q, a ) = 2 ( q, a )故有故有( q02, x2 ) = 2 ( q02, x2 ) = f2 。正则表达式与有限自动机等价正则表达式与有限自动机等价2、对于、对于 r = r1r2 ，求证：，求证：L（r1 r2）= L（M）。）。由归纳假设
22、有：由归纳假设有： L ( r1 ) = L ( M1 )， L ( r2 ) = L ( M2 )；由正则表达式性质：由正则表达式性质： L ( r1 r2 ) = L ( r1 ) L ( r2 ) = L ( M1 ) L ( M2 )只需证：只需证： L（ M1 ）L（ M2 ）= L（ M ） 。 （ “ ”）故有，故有，x L（M）。）。正则表达式与有限自动机等价正则表达式与有限自动机等价2、求证：、求证： L（M）= L（r1 r2）。）。 即证：即证： L（M）= L（M1）L（M2）。）。 （ “ ” ）其中其中, ( q01, x1 ) = f1 , 即有，即有，x1 L（
23、M1）；）； ( f1, ) = q02 ( q02, x2 ) = f2 , 即有，即有，x2 L（M2）；）；从而，从而， x L（M ） L（M1）L（M2）。）。综上所述，综上所述，L（M）= L（M1） L（M2）成立）成立M 与与 r 等价等价 证毕。证毕。设设 x L（M），即有，），即有，( q01, x ) = f2 ，并且，并且 x = x1 x2，使得，使得，例例5： 设设 r1 = ( bc )* ，r2 = ( ba )* ；识别它们的；识别它们的 FA 分别为分别为 M1 和和 M2，构造与，构造与 r = r1r2 等价的等价的- NFA M。 q02q22M2a
24、bq01q12cbM1q02q22M2abq12cb sq013、对于、对于 r = r1*，构造相应，构造相应-NFA。 由归纳假设：由归纳假设： M1 = ， 使得使得 L（M1 ）= L（r1） 构造构造 FA M = , 其中，其中，q0, f Q1。 定义：对定义：对 q Q1 - f1 ，a ， 1） ( q, a ) = 1 ( q, a ) ； 2） ( q0, ) = q01, f ； 3） ( f1, ) = q01，f 。归纳：归纳：设结论对运算符个数为设结论对运算符个数为 n k ( k0 ) 的表达式成立，证的表达式成立，证 n = k + 1 时结时结论仍然成立。由
25、正则表达式定义论仍然成立。由正则表达式定义, 存在存在 r1 + r2, r1r2, r* 三种情况。三种情况。正则表达式与有限自动机等价正则表达式与有限自动机等价3、构造与表达式、构造与表达式 r = r1* 等价的等价的-NFA 的图示：的图示：正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与有限自动机等价3、对于、对于 r = r1*，求证：，求证：L ( M ) = L（M1）*证证: L ( M ) ( L ( M1 ) )*设设 x L（ M ），），如果如果 x =, 由克林闭包定义，显然有，由克林闭包定义，显然有， x = ( L (
26、M1 ) )*；如果如果 x , 则有则有 x = x1x2x3xn ( n1 ) 推导过程见右式。推导过程见右式。表明：表明： x1, x2, x3, x n L ( M1 )于是有：于是有： x = x1x2x3xn ( L ( M1 ) )*同理可证：同理可证：( L ( M1 ) )* L ( M )例例6：设表达式：设表达式 r1 = (ac)*ba 的的 FA M1如图所示，构造与如图所示，构造与 r = ( r1 )* = ( ac *ba )* 等价的等价的 - NFA M。q2 bq01q02aacq12q22q2 q0bq01q02aacq12q22qf例例7：构造与表达式
27、构造与表达式 ( 0+1 )*0 + ( 00 )* 等价的等价的 FA。几点说明：几点说明：1、由、由 “+”、“连接连接”、“*” 的证明过程可知，结论对的证明过程可知，结论对 上任意正上任意正则表达式成立，即，则表达式成立，即，“对于任意正则表达式，都存在一个等价的对于任意正则表达式，都存在一个等价的- NFA”。2、综合第三章结论：任意、综合第三章结论：任意 NFA 均有与之等价的均有与之等价的 DFA；有，；有， RE |=| - NFA |=| NFA |=| DFA 。正则表达式与有限自动机等价正则表达式与有限自动机等价例：例： 设设 r1 = 01* ，r2 = ( 01 )*
28、，求，求 r = r1 + r2 的的 DFA M。 解：解： 1、构造识别、构造识别 r1 和和 r2 的的 FA M1 和和 M2；正则表达式与有限自动机的等价性正则表达式与有限自动机的等价性q02q2201q11q0110M1M21q010q0q11q02q2201qf2、构造识别、构造识别 r = r1 + r2 的的 DFA M 的状态图与状态表：其中，的状态图与状态表：其中，始态始态( q0,) = q01, q02 ；终态；终态( q11, q02 ,) = qf 。3、画出、画出 DFA M 的状态图的状态图：令令 p0= q01, q02，p1= q11, q22， p2=
29、q11, q02，p3= q22 ， p4= q11 ， p5= q02 。p0p1p2p3p4p50001 111q01, q02q11, q22q11, q02 q22 q11 q02 2、由、由 NFA 求求 DFA 算法给出算法给出DFA M 的状态表：的状态表： q22 q02 终态终态 q11 q11 终态终态 q02 q22 q11 q22 q11, q02 终态终态 q11, q02 q11, q22 终态终态 q11, q22 q01, q02 始态始态10输入字符列输入字符列状态列状态列状态状态说明说明等价证明与转换算法：等价证明与转换算法： 给定有穷自动机给定有穷自动机
30、FA，利用图解法求相应等价的正则，利用图解法求相应等价的正则表达式。表达式。正则表达式与有限自动机等价正则表达式与有限自动机等价定义定义4-4： 称正则表达式称正则表达式 r 与自动机与自动机 FA 等价，如果有等价，如果有 L（r）= L（M）。）。2-1、 “图解图解法法”：1、预处理：预处理：删去删去 M 中所有不可达状态，并在中所有不可达状态，并在 M 的始态的始态 q0, 和终态和终态 f1, 两端分别添加用两端分别添加用-连接弧连接的连接弧连接的状态状态 X，Y，将，将 M 括起来；括起来；变换变换 1 - 去去 “并并” 弧：弧：2、弧变换：、弧变换：对预处理后的状态图重复进行以
31、下变换，直至图中除了对预处理后的状态图重复进行以下变换，直至图中除了 X 和和 Y 以外，不再含有其它状态；以外，不再含有其它状态； 最后，最后，X 和和 Y之间最多只有一条弧之间最多只有一条弧。 正则表达式与有限自动机等价正则表达式与有限自动机等价 DFA/RE图解法图解法3、结束算法：、结束算法：当当 X，Y 之间唯一存在一条弧时，弧上的标记则为所求的之间唯一存在一条弧时，弧上的标记则为所求的正则表达式；当弧不存在时，则表达式为正则表达式；当弧不存在时，则表达式为 。变换变换 2 - 去去 “连接连接” 弧弧 ： 变换变换 3 - 去去“连接连接”弧和弧和“ * ” 弧弧 ： 变换变换 4
32、 - 去最终剩余的独立状态：去最终剩余的独立状态：如果图中只剩下三个状态如果图中只剩下三个状态 X、Y、Z，并且，并且， X 与与 Y 之间不存在任何路之间不存在任何路径，则可删去除径，则可删去除 X，Y以外的第三个状态以外的第三个状态 Z 以及与其相关弧。以及与其相关弧。正则表达式与有限自动机等价正则表达式与有限自动机等价例例8：设：设 M = 如下，求与其相应正则表达式。如下，求与其相应正则表达式。正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与有限自动机等价步骤步骤 1：用新添状态用新添状态 X、Y及相关及相关-连接弧，将连接弧，将 DFA 括起
33、来。括起来。步骤步骤 2：删除所有不删除所有不可达状态。可达状态。本状态图中无不可达状态，本步骤不执行。本状态图中无不可达状态，本步骤不执行。正则表达式与有限自动机等价正则表达式与有限自动机等价步骤步骤 3：去除状态去除状态 q3 ：“连接连接” 弧与弧与 “*” 弧。弧。步骤步骤 4：去除状态去除状态 q4 ：“连接连接”弧弧正则表达式与有限自动机等价正则表达式与有限自动机等价步骤步骤 5：去除去除 q2 到到 Y 的的 “并行并行” 弧。弧。步骤步骤 6：去除状态去除状态 q0 ：“*”弧和弧和 “连接连接” 弧。弧。正则表达式与有限自动机等价正则表达式与有限自动机等价步骤步骤 7：去除去
34、除 q1 到到 q2 之间之间的的 “并行并行” 弧。弧。步骤步骤 8：去除状态去除状态 q1 ：“连连接接” 弧与弧与 “*” 弧弧。正则表达式与有限自动机等价正则表达式与有限自动机等价步骤步骤 9：去除状态去除状态 q2： “连连接接” 弧与弧与 “*” 弧。弧。与与 M 等价的正则等价的正则表达式：表达式：几点说明：几点说明： 1、“去状态去状态”顺序不同时，得到的正则表达式形式可能不一样，但它们等顺序不同时，得到的正则表达式形式可能不一样，但它们等价价2、“去状态去状态” 和和 “去并行弧去并行弧” 操作没有绝对的先后顺序规定；但一般来操作没有绝对的先后顺序规定；但一般来说，应优先执行
35、说，应优先执行“去并行弧去并行弧”操作，可使得后续状态图处理比较简单。操作，可使得后续状态图处理比较简单。3、当、当 DFA 是终止状态不可达时，状态图将不存在从始态到终态的路径，是终止状态不可达时，状态图将不存在从始态到终态的路径，按照算法操作，最终，会去掉标记为按照算法操作，最终，会去掉标记为 X 和和 Y 状态以外所有的状态和弧，此状态以外所有的状态和弧，此时，相应的正则表达式为时，相应的正则表达式为 。 4、上述算法不会去掉、上述算法不会去掉 X、Y 状态；故判定算法可结束；可软件实现算法。状态；故判定算法可结束；可软件实现算法。正则表达式与有限自动机等价正则表达式与有限自动机等价习题
36、：习题：p.153, 1. 写写出下列语言的表达式出下列语言的表达式正则表达式的定义及性质正则表达式的定义及性质第四章第四章 正则表达式正则表达式正则表达式的引入正则表达式的引入正则表达式的定义及性质正则表达式的定义及性质正则表达式与有限自动机等价正则表达式与有限自动机等价正则表达式与正则文法等价正则表达式与正则文法等价正则语言等价描述模型总结正则语言等价描述模型总结1、将正则文法、将正则文法 RG 的产生式：的产生式： A1 x1A1 | x2A2 | . | xk Ak， 其中，其中，Ai V, xi T*改写为正则表达式方程式：改写为正则表达式方程式： A1 = x1A1 + x2A2
37、+ . + xkAk 2、将、将 RG 中所有产生式联立为正则表达式方程组。例如，中所有产生式联立为正则表达式方程组。例如， RG ：S 1S | 0A | RE：S = 1S + 0A + A 0S | 1A A = 0S + 1A 3、求解方程组，亦即，求解各语法变元、求解方程组，亦即，求解各语法变元语法范畴语法范畴覆盖字符串集合对应的正覆盖字符串集合对应的正则表达式；其中，初始符则表达式；其中，初始符 S 的解即是代表文法的解即是代表文法 G 派生语言的正则表达式。派生语言的正则表达式。正则表达式与正则文法正则表达式与正则文法等价等价RG 与与 RE 等价的方程组等价的方程组求解算求解算
38、法法: 定理：定理：设有设有正则表达方程式正则表达方程式 x = x + ，其中，其中， , 为已知正则表达为已知正则表达式式，x 是未知正则表达式是未知正则表达式，那么，那么 x = * 是方程式是方程式的一个解。的一个解。正则表达式与正则文法正则表达式与正则文法等价等价证证 * 是是 x = x + 的一个解。的一个解。将将 x = * 代入方程式两边有：代入方程式两边有： * =思路：暂将变元思路：暂将变元 xi 视为已知量，其它变量视为已知量，其它变量 xj ( j i ) 视为未知量，视为未知量，利用定理结论求解未知量所在的方程式。利用定理结论求解未知量所在的方程式。例如，求解已知量
39、例如，求解已知量 x2 式：式： x2 = 0 x1+1x2 = 1* 0 x1。2、将方程式、将方程式 x2 的解代入未知量的解代入未知量 x1 方程式，并利用定理结论求解。方程式，并利用定理结论求解。 x1 式：式：x1 = 1x1 + 01*0 x1 + = (1 + 01*0) x1 + = (1 + 01*0)* = (1 + 01*0)* 结果：结果： x1 = (1 + 01*0)* x2 = 1*0 (1 + 01*0)* 求解正则表达式方程组：求解正则表达式方程组：设方程组：设方程组： x1 = 1x1 + 0 x2 + x2 = 0 x1 + 1x2 正则表达式与正则文法正
40、则表达式与正则文法等价等价例：给定例：给定 DFA 如图所示，求与之等价的正则表达式如图所示，求与之等价的正则表达式。解：解：1、根据定理、根据定理 3-3，写出等价的右线性文法：，写出等价的右线性文法： q00q1 | 1q0 q10q0 | 1q2 | 1 q20q1 | 1q02、求得相应的正则表达式方程组：、求得相应的正则表达式方程组： q0 = 0q1 + 1q0q1 = 0q0 + 1q2 + 1q2 = 0q1 + 1q0正则表达式与有限自动机等价正则表达式与有限自动机等价2、解方程组，求代表初始状态、解方程组，求代表初始状态 q0 字符串存储功能的正则表达式的解字符串存储功能的
41、正则表达式的解3、解方程组：、解方程组： 由于由于 q2 = q0，将其代入，将其代入 q1 式：式： q1 = 0q0 + 1q2 + 1 = ( 0 + 1 )q0 + 1 将将 q1 值代入值代入 q0 式：式：q0 = 0 ( ( 0 + 1 )q0 + 1) + 1q0 = 0 ( 0 + 1 )q0 + 01 + 1q0 = ( 00 + 01 + 1 )q0 + 01由定理结论解得正则表达式由定理结论解得正则表达式: q0 = ( 00 + 01 + 1 )* 01故故 DFA M 对应正则表达式：对应正则表达式： L（M）= ( 00 + 01 + 1 )* 01正则表达式与有
42、限自动机等价正则表达式与有限自动机等价q0 = 0q1 + 1q0q1 = 0q0 + 1q2 + 1q2 = 0q1 + 1q0作业：作业：1、求解下列正则表达式方程组，、求解下列正则表达式方程组， 即，求即，求 x, y, z 对应的正则表达式。对应的正则表达式。2、给出接受下列语言的右线性文法：、给出接受下列语言的右线性文法：正则表达式与正则文法正则表达式与正则文法等价等价x = ax + byy = by + zz = x + az1）a*2) ( a + b ) ( a + b + 0 + 1 )正则表达式的引入正则表达式的引入正则表达式的定义及性质正则表达式的定义及性质正则表达式与
43、有限自动机等价正则表达式与有限自动机等价正则表达式与正则文法等价正则表达式与正则文法等价正则语言等价描述模型总结正则语言等价描述模型总结第四章第四章 正则表达式正则表达式正则语言的正则语言的 5 种等价描述模型：种等价描述模型：正则语言等价描述模型总结正则语言等价描述模型总结正则文法正则文法 （ RG ）；）； 确定的有穷状态自动机（确定的有穷状态自动机（ DFA ）；）；不确定的有穷状态自动机（不确定的有穷状态自动机（ NFA ）；）；带空移动的有穷状态自动机（带空移动的有穷状态自动机（- NFA ）；）；正则表达式（正则表达式（ RE ）。）。五种等价描述模型及其相互模拟（定义）关系：五种
44、等价描述模型及其相互模拟（定义）关系：正则语言等价描述模型总结正则语言等价描述模型总结正则语言等价模型总结正则语言等价模型总结1、DFA RG （用自动机定义正则文法）：（用自动机定义正则文法）： 给定给定 M = （Q, , , q0, F ），构造文法），构造文法 G = ( Q, , P, q0 )； 1）运用）运用 M 的状态转移模拟的状态转移模拟 G 推导过程推导过程 。 P = q a p |( q, a ) = p q a |( q, a ) = p F ； 2）M 始态始态 q0 对应对应 G 起始符起始符 S；( q, a ) = p F 定义定义 G 推导结束推导结束正则语
45、言等价模型总结正则语言等价模型总结2、 RG NFA（正则文法定义自动机）：正则文法定义自动机）： 给定给定文法文法 G = ( V, T, P, S )，构造，构造 M = ( V Z , T, , S, Z ) 1）由）由 G 的推导过程定义的推导过程定义 M 的状态转移。的状态转移。 B | A a B P Z 如果如果 A a P ( A, a ) = B | A a B P 如果如果 A a P 2）G 的起始符的起始符 S 对应对应 M 的起始状态的起始状态 q0； 3）新增加状态）新增加状态 Z = F 为为 M 的终止状态。的终止状态。正则语言等价模型总结正则语言等价模型总结1
46、）新增加）新增加 Z 为为 FA M 开始状态；开始状态； 2）产生式）产生式 A a，M 有有 A =(Z, a) ；3）产生式）产生式 A Ba，M 有有 A =( B, a )； 4）规定）规定 G 的开始符的开始符 S 为为 M 的终止状态。的终止状态。 2、 RG NFA（左线性文法定义左线性文法定义 自动机）：自动机）： 给定文法给定文法 G = ( V, T, P, S )，构造，构造 M = ( V Z , T, , Z, S ) 用用 G 的推导过程定义的推导过程定义 M 的状态转移。的状态转移。正则语言等价模型总结正则语言等价模型总结3、 DFA RE (自动机定义表达式）
47、自动机定义表达式） 1）图解法）图解法 - 预处理：预处理： 去掉去掉 DFA M 中所有不可达状态；中所有不可达状态；在在 M 的始态的始态 q0 和终态和终态 f1 两端分别添加由两端分别添加由标记状态标记状态 X, Y。 2）去）去“并行并行”弧规则：弧规则：用用 r1 + r2 + + rn 标记状态标记状态 q 到到 p 之间之间 r1, r2, , rn 个并行弧；个并行弧； 正则语言等价模型总结正则语言等价模型总结4）求解结果：）求解结果：当当 X，Y 之间存在唯一一条弧时，弧上的标记则为所求的正则表达式；之间存在唯一一条弧时，弧上的标记则为所求的正则表达式；如果图中只剩下三个状
48、态如果图中只剩下三个状态 X、Y、Z，且，且 X 与与 Y 间不存在路径时，删去除间不存在路径时，删去除 X，Y 以外的第以外的第三个状态三个状态 Z 及相关弧，所求表达式为及相关弧，所求表达式为。3、 DFA RE （图解法）图解法） 3）去）去“连接连接”、“*” 状态规则状态规则 ：- 用标记为用标记为 r1r2 的弧代替状态的弧代替状态 q 到到 p、p 到到 t 之间标记分别为之间标记分别为 r1, r2 连接弧连接弧- 用标记为用标记为 r1r3*r2 的弧代替状态的弧代替状态 q 到到 p、p 到到 t 间标记分别为间标记分别为r1, r2 ，并且，并且 p 到到 p 有标记为有
49、标记为 r3 的连接弧；的连接弧；正则语言等价模型总结正则语言等价模型总结4、 RE - NFA （正则表达式定义自动机）（正则表达式定义自动机） 按照按照 RE 的递归定义以及定理的递归定义以及定理 4 - 1 构造性证明过程求解构造性证明过程求解- NFA ： （1） r =： r = ： r = a： （2）由）由 r = r1 + r2 逐步构造等价的逐步构造等价的-NFA。 由由 r = r1 r2 逐步构造等价的逐步构造等价的-NFA。 由由 r = r1* 逐步构造等价的逐步构造等价的-NFA。正则语言等价模型总结正则语言等价模型总结1、( q0, ) = q01, q02 2、
50、( q, a ) = 1 ( q, a ) 3、( q, a ) = 2 ( q, a ) 4、( f1, ) = qf ；5、 ( f2, ) = qf 1、( q, a ) = 1 ( q, a ) 2、( q, a ) = 2 ( q, a ) 3、( f1, ) = q02 4、q0 = q01, qf = f2正则语言等价模型总结正则语言等价模型总结1） ( q0, ) = q01, qf 2） ( q, a ) = 1 ( q, a ) 3） ( f1, ) = q01，qf 正则语言等价模型总结正则语言等价模型总结正则语言等价模型总结正则语言等价模型总结5、 - NFA NFA
