欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

确定有穷自动机(DFA)化简(最小化)

程序员文章站 2024-02-13 14:33:28
...

预备

  • 最简化的DFA:这个DFA没有多余状态、也没有两个相互等价的状态。一个DFA可以通过消除无用状态合并等价状态而转换成一个与之等价的最小状态的有穷自动机。
  • 无用状态:从自动机开始状态出发,任何输入串也发到达的那个状态,或者这个状态没有通路可达终态。
  • 等价转态:两个状态,识别相同的串,结果都同为正确或错误,这两个状态就是等价的。
  • 区别状态:不是等价状态。

化简DFA

  • 分割法:把一个DFA(不含多余状态)的状态分割成一些不相交的子集,并且任意两个子集之间的状态都是可区别状态,同一子集内部的状态都是等价状态。

  • 步骤(按分割法)

    • I0 = 非状态元素构成的集合,I1 = 终态元素构成的集合
    • 经过多次划分后,要保证,任意一个Ik中的元素通过move(Ik,某个字符)的结果都同属于一个Iz,这时候划分完成。否则把状态不同的单独划分出去。
    • 重复上一步,直至没有新的I子集增加。
    • 从子集中任选一个代替整体,画出最简DFA。

例子

  • 题目:将下图DFA M最小化

确定有穷自动机(DFA)化简(最小化)

  • 分割成I0,I1
-----------------I0、I1分割-------------------
I0 = {1,2,3,4} ; 非终态
I1 = {5,6,7} ; 终态
  • 检验I0中元素的等价性,不等价就分割
move(1,a) = 6 ∈I1
move(1,b) = 3 ∈I0

move(2,a) = 7 ∈I1
move(2,b) = 3 ∈I0

move(3,a) = 1 ∈I0
move(3,b) = 5 ∈I1

move(4,a) = 4 ∈I0
move(4,b) = 6 ∈I1

可以发现,{1,2}是等价的,{3,4}是等价的
所以现在分割成了:I2 = {1,2}, I1 = {5,6,7}, I3 = {3,4}
  • 检测I2中元素的等价性,不等价就分割
move(1,a) = 6 ∈I1
move(1,b) = 3 ∈I3

move(2,a) = 7 ∈I1
move(2,b) = 3 ∈I3

可以发现,是等价的,不用分割
  • 检测I3中元素的等价性,不等价就分割
move(3,a) = 1 ∈I2
move(3,b) = 5 ∈I1

move(4,a) = 4 ∈I3
move(4,b) = 6 ∈I1
可以发现,不是等价的,分割成{3},{4}
所以现在分割成了:I2 = {1,2}, I1 = {5,6,7}, I4 = {3}, I5 = {4}
  • 检测I1中元素的等价性,不等价就分割
move(5,a)  = 7 ∈ I1
move(5,b)  = 3 ∈ I4

move(6,a)  = 4 ∈ I5
move(6,b)  = 1 ∈ I2

move(7,a)  = 4 ∈ I5
move(7,b)  = 2 ∈ I2

可以发现,不是等价的,分割成{6,7}, {5}
所以现在分割成了:I2 = {1,2}, I4 = {3}, I5 = {4}, I6 = {5},I7 = {6,7} 
  • 检测后发现,不可再分割,所以最终分割结果就是:I2 = {1,2}, I4 = {3}, I5 = {4}, I6 = {5},I7 = {6,7}

  • 画转态转换图:从集合中选取一个代表就可以
    确定有穷自动机(DFA)化简(最小化)

其它

课件下载:

关注下方微信公众号,
回复:
DFA化简.code

确定有穷自动机(DFA)化简(最小化)

相关标签: DFA DFA最小化