第3章+词法案例.ppt

∑*上的符号串t被NFA M接受也可以这样理解：对于Σ﹡中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFA M所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的道路,其上所有弧的标记均为ε，那么空字可为M所接受。 3.4.3 NFA转换为等价的DFA 对每个NFA 　N一定存在一个DFA　Ｍ ，使得 L(M)=L(N)。对每个NFA N存在着与之等价的DFA M。 基本思路（子集法） DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态. 定义对状态集合I的几个有关运算：1. 状态集合I的ε-闭包，表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。 状态集合I的任何状态S都属于ε-closure(I)。2. 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。 例 ?-closure(0)={0,1,2,4,7} move({0,1,2,4,7},a)={3,8} ?-closure({3,8})={1,2,3,4,6,7,8} NFA确定化算法假设NFA N=(K, ?,f,K0,Kt)按如下办法构造一个DFA M=(S, ?,d,S0,St)，使得L(M)=L(N)：1. M的状态集S由K的一些子集组成。用[S1, S2,... ,Sj]表示S的元素，其中S1, S2,... , Sj是K的状态。并且约定，状态S1, S2,... ,Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2];2. M和N的输入字母表是相同的，即是?；3. 转换函数是这样定义的：d([S1, S2,... ,Sj],a)= [R1,R2,... ,Rt],其中[R1,R2,... , Rt]=?-closure(move({S1, S2,…, Sj},a)) 4. S0=?-closure(K0)为M的开始状态；5. St={[Si, Sk,…, Se]，其中[Si, Sk,... ,Se]?S且{Si , Sk,... , Se}?Kt??} 构造NFA N的状态K的子集的算法假定所构造的子集族为C，即C= (T1, T2,... , TI),其中T1, T2,... , TI为状态K的子集。1. 开始，令?-closure(K0)为C中唯一成员，并且它是未被标记的。2. while (C中存在尚未被标记的子集T) do { 标记T; for 每个输入字母a do { U:= ?-closure(move(T,a)); if U不在C中 then 将U作为未标记的子集加在C中 } } 3.4.4 确定有穷自动机的化简 对于任一个DFA，存在一个唯一的状态最少的等价的DFA。 一个有穷自动机是化简了的，即是说它没有多余状态并且它的状态中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 所谓有穷自动机的多余状态是指是指这样的状态：从该自动机的开始状态出发，任何输入串也不能到达那个状态。 0 1 s0 s1 s2 s3 s5 s7 s1 s5 s1 s2 s2 s5 s5 s1 s1 s3 s0 s1 0 1 s0 s1 s2 s3 s4 s5 s6 s7 s8 s1 s5 s7 s2 s2 s5 s5 s7 s5 s6 s1 s3 s8 s0 s0 s1 s3 s6 例: 画状态图可以看出s4,s6,s8为不可达状态应该消除 状态s和t的等价条件是: 一致性条件：状态s和t必须同时为可接受状态或不接受状态。 蔓延性条件：对于所有输入符号,状态s和t必须转换到等价的状态里。 有穷自动机的状态s和t不等价,称这两个状态是可区别的。 DFA的最小化算法- “分割法” 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的。 3.5正规式和有穷自动机的等价性 有穷自动机和正规表达式的等价性：1.对于∑上的一个NFA M，可以构造一个∑上的正规式R,使得L(R)=L