第3章词法分析与有限自动机.pptVIP

4、确定有限自动机的化简（1）DFA的化简（最小化DFA） 对于任意给定的DFAM，构造另一个DFAM′，使得L(M)=L(M′)，且DFAM′的状态个数为最少。（2）状态等价和可区别 假定s和t是M的两个不同状态，如果从状态s出发能读出某个字w而停于终态，从状态t出发也能读出同样的字w而停于终态，反之亦然，就称状态s和t是等价的；如果DFAM的两个状态s和t不等价，则称状态s和t是可区别的。可区别等价第62页，共95页，星期日，2025年，2月5日4、确定有限自动机的化简 终态和非终态是可区别的。（3）状态等价的条件一致性条件：状态s和t必须同时为终态或非终态。蔓延性条件：对于所有输入符号，状态s和t必须转化到等价的状态里。等价第63页，共95页，星期日，2025年，2月5日4、确定有限自动机的化简（4）DFA最小化的任务 确定有限自动机化简的任务是去掉多余状态，合并等价状态。多余状态是指从该自动机的开始状态出发，任何输入串也不能达到的状态，即从初态结点开始永远到达不了的那些状态。（5）DFA最小化算法（子集分割算法）基本思想将DFAM中的状态集分割成一些互不相交的子集，使得任何不同的两个子集中的状态都是可区别的，而同一个子集中的任何两个状态都是等价的。从每个子集中任选一个状态作为代表，同时消去其它等价状态及其射出的弧。把那些原来到达其它等价状态的弧改为到达相应的代表状态。第64页，共95页，星期日，2025年，2月5日（5）DFA最小化算法（子集分割算法）具体步骤初始分割：把状态集S划分为终态集和非终态集，记为其中，属于终态集，属于非终态集。k次分割：假定经过k次划分后，得到m个子集，记为

，并且属于不同子集中的状态都是可区别的。检查中的每个子集，看其能否进一步分割。令，若存在一个输入字符a（a∈Σ），使得不全包含在现行分割的某一子集中，就将一分为二。4、确定有限自动机的化简第65页，共95页，星期日，2025年，2月5日分割办法： 假设当前子集，若状态q1和q2经a弧分别到达状态t1和t2，而t1和t2又分属于当前已划分出的两个不同子集和中，则此时应将分为两半，使得一半含有q1，另一半含有q2。4、确定有限自动机的化简q1和q2不等价t1和t2不等价第66页，共95页，星期日，2025年，2月5日（5）DFA最小化算法（子集分割算法）具体步骤循环分割：重复上一步，直到子集个数不再增加为止（即每个子集已是不可再分的了）。所谓不能划分，是指该子集或者仅有一个状态，或者虽有多个状态但这些状态均不可区别（即等价）。选代表，删除等价状态：对于最后分划中的每一个子集，选取该子集中的一个状态代表其它等价状态。例如，状态子集I={q1,q2,…，qk}，挑选q1作为子集I的代表，则凡导入到q2，…，qk的弧都改成导入到q1中，然后将q2，…，qk及其所射出的弧从原来的DFA中删除。决定初态和终态：设删除等价状态之后的DFA为M′，凡那些包含M的初态的状态子集所对应的代表状态均作为M′的初态；凡那些包含M的终态的状态子集所对应的代表状态均作为M′的终态。则有L(M′)=L(M)。4、确定有限自动机的化简第67页，共95页，星期日，2025年，2月5日4、状态转换图的代码实现elseif(ch===)return($ASSIGN,－);elseif(ch==+)return($PLUS,－);elseif(ch==*){GetChar(); if(ch==*)return($POWER,－); Retract();return($STAR,－);}elseif(ch==;)return($SEMICOLON,-);elseif(ch==()return($LPAR,-);elseif(ch==))return($RPAR,-);