编译原理第九讲讲义.ppt

证 ? 对正规表达式r的运算数目作归纳。设r具有零个运算，则或r=?或r= ?或r=a? ? * Compiler Construction Principles * Formal Languages and Automata 正规表达式与有穷自动机的等价性 定理 设r是?上一个正规表达式，则存在一个NFA m接受L( r )。 对于?上任一NFA m，能构造?上一个正规表达式r，使得L( r )=L(m)。 把转换图的概念拓广，每条弧上可以用一个正规式标记。首先，在m的转换图上加进x,y两个结。从x用?弧连接到m的所有初态结点，从m的所有接受态结点用?弧连接到y，从而构成一个新的NFA m’，L(m)=L(m’)。 下面，逐步消去NFA m’中的状态结点，直至剩下x,y为止。在消结的过程中，逐步用正规式标记弧。消结的过程是直观的，只需反复使用下面的替换规则。 a b c a c a c a c a b c a c r1 r2 r2 r2 r1 r1 r3 r1r2 r1?r2 r1r2*r3 替换规则 代之以 代之以 代之以 q0 q0 q1 q0 q1 a r=? r= ? r=a 设结论对少于i(i?1)个运算的正规表达式r成立。当r有i个运算时，有三种情况： 情况1 r=r1?r2 情况2 r=r1r2 情况3 r=r1* 有 m1=(?1,Q1,q1,F!,?1), m2=(?2,Q2,q2,F2,?2) 且L(m1)=L( r 1), L(m2)=L(r2) ，由m1和m2构造m,使得 L(m)=L( r ).构造方法图示如下： q0 q1 f1 f2 q2 f0 m2 m1 ? ? ? ? r=r1?r2 q0 q1 f1 q2 f0 m2 m1 ? ? ? ? f2 ? q1 f1 r=r1r2 r=r1* 上述证明方法，是对于一个正规表达式r,构造一个FA m,且L(m)=L( r )的算法,但假定知道r的计算顺序。 正规表达式r的语法是上下文无关文法。 例构造与下列正规式 为r=(01*)?1 和R=(a|b) * abb构造NFA N，使得L(N)=L(R)。 q0 q1 0 q2 q3 1 q2 q3 q5 q4 1 ? ? ? ? 0 1 q0 q1 q6 q7 1 q2 q5 q4 ? ? ? ? ? q0 q1 q4 q2 q3 q3 q6 q7 1 1 0 ? ? ? ? ? q8 q5 q9 ? ? ? ? 正规文法与有限自动机(FA)的等价性L(G)=L(m) 定理 对于每一个右线性正规文法或左线性正规文法G，都存在一个NFA m，使 L(m)=L(G) 证 给定右线性正规文法G=(VT,VN,S,P),设 Z? VN ，令m=(VT ,Q, S, F, ?), 其中，F= ?Z? Q= VN??Z?, 转移函数 ? 定义如下： (a) A?a, ?(A,a)=f (b) A ?aA1?aA2 ?... ?aAn ?(A,a)= ?A1,A2 ,... ,,An ? 构造与文法G[S]等价的NFA M　　G[S]： S→aA　　S→bB　　S→ε　　A→aB　　　 　　A→bA 　 B→aS　　B→bA　　B→ε