个性化阅读
专注于IT技术分析

DFA最小化

点击下载

DFA的最小化意味着减少给定FA中的状态数。因此,在最小化FSM之后,我们获得了具有冗余状态的FSM(有限状态机)。

我们必须遵循各种步骤以最小化DFA。这些如下:

第1步:通过任意一组DFA转换,从初始状态中删除所有无法访问的状态。

步骤2:绘制所有状态对的转换表。

步骤3:现在将转换表分为两个表T1和T2。 T1包含所有最终状态,T2包含非最终状态。

步骤4:从T1查找相似的行,以便:

1. δ (q, a) = p
2. δ (r, a) = p

这就是说,找到两个具有相同a和b值的状态,然后删除其中之一。

步骤5:重复步骤3,直到在过渡表T1中找不到相似的行。

步骤6:对表T2也重复步骤3和步骤4。

步骤7:现在合并简化的T1和T2表。组合的过渡表是最小化DFA的过渡表。

例:

解:

步骤1:在给定的DFA中,q2和q4是无法访问的状态,因此请将其删除。

步骤2:绘制其余状态的转换表。

01
→q011第3季
q100第3季
*q3q5q5
*q5q5q5

步骤3:现在将转换表的行分为两组:

1.一组包含从非最终状态开始的那些行:

01
q011第3季
q100第3季

2.另一组包含从最终状态开始的那些行。

01
q3q5q5
q5q5q5

步骤4:集合1没有相似的行,因此集合1将相同。

步骤5:在集合2中,第1行和第2行相似,因为q3和q5转换为0和1上的相同状态。因此,跳过q5,然后用其余的q3替换q5。

01
q3第3季第3季

步骤6:现在将集合1和集合2组合为:

01
→q011第3季
q100第3季
*q3第3季第3季

现在,它是最小化DFA的转换表。


赞(0)
未经允许不得转载:srcmini » DFA最小化

评论 抢沙发

评论前必须登录!