文章目錄

• 一、確定性有窮自動(dòng)機(jī)組成
• 二、確定性有窮自動(dòng)機(jī)計(jì)算過(guò)程
• 三、確定性有窮自動(dòng)機(jī)定義
• 四、自動(dòng)機(jī) 語(yǔ)言 與 等價(jià)
• 五、自動(dòng)機(jī)語(yǔ)言 示例

一、確定性有窮自動(dòng)機(jī)組成

---

DFA , 全稱為 Deterministic Finite Automaton , 確定性有窮自動(dòng)機(jī) ;

確定性 有窮自動(dòng)機(jī) 組成 : 由以下的 $5$ 部分組成 , 放入集合中展示 $\{Q,\Sigma ,,\delta ,q_0,F\}$ ;

① $Q$ 狀態(tài)集 : 有限個(gè)狀態(tài) ;

② $\Sigma$ 字母表 : 有限個(gè)字符集 , 長(zhǎng)度有限的字符串 ;

③ $\delta$ 轉(zhuǎn)移函數(shù) : $\delta$ 稱為轉(zhuǎn)移函數(shù) ; 基于當(dāng)前的 自動(dòng)機(jī) 的某個(gè)狀態(tài) , 將字符集 輸入到自動(dòng)機(jī)中 , 該自動(dòng)機(jī)轉(zhuǎn)換成另一個(gè)狀態(tài) , 這個(gè)轉(zhuǎn)換就是通過(guò) $\delta$ 轉(zhuǎn)換函數(shù)進(jìn)行的 , 使用公式描述 $Q\times \Sigma \to Q$ ;

④ $q_0$ 起始狀態(tài) : 是自動(dòng)機(jī)的開(kāi)始狀態(tài) ;

⑤ $F$ 接受狀態(tài)集 : $F$ 是 可接受狀態(tài) , 是 $Q$ 的子集 , 記做 $F?Q$ , 與 $F$ 可接受狀態(tài)相對(duì)的是不可接受狀態(tài) ;

二、確定性有窮自動(dòng)機(jī)計(jì)算過(guò)程

---

1 . 自動(dòng)機(jī)示例 : 上圖是上一篇博客的自動(dòng)機(jī)示例 , 自動(dòng)機(jī)開(kāi)始執(zhí)行后 , 將 字符串 “$0101$” 輸入到自動(dòng)機(jī)中 , 從 Start 出發(fā) , 根據(jù)當(dāng)前的自動(dòng)機(jī)狀態(tài) , 結(jié)合當(dāng)前處理的輸入字符 , 改變成另外一個(gè)自動(dòng)機(jī)狀態(tài) , 所有字符處理完畢后 , 查看當(dāng)前自動(dòng)機(jī)狀態(tài)是否是可接受狀態(tài) ;

2 . 自動(dòng)機(jī)運(yùn)行過(guò)程 : 詳細(xì)的計(jì)算過(guò)程 , 參考上一篇博客 : 【計(jì)算理論】自動(dòng)機(jī) 示例 ( 自動(dòng)機(jī)示例 | 自動(dòng)機(jī)表示方式 | 自動(dòng)機(jī)計(jì)算流程簡(jiǎn)介 )

3 . 自動(dòng)機(jī)定義由來(lái) : 將 $\{Q,\Sigma ,,\delta ,q_0,F\}$ 五個(gè)組件代入上述過(guò)程 , 就可以得到自動(dòng)機(jī)定義 ;

三、確定性有窮自動(dòng)機(jī)定義

---

確定性又窮自動(dòng)機(jī)定義

1 . 有以下已知條件 :

① 有窮自動(dòng)機(jī) : $M$ ;

② 輸入信息 : 接收 $w$ 字符串作為輸入 , $w$ 字符串可以寫(xiě)成 $\{w_1,w_2,w_3,?w_m\}$ 等 $m$ 個(gè)字符 ; 其中 每個(gè)字符都屬于有限字符集 $\Sigma$ 中的字符 , 這些字符有重復(fù)的 , 這是輸入序列 , 下面是狀態(tài)序列 ; $m$ 是總共計(jì)算的次數(shù) ;

③ 狀態(tài)序列 : 自動(dòng)機(jī) $M$ 有以下 $m+1$ 個(gè)狀態(tài)序列 , $\{r_0,r_1,r_2,?,r_m\}$ , 這個(gè)序列中的狀態(tài)有很多重復(fù)的 , 這是自動(dòng)機(jī)的執(zhí)行序列 , 途徑的狀態(tài) , 所有的狀態(tài)都屬于 $Q$ ; 這是 自動(dòng)機(jī) $M$ 計(jì)算過(guò)程中的 狀態(tài)序列 , 上面的輸入信息時(shí)每個(gè)狀態(tài)序列對(duì)應(yīng)的輸入序列 ; $m$ 是總共計(jì)算的次數(shù) ;

2 . 上述條件滿足如下計(jì)算 :

① 自動(dòng)機(jī)起始狀態(tài) : $r_0=q_0$ , 自動(dòng)機(jī) $M$ 開(kāi)始時(shí) , 是 $q_0$ 起始狀態(tài) , 相當(dāng)于上圖中的 Start 狀態(tài) ; 這也是為什么狀態(tài)序列比輸入信息序列多一個(gè)原因 , 狀態(tài)序列開(kāi)始必須有一個(gè)狀態(tài) , 之后每接受一個(gè)參數(shù)字符 , 就更新一個(gè)新的狀態(tài) , 之后就狀態(tài)與輸入字符就是一一對(duì)應(yīng)的 ; 最后狀態(tài)序列 比 字符序列多一個(gè) ;

② 自動(dòng)機(jī)計(jì)算 : 對(duì)于 $1=0,1,?,m?1$ , 有 $\delta (r_i,w_{i+1})=r_{i+1}$ , 意思就是 當(dāng)前是自動(dòng)機(jī)的一個(gè)狀態(tài) $r_i$ , 輸入一個(gè) $w_{i+1}$ 字符后 , 變成了 $r_{i+1}$ 狀態(tài) ;

③ 最終狀態(tài)可接受 : 最終的 $r_m$ 狀態(tài)必須是可接受狀態(tài) , $r_m\in F$ ;

3 . 自動(dòng)機(jī)組件 :

① $Q$ 狀態(tài)集 : 自動(dòng)機(jī)的有限個(gè)狀態(tài) , 其中有可接受狀態(tài) ( 雙圈 ) , 不可接收狀態(tài) ( 單圈 ) ;

② $\Sigma$ 字母表 : 有限個(gè)字符集 , 如 $\{0,1\}$ , 但其輸入可以是 $0101$ , 也可以是 $00111$ 等字符 ;

③ $\delta$ 轉(zhuǎn)移函數(shù) : $\delta$ 稱為轉(zhuǎn)換函數(shù) ; 基于當(dāng)前的 自動(dòng)機(jī) 的某個(gè)狀態(tài) , 將字符集 輸入到自動(dòng)機(jī)中 , 該自動(dòng)機(jī)轉(zhuǎn)換成另一個(gè)狀態(tài) , 這個(gè)轉(zhuǎn)換就是通過(guò) $\delta$ 轉(zhuǎn)換函數(shù)進(jìn)行的 , 使用公式描述 $Q\times \Sigma \to Q$ ;

④ $q_0$ 起始狀態(tài) : 是開(kāi)始狀態(tài) ;

⑤ $F$ 接受狀態(tài)集 : $F$ 是 可接受狀態(tài) , 是 $Q$ 的子集 , 記做 $F?Q$ , 與 $F$ 可接受狀態(tài)相對(duì)的是不可接受狀態(tài) ;

四、自動(dòng)機(jī) 語(yǔ)言 與 等價(jià)

---

1 . 自動(dòng)機(jī)語(yǔ)言 : 確定性有窮自動(dòng)機(jī) $M$ , 將自動(dòng)機(jī) $M$ 所接受的所有的字符串放在一個(gè)集合 $A$ 中 , 該集合 $A$ 稱為自動(dòng)機(jī) $M$ 的語(yǔ)言 , 自動(dòng)機(jī) $M$ 認(rèn)識(shí) ( 接受 ) $A$ 語(yǔ)言 , 記作 $L(M)=A$ ;

2 . 自動(dòng)機(jī)等價(jià) : 如果兩個(gè)自動(dòng)機(jī)認(rèn)識(shí)相同的語(yǔ)言 , 那么稱這兩個(gè)自動(dòng)機(jī)是等價(jià)的 ;

五、自動(dòng)機(jī)語(yǔ)言 示例

---

1 . 自動(dòng)機(jī)描述 :

自動(dòng)機(jī)有 $5$ 個(gè)狀態(tài) ;

$S$ 是開(kāi)始狀態(tài) ;

$q_1,r_1$ 是可接受狀態(tài) ;

$q_2,r_2$ 是不可接受狀態(tài) ;

自動(dòng)機(jī)語(yǔ)言是 $\{a,b\}$ 字符集 ;

下面開(kāi)始分析上面 $5$ 狀態(tài)自動(dòng)機(jī)的語(yǔ)言 ;

2 . 自動(dòng)機(jī) 左側(cè)分支分析 :

① 執(zhí)行流程 : 開(kāi)始時(shí) , 自動(dòng)機(jī)是 $S$ 起始狀態(tài) , 當(dāng)輸入 $a$ 時(shí) , 自動(dòng)機(jī)狀態(tài)變成 $q_1$ , 此后不管多少次輸入 $a$ , 一直處于 $q_1$ 狀態(tài) , 如果輸入 $b$ , 那么就會(huì)轉(zhuǎn)為 $q_2$ 狀態(tài) , 如果一直輸入 $b$ , 自動(dòng)機(jī)一直處于該非接受狀態(tài) $q_2$ , 如果輸入 $a$ , 又回到接受狀態(tài) $q_1$ ;

② 左側(cè)分支分析總結(jié) : 左側(cè)分支 , 主要接受 以 $a$ 開(kāi)頭 , 以 $a$ 結(jié)尾的字符串 , 最后才能進(jìn)入接受狀態(tài) ;

3 . 自動(dòng)機(jī) 右側(cè)分支分析 :

① 執(zhí)行流程 : 開(kāi)始時(shí) , 自動(dòng)機(jī)是 $S$ 起始狀態(tài) , 當(dāng)輸入 $b$ 時(shí) , 自動(dòng)機(jī)狀態(tài)變成 $r_1$ , 此后不管多少次輸入 $b$ , 一直處于 $r_1$ 狀態(tài) , 如果此時(shí)輸入 $a$ , 那么就會(huì)轉(zhuǎn)為 $r_2$ 狀態(tài) , 此時(shí)如果一直輸入 $a$ , 自動(dòng)機(jī)一直處于該非接受狀態(tài) $r_2$ , 如果輸入 $b$ , 又回到接受狀態(tài) $r_1$ ;

② 右側(cè)分支分析總結(jié) : 右側(cè)分支 , 主要接受 以 $b$ 開(kāi)頭 , 以 $b$ 結(jié)尾的字符串 , 最后才能進(jìn)入接受狀態(tài) ;

4 . 自動(dòng)機(jī) 總體分析 : 自動(dòng)機(jī) $M$ 接受相同開(kāi)頭 和 相同結(jié)尾的 字符串 ;

5 . 接受狀態(tài) 與 非接受狀態(tài) : 只在計(jì)算結(jié)束以后才開(kāi)始起作用 ;

① 計(jì)算過(guò)程 : 在計(jì)算過(guò)程中 , 這兩個(gè)狀態(tài)沒(méi)有區(qū)別 , 可以任意轉(zhuǎn)換 ;

② 最終狀態(tài) : 自動(dòng)機(jī)的 最終的狀態(tài) , 必須判定失接受狀態(tài) 還是 非接受狀態(tài) , 如果是非接受狀態(tài) , 說(shuō)明輸入不對(duì) , 自動(dòng)機(jī)拒絕該輸入 ;

總結(jié)

以上是生活随笔為你收集整理的【计算理论】确定性有穷自动机 ( 自动机组成 | 自动机语言 | 自动机等价 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。