编译原理第三章剖析.ppt

* 4.2.4 DFA的程序模拟 DFA M=（K，Σ，f，S，Z）的行为的模拟程序 K = S； c = getchar; while c eof do { K = f(K,c); c = getchar; }; if K is in Z then return (‘yes’) Else return (‘no’) * 4.3 非确定有限自动机NFA 一个非确定有限自动机NFA M是一个五元式： M = (S，Σ，δ，S0，F) 其中： S是一个有限集，它的每个元素称为一个状态； ∑是一个有穷字母表，它的每个元素称为一个输入字符； δ是一个从S x ∑*至S的子集的映射，即δ： S x ∑* →2s（S集合的幂集/S的所有子集的集合） S0 S，是一个非空初态集。 F S,是一个终态集（可空）。 * 对于∑*中的任何一个字α，若存在一条从某一初态结点到某一终态结点的通路，且这条通路上所有弧的标记字依序连接成的字（忽略那些标记为ε的弧）等于α，则称α可为NFA M所识别（读出或接受）。若M的某些结点既是初态结点又是终态结点，或者存在一条从初态结点到某一终态结点的ε通路，那么，空字ε可为M所接受。 例子：识别所有含有相继两个a或相继两个b的字NFA。 5 X 1 2 3 4 6 Y a a a a b b b b ε ε ε ε * 4.4 DFA M和NFA M的等价性 定理：对于每个NFA M存在一个DFA M′，使得L(M) = L(M′) 证明思想：用M′的一个状态对应M的一个状态集合，用这种方法，能从一个NFA M构造一个DFA M′使得L（M′） = L（M）， 这种方法称作子集构造法。 * 4.4.1 状态集的ε闭包定义 设I是有限自动机的状态集的子集，I的ε闭包ε_CLOSURE(I)为： (1) 如果状态q∈I，则q∈ε_CLOSURE（I）（既I中的状态全部属于ε_CLOSURE(I)） (2) 如果状态q∈I，那么从状态q出发经过任意ε弧而能到达的任何状态q′都属于ε_CLOSURE(I)。（注意：可以连续经过多条ε弧） * 4.4.2 有限自动机的转移函数 假定I是非确定有限自动机的状态集的子集，则定义： Ia =ε_CLOSURE(J) 其中：a∈Σ，J是从I中的某一状态结点出发经过一条a弧而达到的状态结点的全体。 * 4.4.3 从NFA M 构造DFA M的步骤（方法） （1）设NFA M = S，Σ，δ，S0，F，对M的状态图进行改造： 引进新的初态结点X和终态结点Y， 且X，Y ? S，从X到S0中任意状态结点连一条ε箭弧，从F中任意状态结点连一条ε箭弧到Y； 对M中的状态图进行下图所示的替换，其中k是新引进的状态。重复这种分裂过程直到状态图中的每条箭弧上的标记或为ε，或为Σ中的单个字母。将最终得到的NFA记为M′，显然L（M′）= L（M） i j i k j AB A B i j A|B i j A* i j A B i k j ε ε A * （2）将非确定有限自动机M′转换成确定有限自动机M方法：假设Σ={a1，a2，a3，…，ak}，构造状态转化表，表的构成： a) 每一行包含k+1列，首行首列为ε_CLOSURE(X)； b) 如果每行的第一列假定为I，则该行的i+1列为Iai(i= 1，2，…，k)。然后检查该行的所有状态子集，将未曾在第一列出现的填入到后面空行的第一列。 c) 重复上述b)，直到出现在表的第i+1列上的所有状态子集均在第一列中出现。 d) 将构造出来的表视为状态转换表，将其中的每个状态子集视为新的状态，显然该表唯一的刻画了一个DFA M，该有限自动机的初态为该表的首行首列，终态为那些包含原终态的状态子集。显然L(M)=L(M)=L(M) * 例子：p50正规式（a|b）*（aa|bb）（a|b）*对应的NFA如例3.3中图。其中X为初态，Y为终态。状态转换矩阵如下表： I J Ia J Ib {X,5,1} {5,3} {5,3,1} {5,4} {5,4,1} {5,3,1} {5,3,2} {5,3,1,2,6,Y} {5,4} {5,4,1} {5,4,1} {5,3,1} {5,4,1,2,6,Y} {5,3,1,2,6,Y} {5,3,1,2,6,Y} {5,4,1,6,Y} {5,4,1,6,Y} {5,3,1,6,Y} {5,4,1,2,6,Y} {5,4,1,2,6,Y} {5,3,1,6,Y} {5,4,1,2,6,Y} {5,3,1,6,Y} {5,3,1,2,6,Y} {5,4,1,6