资源描述：
《第03章 词法分析与有穷自动机ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.4.5DFA的化简1.DFA的化简所谓一个DFAM的化简是指寻找一个状态数比M少的DFAM'，使得L(M)=L(M')。(1)没有多余状态。化简了的DFA满足两个条件:(2)它的状态集中没有两个状态是互相等价的。所谓有穷自动机的多余状态是指从该自动机的开始状态出发，任何输入串不能到达的状态。3.4.5DFA的化简2.多余状态3.等价状态设DFAM＝(Q,Σ,f,S0,Z),s,t∈Q，若对任何*,f(s,)∈Z当且仅当f(t,)∈Z，则称状态s和t是等价的。例如，终态与非终态是可区别的。因为终态有一条到达自身的ε道
2、路，而非终态没有到达终态的ε道路。3.4.5DFA的化简如果s和t不等价,则称s和t是可区别的。5.化简方法一致性条件:状态s和t必须同时为终态或非终态。4.两个状态等价的条件:蔓延性条件:对于所有输入符号a,状态s和t必须转到等价的状态里。输入：一个DFAM。输出：接受与M相同语言的DFAM'，且其状态数最少。3.4.5DFA的化简无多余状态下把M的状态集Q划分成一些不相交的子集，使得每个子集中任何两个状态是等价的，而任何两个属于不同子集的状态都是可区别的。化简方法:然后在每个子集中任取一个状态作“代表”,而删去子集中其余状态
3、,并把射向其余状态的箭弧都改作射向作“代表”的状态中。3.4.5DFA的化简{A,F,G}{I,L,M}{W,Z}{E,H,K}{O,R,T,X}AMWHT下面给出化简算法的具体执行步骤:1.将DFAM的状态集Q分成两个子集：终态集F和非终态集¬F，形成初始分划∏。2.对∏使用如下方法建立新划分∏NEW：(1)把G划分成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号a，状态s和t转换到的状态都属于∏的同一子集。对∏的每个状态子集G:3.4.5DFA的化简用G划分出的所有新子集替换G,形成新的划分∏NEW；如
4、果∏NEW＝∏，则执行第4步；否则令∏＝∏NEW，重复第2步。划分结束后，对划分中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把指向其它状态的箭弧改为指向这个作为代表的状态。3.4.5DFA的化简例1.将右面的DFA最小化初始分划∏=({A,B,C,D}{E}){A,B,C,D}a={B}分析由图可知，给定的DFA中无多余状态。{A,B,C,D}b={C,D,E}∏=({A,B,C}{D}{E}){A,B,C}a={B}{A,B,C}b={C,D}∏=({A,C}{B}{D}{E}){A,C}a={B}{A,
5、C}b={C}∏=({A,C}{B}{D}{E})aABCDEaaaabbbbbEDBAaaaabbbb例2.将右面的DFAM最小化{1,2}l={2}∏=({1,2}{0})分析由图可知，给定的DFA无多余状态。初始分划∏=({1,2}{0}){1,2}d={2}ld02lld1d01ll3.4.5DFA的化简3.4.6有穷自动机到正规式的转换1.在M的转换图上添加两个结点：X结和Y结。从X结点用ε连线连结到M的所有初态结点，从M的所有终态结点用ε连线连结到Y结，从而构成一新的非确定有穷自动机M’，它只有一个初态结X和一个终态
6、结Y。显然，L(M)=L(M’)。即，这两个NFA是等价的。3.4.6有穷自动机到正规式的转换2.逐步消去M’中的其它结点，直至只剩下X，Y结点。在消除结点过程中，逐步用正规式来标记相应的箭弧。消除结点的过程是很直观的，只需反复使用下图的替换规则即可。3.4.6有穷自动机到正规式的转换对于代换为ABr1r2ACBr1r2对于ABr1
7、r2代换为代换为ABr1r2*r3ABr1r2对于ACBr1r3r23.4.6有穷自动机到正规式的转换例1.设有穷自动机的状态图如图所示试求该自动机识别语言的正规式。R=(10
8、01)(10
9、01)
10、*3.5正规文法与有穷自动机前面提到程序设计语言的单词符号可用乔母斯基3型文法——正规文法来描述对于正规文法所描述的语言可用一种有穷自动机来识别下面分别就左线性正规文法/右线性正规文法给出构造相应有穷自动机的方法3.5正规文法与有穷自动机右线性正规文法到有穷自动机的转换方法则相应的有穷自穷自动机M=(Q,Σ,f,q0,Z)1.令Q=VN∪{D}(DVN)Z={D}Σ=VTq0=S2.对G中每一形A→aB(A,B∈VN,a∈VT∪{ε})的产生式,令f(A,a)=B设给定了一个右线性正规文法G=(VN,VT,P,S)∈/a=εA→
11、B令f(A,ε)=BA→aBA→a3.5.1右线性正规文法到有穷自动 机的转换方法3.对G中每一形如A→a(A∈VN,a∈VT)的产生式,令f(A,a)=D4.对G中每一形如A→ε(A∈VN)的产生式,令A为接受状态或令f(A,ε)=D例1构造下述文法G[Z]的
