什麼是DFA的最小化？

問題

給定一個確定性有限自動機（DFA），嘗試透過去除不可達狀態和去除類似行來簡化DFA。

解決方案

步驟 1

從q0中移除不可達狀態

從初始狀態開始，我們無法到達q2和q4。因此，刪除這兩個狀態，如下所示：

移除不可達狀態後，部分最小化的DFA如下：

步驟 2

下面給出狀態轉換表：

步驟 3

將表格劃分為2個表格，如下所示：

表1從非終結狀態開始。

表2從終結狀態開始。

步驟 4

刪除類似的行。

表1沒有類似的行

表2有類似的行。因此，跳過q5並用q3替換q5

步驟 5

合併兩個表格，如下所示：

因此，最小化的DFA如下：

Bhanu Priya

更新於: 2021年6月12日

494 次瀏覽

啟動你的 職業生涯

透過完成課程獲得認證

開始