西北工业大学编译原理课件第三章 词法分析及词法分析程序3.pptVIP

3.3 有限自动机 状态转换图实际上是有限自动机的图形表示 3.3.1 确定的有限自动机DFA 1.抽象地看,状态转换图由五个部分组成: (1)有限个状态之集,记作K; (2)有限个输入符号组成的字母表,记作?; (3)从K??到K的转换函数 f: K???K. f(p,a)=q表示若当前状态为p,且输入符号为a,则进入下一个状态为q; (4)S0?K,初始(开始)状态; (5)若干个终态之集: Z( ?K ) 由上述五个要素组成的五元式 M=(K, ?, f,S0,Z )称为一个确定的有限自动机 (DFA: Deterministic Finite Automata) 由此可见,一DFA实际上是状态转换图的形式描述(数学定义),状态转换图是DFA的几何(图形)表示. DFA的接受集 2.为定义DFA所接受(或识别)的符号串集合,我们先将其转换函数f 的定义域拓广到K??* : (1)f^ (s,?)=s, s?K; (2)f^ (s,aw)=f^ ( f(s,a),w), s?K,a??,w??*; 由上面的定义可知,对于x??* ,f^(s,x)=t 的含义是,当M从状态s出发,依次扫描完x的各个符号后将进入状态t.即只要f有定义,f^与f的效果是一致的. 我们称DFA M接受(或识别)某符号串x??*,用状态转换图来说,就是从初态S0出发,经一恰好标有x 的路径后可达到某终态S?Z ;用f^描述就是: ?S?Z, f(S0,x)=S M的接受集 我们把一DFA M所接受的符号串的全体称为M的接受集,记为L(M),即 L(M)={ x | f(S0,x) ?Z,x??* } 确定的有限自动机 我们之所以把前面定义的有限自动机称为确定的FA，是因为在状态转换的每一步，根据FA当前的状态及扫描的输入字符，便能唯一地确定FA的下一状态。在转换图上看，若|?|=n，则任何结点所引出的矢线至多有n条，且矢线上的标记均不同。 例如，P51图3-4所对应的DFA为 M=({R,U,S},{0,1},f,R,{S}) 其中，f的定义如下：f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S 由DFA与状态转换图的关系可知，构造状态转换图的算法，同样适用于构造DFA。 实际上，我们可以证明，?正规文法G，?DFA M，使 L(M)=L(G)，反之亦然。 3.3.2非确定的有限自动机 若在一左线性文法中含有多个右部相同的产生式，如 A?Ua B?Ua C?Ua ? X?Ua, 或在一右线性文法中同时含有形如 U?aA U?aB U?aC ? U?aX 的产生式， 在相应的状态转换图中，就会出现这样的结点U，它具有多条标记为同一输入符号a的矢线，如右图所示 非确定有限自动机的定义 在形式上，NFA M同样可用五元式定义：M=(K,?,f,S0,Z)，其中，K, ?,S0,Z的含义同DFA,转换函数f的定义为 f: K????(K),即将(Si,aj)映射到K的一个子集{Sk1,…,Skm} 类似地，我们可把f的定义域拓广到K??* ： (1) f^(S,?)={S}; (2)f^(S,aw)=f^(f(S,a),w) a??,w??*. 再设 f(S,a)= {Sk1,…,Skm} ,且定义 NFA的接受集 对于x??*,若集合f(S0,x)中含有Z中的元素（终态），则说明，至少存在一条从初态S0到某一终态的路径，此路径上的符号之连接恰为x，此时，我们称x为M所接受 所有为M所接受的符号串之集称为NFA M的接受集（或识别集），记作 L(M).即 L(M)={x | f(S0, x )? Z ? ?, x??} 例3.1 给定M= ({S,A,B,C}, {a,b}, f , S ,{C}),其状态转换图见右。由图可知M是一NFA。 M识别符号串ababb的路径为 S(a)?A(b)?B(a)?A(b)?B(b)?C(接受)。(参见书中P60的表) 3.3.3 NFA与DFA的等价性 定理3.1 对于字母表?上的任一NFA M，必存在与M等价的DFA M’ 证明 设 M=(K,?,f,S0,Z) 是?上的NFA，现构造?上DFA M’=（K’,?,f’,S0’,Z’).方法如下： 1.K’=?(K).为表示方便,设K某子集为{S1,S2,…,Si},记相应的状态为[S1,S2,…,Si].特别地,令S0’=[S0]. 2.映射f’的定义: f’([S1,S2,…,Si],a)=[R1,R2,…,Rj] iff f({S1,S2,…,Si},a)={R1,R2,…,Rj} 3.M’的终态集Z={[Sp,Sq,…,Sr]|{Sp,Sq,…,Sr}?Z??} 现在,我们证明,M’与M等价