第四章 正则表达式及描述模型总结5.pdfVIP

第四章 正则表达式 习题： 题1、题2、题3 -（3，4）、 题5、题6 第四章 正则表达式以及 正则语言描述模型总结 软件开发环境国家重点实验室 第四章 正则表达式 正则表达式的引入 正则表达式的定义及性质 正则表达式与有限自动机等价 正则表达式与正则文法等价 正则语言等价描述模型总结 正则表达式的引入 例：设正则语言： n m k i n m { a b c | n, m, k≥1 } ∪{ a c bxa | i≥0, n ≥1, m ≥2, x 是由 d 和 e 组成的字符串 } 有穷自动机描述模型： 正则表达式的引入 FA 每个状态针对各输入字符所具有的存储功能： 由于, 所以, 正则表达式的引入 正则语言： 正则表达式： r = a+ b+ c+ + a*c+ ( d + e )*a+ a = a a*bb*cc* + a*cc*( d + e )*aaa* 第四章 正则表达式 正则表达式的引入 正则表达式的定义及性质 正则表达式与有限自动机等价 正则表达式与正则文法等价 正则语言等价描述模型总结 正则表达式的定义及性质 定义4-1 ：设字母表为∑，正则表达式递归定义如下： 正则表达式的定义及性质 例：设∑ = { 0，1 }，∑中部分正则表达式及其语言对应如下： 正则表达式的定义及性质 定义4 - 2 ： 设 r 是字母表∑上的正则表达式，r 的 n 次幂定义为： 满足性质： n n L （r ）= （L （r ）） , rn r m = r n + m, n, m ≥0 正则表达式的定义及性质 表达式简化约定： - 减少括号 1、r 的正闭包： 2、运算符的优先级： 闭包运算＞乘运算＞加运算 正则表达式的定义及性质 表达式的简化约定： 3、意义明确时，正则表达式 r 表示的语言记为 L （r ）， 也可直接记为 r 。 4、无扩号说明时，加、乘、闭包运算均执行左结合规则。 例： R1 ∪R2 ∪R3 = （R1 ∪R2 ）∪R3 R1 R2 R3 = （R1 R2 ）R3 正则表达式的定义及性质 定义4 - 3 ： 设 r, s 分别为字母表∑上的正则表达式，如果 L ( r ) = L ( s ), 则称表达式 r 与 s 相等（或等价），记作 r = s 。 例：令 r , r 分别为语言 R = ( 0 ∪1 )*，R = ( 0*1* )* 的正则表达 1 2 1 2 式，有 r = r 。 1 2 正则表达式的定义及性质 可以证明，字母表∑上正则表达式 r, t, s 及相关语言满足以下等式： 正则表达式的定义及性质 * * * * * * 例1- 证16式：L ( (r ) ) = L (r) ，其对应语言集合 ( R ) = R 。 证：施归纳于集合 R 乘积的个数，求证（ R* )n = R* ( n ≥0 ) 。 0 1 基础语句：设 n = 0，1， （R* ) = { ε}， （R* ) = R* ，结论成立。 归纳语句：设 n ＞1, （R* )n = R* 结论成立，证 ( R* )n+1 = R* 时结论成立