编译原理学习笔记(十五)~最小化DFA |
您所在的位置:网站首页 › 最小化设计强调的是 › 编译原理学习笔记(十五)~最小化DFA |
概念
最小化:优化DFA,使其状态数最少。 那么什么时候状态数是最少的呢?这里我们需要介绍两个新的名词:可区分和不可区分。 官方定义: 可区分:对于任何两个状态t和s,若从一状态出发接受输入字符串ω,而从另一状态出发不接受ω,或者从t出发和从s出发到达不同的接受状态,则称ω对状态t和s是可区分的。 不可区分:设想任何输入序列ω对s和t均是不可区分的,则说明从s出发和从t出发,分析任何输入序列ω均得到相同结果。因此,s和t可以合并成一个状态 通俗一点的来说,可区分状态可以理解为两个(或多个)状态根本不是一类,根据下一个输入的符号,不同状态得到的结果可能会出现不同。而不可区分状态就是,这两个(或多个)状态,无论下一个接收的符号是什么,得到的结果都是一样的。【定义理解不懂的,可以参考后面的例子思考,应该会容易一点点】 综上所述,DFA的最小化就是找出DFA中所有的不可区分状态,把它们合并为一个状态,这样可以简化DFA的状态数,显得更加简洁。 举例说明下图是一个没有最小化的DFA 从上的分析可以看出,ABC不是同一类的,属于可区分,因为在接收b的时候,出现了分歧。 然后再加上AC是一类,B单独一类,D单独一类。 AC接收a,到达的状态都是BAC接收b,到达的状态都是C从上面的分析我们可以发现,AC是一类,不可区分,因为无论输入a,还是b,它们最终到达的状态都是一样的,所以我们可以说它们是不可区分的。在最小化DFA中,AC是可以合并为一个状态的。 所以最后的最小化DFA就是: |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |