《编译原理及实现技术：4.词法分析__NFA与最小化》由会员分享，可在线阅读，更多相关《编译原理及实现技术：4.词法分析__NFA与最小化（22页珍藏版）》请在装配图网上搜索。
1、第二章：词法分析 NFA与自动机的最小化2内容介绍w 非确定有限自动机（NFA）的定义w NFA到DFA的转换w 自动机的最小化w 自动机的化简31.1 非确定有限自动机的定义w 非确定有限自动机NFA为一个五元组(,S,S0,f,Z)，其中：v是一个有穷字母表，它的每个元素称为一个输入字符；vS是状态的集合，它的每个元素称为一个状态；vS0 S，是非确定有限自动机的初始状态集；vf是一个从S()到S 的子集的映射，即 S()2svZS，是一个终止状态集，又称为接受状态集41.2 DFA和NFA的区别w 总结来看有3点区别w 一个状态的不同输出边可以标有相同符号w 允许有多个开始状态1.允许有
2、空边51.3 NFA的一些问题w NFA所能接受的串与DFA的定义是相同的w 实现起来很困难a a,b102aba62.1 自动机等价w 定义：设A1和A2是同一个字母表上的自动机，如果有L(A1)=L(A2),则称A1和A2等价w 定理：对于每一个非确定自动机A,存在一个确定自动机A,使得L(A)=L(A)72.2 NFA到DFA的转换 w状态集I的闭包：设I是NFA M状态集的子集，定义I的闭包-CLOSURE(I)为：w 若q I,则q _CLOSURE(I).1.若q I,那么从q出发经任意条弧而能到达的任何状态q都属于-CLOSURE(I).82.2 NFA到DFA的转换 w状态集I
3、的a转换：若I=S1,Sm 是NFA的状态集的一个子集，a,则定义:Ia=-CLOSURE(J)其中:J=f(S1,a)f(S2,a)f(Sm,a)92.2 NFA到DFA的转换 w 已知 A：NFA,构造 A:DFAw 令A的初始状态为I0=_CLOSURE(S1,S2,Sk),其中S1Sk是A的全部初始状态。w 若I=S1,Sm是A的一个状态，a，则定义f(I,a)=Ia将Ia加入S，重复该过程，直到S不产生新状态。1.若I=S1,Sn是A的一个状态,且存在一个Si是A的终止状态，则令I为A的终止状态。102.2 NFA到DFA的转换a 219b45aa3 8 bba67例子：112.2
4、NFA到DFA的转换 输入字 状态ab+1,22,4,5,6,73,8-2,4,5,6,73,8,93,89-3,8,99-9122.2 NFA到DFA的转换w 转化后的结果1,2对应12,4,5,6,7对应23,8对应33,8,9对应49对应513245babaa132.2 NFA到DFA的转换w 另外一种消除空边的转换方式w 删去空边，增加0到2的边w 环路的时候，就把这几个状态合成一个a 10a2aa10a2142.3 自动机的最小化w 定义：等价状态 设DFA M 的两个状态S1和S2,如果对任意输入的符号串x，从S1和S2出发，总是同时到达接受状态或拒绝状态中，则称S1和S2是等价的
5、。1234567abccbd152.3 自动机的最小化w 定义：无关状态 设S是DFA M的一个状态，若：w 从开始状态无到S的通路，或w S到任意终止状态无通路 则称S为M的无关状态 102ab102ab162.3 自动机的最小化w 定义：最小(最简)自动机 如果DFA M 没有无关状态，也没有等价状态，则称M 为最小自动机w 结论：任一DFA都可以化为最简自动机，即任一DFA M都存在DFA M，使得 L(M)=L(M)，且M是最简自动机 172.4 自动机的化简w 状态分离法w 终止状态为一组，非终止状态为一组w 对每一组进行分离，若每组中的元素映射到不同的组，则表示他们不等价，就可以划分出来。1.重复2，知道没有新组产生，此时每组中的状态都为等价状态。182.4 自动机的化简w 例1aa17b32bab5abaa46bb8bab192.4 自动机的化简1,3ba4,6,7,8a2,5bb202.4 自动机的化简w 例2a15b2b34bbaaaab212.4 自动机的化简aa125b34bbaaabaCDBAEFSbaaaaabbbbbabF
编译原理及实现技术：4.词法分析__NFA与最小化
