構造一個確定性有限自動機 (DFA)，識別在字母表∑={0,1} 上的語言 {x | 1 的個數能被 2 整除，且 0 的個數能被 3 整除}。

問題

給定的語言 L={ x | 1 的個數能被 2 整除，且 0 的個數能被 3 整除}，字母表 ∑={0,1}。

解答

該語言分為兩部分，首先我們需要找到 1 的個數能被 2 整除的情況，其次找到 0 的個數能被 3 整除的情況，最後將兩部分結合起來生成結果。

步驟 1 - 第一部分的 DFA，1 的個數能被 2 整除。

這裡：

• q0 狀態下輸入 0 轉到 q0（最終狀態），生成字串 0，被該語言接受。

• q0 狀態下輸入 1 轉到 q1，q1 狀態下輸入 1 轉到 q0（最終狀態），生成字串 “11”，個數能被 2 整除。

• q0 狀態下輸入 0 轉到 q0，q0 狀態下輸入 1 轉到 q1，q1 狀態下輸入 0 轉到 q1，q1 狀態下輸入 1 轉到 q0（最終狀態），生成字串 “0101”，個數能被 2 整除。

步驟 2 - 第二部分的 DFA，0 的個數能被 3 整除。

這裡：

• q0’ 狀態下輸入 1 轉到 q0’（最終狀態），生成字串 1，被該語言接受。

• q0’ 狀態下輸入 0 轉到 q1’，q1’ 狀態下輸入 0 轉到 q2’，q2’ 狀態下輸入 0 轉到 q0’（最終狀態），生成字串 “000”，個數能被 3 整除。

步驟 3 - 最終的 DFA 是：第一部分 DFA × 第二部分 DFA。

狀態轉換圖

DFA 的狀態轉換圖如下所示：

Bhanu Priya

更新於：2021年6月15日

4K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習