计算理论02_正则语言技术总结.pptVIP

计算理论 wbfeng@staff.edu.shu.cn 计算理论 wbfeng@staff.edu.shu.cn * * 第二讲课程 Chapter 1: RL = Regular Languages, nonregular languages RL pumping lemma Chapter 2: Context-Free Languages (CFLs) * * Regular Expressions (Def. 1.26 中文：定义1.26 ) ep64 cp39 递归法下定义，适合本身是递归结构的对象 例 N! 或记为 F(N) 定义为 F(0)=1; 递归基础 （程序终止条件） F(N)=N*F(N-1) 当 N = 1 //递归 (减1）结构 Int Factor(int n) { if (n0) printf(“error”); if n==0 return 1; //无此语句，会导致error else return n*Factor(n-1); //通常用栈结构实现 } 如第1,2句均无，则死循环，称为 图灵机不停机， * * Regular Expressions 正则表达式 (Def. 1.26 中文：定义1.26 ) ep64 cp38 递归法下定义，适合本身是递归结构的对象，构造性的 Given an alphabet ?, R is a regular expression if R = a, with a?? R = ? 递归基础 R = ? R = (R1?R2), with R1 and R2 regular expressions R = (R1?R2), with R1 and R2 regular expressions R = (R1*), with R1 a regular expression 递归结构，增加 一个运算符号 的 构造方法 * * Thm 1.28: RL ~ RE ep66 cp40（读一下） Thm 1.28 L is RL ? ? there exists RE E such that L=E 通常 L={ ..|….} E形如 (a+b)C+(d.g)* (无穷) 集合表达式 有限字母 有限运算 构造，可计算 We need to prove both ways: 左边? ?右边 If a language is described by a regular expression,then it is regular (Lemma 1.29)上次实际上已证 左边? 右边 (Last week we saw how we can convert a regularexpression R into an NFA M such that L(R)=L(M))上次已完成FA的确定化 Today we do the second part: 左边 ?右边, 给机造表达式 If a language is regular, then it can be described bya regular expression (Lemma 1.32) * * Thm 1.28: RL ~ RE 给机造表达式ep66 cp40（读一下） Today we do the second part: 左边 ?右边， 即： If a language is regular, then it can be described bya regular expression (Lemma 1.32) 分两部 1 RL 有 DFA M识别（定义），把DFA 转化称广义的GNFA 2 把广义的GNFA转化成正则表达式 RE 下页先引入广义的GNFA 普通的NFA中一个边相当于一个语句 广义的GNFA 自动机的边可以是正则表达式（自动机），相当相当于 程序可以调用（子）程序 * * Generalized NFA 给机造表达式 ep70-73 , cp41-42 Generalized nondeterministic finite automaton M=(Q, ?, ?, qstart, qaccept) with Q finite set of states ? the input alphabet qstart the start state qaccept