形式语言与自动机 6 正则表达式.pptVIP

* / * 思考题：如何形式化的描述GNFA? 如何形式化证明上述定理？ * / * (3) 删除一个节点 (4) 再删除一个节点 * / * 例题7：运用上述证明中的方法将图中的DFA转换为正则表达式。 (1) DFA (2) GNFA * / * 习题：将下图中三个状态的DFA，转化为正则表达式。要求严格按照上述步骤进行。 * / * Question Answer / UJS Jiangsu University / * / * 形式语言与自动机 授课 人： 王 良 民MAIL:wanglm@ * / * 第六章 正则表达式 6.1 引例 6.2 正则表达式的形式定义 6.2.1形式定义 6.2.2 例题 6.3 正则表达式与有穷自动机的等价性 6.3.1充分性证明 6.3.2必要性的证明 (1)首先说明如何把DFA转换成GNFA (2)说明如何把GNFA转换成正则表达式 * / * 例题1：：算术表达式：(5+4)×2, 值为18，是一个数字正则表达式：(0∪1)0*, 正则表达式的值是一个语言 注意： (0∪1)0* 表示的是01后加任意多个0构成的字符串所组成的语言 0和1是集合{0}和{1}的缩写，就是{0}∪{1}, 这部分的值是语言{0, 1} 0*就是{0}*,其值为所有包含任意个0的字符串构成的语言 在正则表达式中省略了连结运算符号o, (0∪1)0*实际上是(0∪1) o0* 正则表达式可以用来描述满足“某种模式”的字符串。 * / * 很多应用程序及现代程序设计语言、文本编辑程序都提供用正则表达式描述模式的手段。 例题2：正则表达式(0∪1)* 其值为：由0和1的所有字符串组成的语言，也表示为{0, 1}* 表示方法：记∑为字母表，∑也可以表示该字母表中所有长度为1的字符串，而∑*为由该字母表中所有字符串组成的语言。 如：(0∑*)∪(∑*1)表示所有以0开头而以1结尾的字符串 正则运算的优先级：先星号，后连结，最后并，要改变这种惯常的顺序需要用括号。 * / * 第六章 正则表达式 6.1 引例 6.2 正则表达式的形式定义 6.2.1形式定义 6.2.2 例题 6.3 正则表达式与有穷自动机的等价性 6.3.1充分性证明 6.3.2必要性的证明 (1)首先说明如何把DFA转换成GNFA (2)说明如何把GNFA转换成正则表达式 * / * 定义 称R是一个正则表达式，如果R是 a, 这里a是字母表∑中的一个元素； ε； φ； (R1∪R2)，这里R1和R2是正则表达式； (R1oR2)，这里R1和R2是正则表达式； (R1*)，这里R1是正则表达式； * / * 说明： 在(1)和(2)中，a和ε分别表示{ a }和{ε} 在(3)条中，φ表示空语言 在第(4)、(5)、(6)表示通过正则运算并、连结和星号获得正则表达式 （用较小的正则表达式定义较大的正则表达式，是归纳定义中的归纳步骤） 此处ε和φ的区别：有一个空语句的语言，和空语言 要想明显的区分正则表达式R和它所表示的语言时，后者用L(R)表示。 * / * 第六章 正则表达式 6.1 引例 6.2 正则表达式的形式定义 6.2.1形式定义 6.2.2 例题 6.3 正则表达式与有穷自动机的等价性 6.3.1充分性证明 6.3.2必要性的证明 (1)首先说明如何把DFA转换成GNFA (2)说明如何把GNFA转换成正则表达式 * / * 例题3：在下面的句子中，字母表为{0,1} 0*10* {ω|ω恰好有一个1} ∑*1∑* {ω|ω至少有一个1} ∑*001∑* {ω|ω中含有子串001} (∑∑)* {ω|ω是偶长度的字符串} (∑∑∑)* {ω|ω是长度为3的字符串} 01∪10 {01, 10} 0∑*0∪1∑*1∪0∪1 {ω|ω以相同的字符开始和结束} (0∪ε)1* 01*∪1* 说明：(0∪ε)表示语言{0,ε} (0∪ε) (1∪ε) {ε, 0, 1, 01} 1*φ φ φ* {ε} 说明：*运算只能把0个字符串连接在一起，得到的唯一的一个字符串是ε * / * 例题4：设R是任意的正则表达式，有下述恒等式成立。 几个正则表达式的恒等式 这些恒等式有助于对正则表达式定义的理解 R∪φ = R 空语言加上任何一个语言不改变这个语言 Roε = R 空串加上任何一个字符串上不改变这个字符串 但是：R∪ε不一定等于R，Roφ不一定等于R * / * 例题5：程序设计语言中的基本单位称为单字，如变量名和常量，这些东西可以用正则表达式描述。 通常是包括小数部分和正负号的的数值常量可以描述成下述语言的一个成员： {+, --, ε}(DD*∪DD*. D*∪D*.DD*) 其中，D ＝ {