第四章---正则表达式.ppt

1、在第四章正则表达式中，正则语法擅长语言的生成，贫穷状态自动机擅长语言的识别。 本章介绍正则语言的正则表达式的说明。 它在正则语言的表达上具有特殊优点，为正则语言的校正计算机处理提供了方便的条件。 简洁，更接近语言的集合表现和语言的计算机表现等。 第四章正则表达式，主要内容是典型的RE结构。 与RE等价的FA的构造方法。 与DFA等价的RE的构造。 重点RE的概念。 RE和DFA的等价性难点： RE和DFA的等价性证明。 前面，我们使用正则表达式(例如，语言(红色部分):l (g )=0n|n1l (g )=0n1m2k|n、m和k1)进行了表达。 更接近集合表现和修正算机表现。 4.1显示，生

2、产语言anbmck|n、m、k1 aicnbxam|i0、n1、m2、x是由d和e组成的列的正则语法是aaa|ab|cebbb|bcccc|cece。 一个集合，一个集合，一个集合，一个集合，一个集合，一个集合，一个集合，一个集合可以这样写L(M )，写L(M)=a b c a*c b (de)*a a，写abca*c(de)*a=aa*bb*cc*a*cc是上面的RE，代表语言a，而a是上面的RE，代表语言a。 如果r和s分别是以上表示的词r和s的RE，则r和s的“和”(r s )是以上的RE，(r s )表示的词是r s。 r和s的“乘积”(rs )是上面的RE，而表示(rs )的语言是r

3、s。 r的克林闭包(r* )是以上的RE，(r* )表现的语言是r*。 只有上面的RE才能满足、4.2 RE的形式定义，例4-1=0、10，表示语言0。 1、表达语言1； 表示(0-1)，语言0，1。 (01 )、显示语言01； (0 1)* )，表示语言0、1*； (00)(00)* ) )，语言0000*； 4.2 RE的形式定义(0 1)*)(0 1)(0 1)* ) )，表示语言0，1。 (0 1)*)000)(0 1)* ) )表示由至少包括三个0，1以上的连续0的字符串组成的语言。 (0 1)*)0)1)表示由以01结尾的0、1个字符串组成的语言。 (1(0 1)*)0) )表示以

4、1开始，以0结束的由0、1个字符串组成的语言。4.2 RE的形式定义、约束r的正闭包r是r和(r* )的乘积以及(r* )和r的乘积： r=(r(r*)=(r*)r )闭包运算的优先级最高，因此，在意义明确的情况下，可以省略其中的几个括号。 (01)* ) 000 ) (01 ) * ) )=(01 ) * 000 (01 ) *、4.2 RE的形式定义(01 ) * )相加、乘法、闭包运算都执行左结合规则。 4.2 RE的形式定义是相等的r，s是字母上的RE，如果L(r)=L(s )，那么就将其称为r和s相等，表示为r=s。 相等也称为等价。 基本结论结合律： (rs)t=r(st) (r

5、s) t=r (s t )分配律： r(s t)=rs rt (s t)r=sr tr，4.2幂等律： r r=r 加零要素： r=r。 乘法单位元： r=r=r。 乘以零要素： r=r=。 L()=。 L()=。 L(a)=a。 4.2 RE的形式定义，L(rs)=L(r)L(s )。 L(r s)=L(r)L(s )。 L(r*)=(L(r)*。 L(*)=。 L(r )*)=L(r* )。 L(r*)*)=L(r* )。 l (r * s * ) * )=l (r * s ) *。 如果l (r )到l (s )，则r s=s。 4.2 RE的形式定义，L(rn)=(L(r)n。 rnr

6、m=rn m。 一般来说，r r、(rs)n rnsn、rssr。 应该r是字母表上的RE，r的n次方被定义为r0=。 rn=rn-1r。4.2 RE的形式定义，例4-2=0，100表示语言00。 (0 1)*00(0 1)*表示由0、1列组成的所有语言，其中至少包含两个连续的0。 (0 1)*1(0 1)9表示由所有倒数第10个字符为1的字符串构成的语言，是4.2 RE的形式定义，L(0 1)*011)=x|x是以011结束的0，1列。 L(0 1 2 )=0n1m2k|m、n、k1。 L(0*1*2*)=0n1m2k|m、n、k0。 L(1(0 1)*1 0(0 1)*0)=x|x的开头字

7、符与末尾字符相同。 4.3 RE与FA等价，正则表达式r与FA M等价，如果L(r)=L(M )。 基于由状态之间的转变所确定的后续关系，从开始状态起依次计算对应于给定的FA的每一个状态q的set(q )，并且最终获得相应的FA所接收的语言的RE表示。 寻找比较“机器”的方法，使计算机系统能够自动完成FA和RE之间的转换。 从4.3.1 RE到FA的等效变换、对应于0的FA、对应于01的FA、对应于4.3.1 RE到FA的等效变换、对应于01的FA、对应于4.3.1 RE到FA的等效变换、对应于0*的FA、证明：正则表达式中包含的运算符的个数n m正好是结束状态。 m在结束状态下什么也不移动。

8、 假设在结论为n=k的情况下，从4.3.1 RE到FA的等效变换、n=0，r=、r=、r=a，4.3.1 RE到FA的等效变换成立，那么存在以下fa:m1的Q1Q2=。 取从n=k、4.3.1 RE到FA的等效变换，取n=k 1、r=r1 r2、q0、fQ1Q2，M=(Q1Q2q0、f、q0、) q 1、a、(q、a)=1(q、a )； qQ2、a、q、a=2、q、a； (f1，)=f； (f2，)=f 从4.3.1 RE到FA的等效变换，从n=k 1，r=r1r 2，4.3.1 re到FA的等效变换，M=(Q1Q2，q01，f2)对qq1 qQ2-f2，a (q，a)=2(q，a )； (f

9、1，)=q02，从4.3.1re到FA的等效变换，从r=r1r 2，4.3.1 re到FA的等效变换，M=(Q1q0，f，q0，) (f1，)=q01，f (q0，)=q01，f。 当以如下方式构建所给定RE的等效值FA时：4.3.1 RE到FA的等效变换，r=r1*，4.3.1 RE到FA的等效变换，以及在定理4-1证明中给出的方法，FA可能包括许多空运动。 可以根据自己对给定RE的“理解”和对FA的“理解”“直接”制作相对“简单”的FA。 定理证明给出的方法是机械的。 由于“直接”构筑的FA的正确性取决于构造者的“理解”，因此其正确性缺乏有力的保证。 从4.3.1 RE到FA的等效转换，例

10、4-3结构是与(0 1)*0 (00)*等效的FA。 从4.3.1 RE到FA的等效转换是根据对(0 1)*0 (00)*的“理解”“直接”构建的FA。 4.3.2 RL可以用RE表示，对每个DFA状态修正对应的集合字母的克林闭包的等价分类具有启发性意义。 这个订正计算过程“机械的”很难进行。 校正从q1到q2的一系列集合： Rkij。 图上作业法。 4.3.2 RL可以用RE表示，定理4-2 RL可以用RE表示。 设DFA M=(q1，q2，qn，q1，F) Rkij=x|(qi，x)=qj且对于x的任意前缀y(yx，y )，4.3.2 RL可以用RE表示，R0ij=，a|(qi，a)=qj

11、效果ij，a|(qi，a )=表示图上作业法操作步骤前处理：在标记为x和y的状态下包围m :在状态转移图上追加标记为x和y的状态，从标记为x的状态到标记为q0的状态，从标记为q(qF )的状态到标记为y的状态，分别进行标记清除所有无法到达的状态。 4.3.2 RL可由RE表示并且对于步骤(1)中获得的状态转换图重复下面的操作直到图中不包括除x和y之外的状态，并且在这两个状态之间最多只有一个弧形。 并弧将从q到p的标记变换为r1、r2、将rg的并弧将从q到p的r1 r2 rg的标记变换为r1 r2 rg的弧。4.3.2 RL可以由RE表示，其中，解锁状态1从q到p具有标记为r1的弧，从p到t具有

12、标记为r2的弧，没有从状态p到状态p的弧，以及去除状态p和与其相关联的两个弧，并用标记为r1r2的弧代替q到t的弧如果脱离状态2-q到p具有标签为r1的弧，那么从p到t具有标签为r2的弧。如果从状态p到状态p具有标签为r3的弧，那么将状态p和与其相关联的三个弧去除，用从q到t的标签为r1r3*r2的弧替换。 4.3.2 RL可以由RE表示，如果在拆卸状态3图中只有三个状态，没有从标记为x的状态至标记为y的状态的路径，那么除了标记为x的状态以外的第三种状态及其相关联的弧都被删除。从标记为x的状态到标记为y的状态的弧的标记是求出的正则表达式。 如果此弧不存在，则计算的正则表达式为。 可以用RE表示

13、4.3.2 RL，例如4-4求出与图4-14所示的DFA等价的RE。 另外，4.3.2 RL可以用RE表示，预处理：4.3.2 RL可以用RE表示，删除状态q3:4.3.2 RL可以用RE表示，删除状态q4:4.3.2 RL和4.3.2 RL可以用RE表示，删除状态q0:11*0； 4.3.2 RL可以由RE表示，删除状态q1:4，4.3.2 rl可以由RE表示，虽然如果一些要关注的问题去往不同状态的顺序，则所得到的RE可以具有不同的形式，但是它们是等效的。 在DFA的终止状态全部不能到达的情况下，在状态转移图中不存在从开始状态到终止状态的道路。 此时，对应的RE为。 如果没有校正自身到自身的弧，并且状态q的入度是n，出度是m，则必须在去除状态q和与其相关联的弧后添加n*m个新弧。 (4)总结操作的步骤数，可以证明其正确性。 4.3.2 RL可以用RE表示，推论4-1正则表达式等效于FA、正则语法，是正则语言的表达模型。4.4正则语言等价模型的总结、4.4正则语言等价模型的总结、4.5总结，本章对RL与FA的等价性进行讨论。 字母表上的RE用来表示上面的RL。a(a )为上述最基本的RE，分别