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

DFA的优化

要优化DFA, 你必须遵循各个步骤。这些如下:

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

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

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

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

δ (q, a) = p
δ (r, a) = p

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

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

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

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

DFA的优化

解:

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

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

DFA 1的优化

第三步:

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

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

DFA 2的优化

2.其他集合包含从最终状态开始的那些行。

DFA 3的优化

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

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

DFA 4的优化

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

DFA 5的优化

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

最小化DFA的过渡图:

DFA 6的优化

图:最小化的DFA

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

评论 抢沙发

评论前必须登录!