编译原理4(09-10用).ppt

为了说明DFA如何作为一种识别机制,我们还要理解下面的定义 ∑*上的符号串t被M接受 对于∑*中的任何符号串t,若存在一条从初态到某一终态的道路,且这条道路上所有弧的标记连接成的字符串等于t,则称t可为DFA M 所接受.若M的初态同时又是终态，则空字可为M所识别(接受)。 　　 即：若t∈∑*，f(S，t)=P，其中S为 M的开始状态，P∈Z，Z为终态集。　　 则称t为DFA M所接受（识别） DFA M所能接受的符号串的全体记为 L(M) ∑*上的符号串t在M上运行 一个输入符号串t,（我们将它表示成Tt1的形式，其中T∈∑，t1∈∑*）在DFA M上运行的定义为：　　f（Q，Tt1）=f（f（Q，T），t1） 其中Q∈K 扩充转换函数f，是K×Σ*→K上的映射，且: f（ki，ε）= ki　　 DFA的最小化算法 正规式、正规文法、自动机的相互转换关系 （2）所有3个0的字符串的集合。 正规式为：1*01*01*01* 1 1 1 A 0 B C 0 D 0 1 描述下列正规式所表示的语言 （1）0(0|1)*0 (2)(0|1)*0(0|1)(0|1) (3)0*10*10*10* 解：以0开头并且以0结尾的0、1串。 解：由0、1组成的串,且从右边开始数第三位为0。 解：含3个1的0、1串。 对下列语言分别写出它们的正规式： （1） Σ＝{0,1}上含偶数个1的所有串 （2） Σ＝{0,1}上含奇数个1的所有串 解：(0|10*1)* 解：(0|10*1)* 0*10* 4 f 3 5 6 2 1 i ? ? ? ? a a a a b b b b 例： NFA＝DFA 等价的DFA a C D B A E F S b a a a a a b b b b b a b F 确定有穷自动机的化简 寻找一个状态数最少DFA M’,使得L(M)=L(M’) 说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。 ? DFA的最小化就是寻求最小状态DFA 最小状态DFA的含义: 没有多余状态(死状态) 没有两个状态是互相等价（不可区别） 两个状态s和t等价的条件： 兼容性（一致性）条件——同是终态或同是非终态 传播性（蔓延性）条件——从s出发读入某个a?a???和从t出发读入某个a到达的状态等价。 例： b 0 2 b b 1 a 3 b a a 4 a b 状态0和状态4是可区别状态，状态2和状态3也是可区别状态，因为：2状态输入b 到达2状态（非终态），而3状态输入b 到达4状态（终态） C和D同是终态,读入a到达C和F, C和F同是终态, C和F读入a都到达C,读入b都到达E. C和D等价 a C D B A E F S b a a a a a b b b b b a b F 最小状态DFA 对于一个DFA M =（K,∑,f, k0,,kt)，存在一个最小状态DFA M’ =（K’,∑,f’, k0’,,kt’),使L(M’)=L(M). 结论 接受L的最小状态有穷自动机不计同构是唯一的。 DFA M =（K,∑,f, k0,,kt)的最小状态DFA M’ (1)构造状态的一个初始划分∏ ： 终态kt和非终态K- kt两组 (2)对∏施用过程PP构造新划分∏new (3)如∏new=∏ ，则令∏final=∏并继续步骤(4),否则∏:=∏new重复(2). (4)为∏final中的每一组选一代表，这些代表构成M’ 的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=r 过程PP：构造∏new ① 对∏每一个状态组G进行下述工作：　　将G划分为子组。G的两个状态s和t分在同一子组的充要条件是：对所有的输入符号a，状态s和t的a转换都是∏的同一组中的状态。 ②形成的所有子组成为∏new的状态组。 “分割法” ——DFA的最小化算法的核心 把一个DFA的状态分成一些不相交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是等价的.最后每个子集中选出一个代表，同时消除其他等价状态。 DFA的最小化—例子 1、将M的状态分为两个子集一个由终态{C,D,E,F}组成一个由非终态{S,A,B}组成: 2、考察{S,A,B}是否可分。 C D B A E F S b a a a a a