第3章词法与有限自动机案例.ppt

4、确定有限自动机的化简 终态和非终态是可区别的。 （3）状态等价的条件 一致性条件：状态 s 和 t 必须同时为终态或非终态。 蔓延性条件：对于所有输入符号，状态 s 和 t 必须转化到等价的状态里。 等 价 4、确定有限自动机的化简 （4）DFA最小化的任务 确定有限自动机化简的任务是去掉多余状态，合并等价状态。多余状态是指从该自动机的开始状态出发，任何输入串也不能达到的状态，即从初态结点开始永远到达不了的那些状态。 （5）DFA最小化算法（子集分割算法） 基本思想 将DFA M中的状态集分割成一些互不相交的子集，使得任何不同的两个子集中的状态都是可区别的，而同一个子集中的任何两个状态都是等价的。 从每个子集中任选一个状态作为代表，同时消去其它等价状态及其射出的弧。 把那些原来到达其它等价状态的弧改为到达相应的代表状态。 （5）DFA最小化算法（子集分割算法） 具体步骤 初始分割：把状态集S划分为终态集和非终态集，记为 其中， 属于终态集， 属于非终态集。 k次分割：假定经过k次划分后， 得到m个子集， 记为 ，并且属于不同子集中的状态都是可区别的。检查 中的每个子 集 ，看其能否进一步分割。令 ，若存在一个输入字符a（a∈Σ），使得 不全包含在现行分割 的某一子集 中，就将 一分为二。 4、确定有限自动机的化简 分割办法： 假设当前子集 ，若状态q1和q2经a弧分别到达状态t1和t2，而t1和t2又分属于当前已划分出的两个不同子集 和 中，则此时应将 分为两半，使得一半含有q1，另一半含有q2。 4、确定有限自动机的化简 q1和q2不等价 t1和t2不等价 （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、确定有限自动机的化简 4、确定有限自动机的化简 【例3.13】 对下图所示的DFA M进行化简。 解：①初始分割 将状态集S={0，1，2，3，4，5，6}划分为终态集{3，4，5，6}和非终态集{0，1，2}。 4、确定有限自动机的化简 ② 考察{3，4，5，6} 所以，{3，4，5，6}不再分割。 ③考察{0，1，2} 由于 ，所以，应将{0，1，2}分割为{0，2}和{1}。 至此，得到的全部分割子集为{3，4，5，6}，{0，2}和{1}。 4、确定有限自动机的化简 ④考察{0，2} 所以，将{0，2}分割为{0}和{2}。 最后，得到的全部分割子集为{0}，{1}，{2}，{3，4，5，6}。每个子集均不需再分割，即每个子集内的状态互相等价，任意不同两个子集中的状态都是可区别的。 4、确定有限自动机的化简 ⑤选代表，删除多余状态 令状态3代表{3，4，5，6}，把原来导入4