文章目錄

• 一、 下推自動(dòng)機(jī)
• 二、下推自動(dòng)機(jī) 計(jì)算過程
• 三、下推自動(dòng)機(jī) 計(jì)算結(jié)果
• 四、下推自動(dòng)機(jī) 計(jì)算示例

一、 下推自動(dòng)機(jī)

---

1 . 下推自動(dòng)機(jī) 由來 : 下推自動(dòng)機(jī) ( PDA ) 是在 確定性有限自動(dòng)機(jī) ( DFA ) 基礎(chǔ)上 擴(kuò)展而來的 ;

2 . 下面是 下推自動(dòng)機(jī) ( PDA ) 的示意圖 :

① 輸入字符串 : 將輸入的字符寫在右側(cè)的帶子上 ;

② 開始狀態(tài) : 讀取指針 ( 讀頭 ) 開始指向最左端字符 , 此時(shí)處于開始狀態(tài) ;

③ 啟動(dòng)自動(dòng)機(jī) , 自動(dòng)機(jī)根據(jù)讀取的指令進(jìn)行計(jì)算 ;

④ 讀取指令 : 每讀取一個(gè)字符 , 自動(dòng)機(jī)跳轉(zhuǎn)到一個(gè)新的狀態(tài) , 指針向后移動(dòng)一個(gè)格子 ;

⑤ 自動(dòng)機(jī)停止 : 當(dāng)讀取指針指向輸入的最右端 , 此時(shí)自動(dòng)機(jī)就停止了 , 此時(shí)查看當(dāng)前狀態(tài) , 如果當(dāng)前是接受狀態(tài) , 稱自動(dòng)機(jī)接受該字符串 ( 帶子上寫的字符組成的字符串 ) , 反之 , 自動(dòng)機(jī)不接受該字符串 ;

二、下推自動(dòng)機(jī) 計(jì)算過程

---

1 . 下推自動(dòng)機(jī) ( PDA ) 提升了自動(dòng)機(jī)計(jì)算能力 : 在上述自動(dòng)機(jī)的基礎(chǔ)上 , 提升該自動(dòng)機(jī)的計(jì)算能力 , 引入一個(gè)新的棧結(jié)構(gòu) ;

棧特點(diǎn) : ① 后進(jìn)先出 , ② 存儲(chǔ)能力無限 ;

2 . 下推自動(dòng)機(jī)計(jì)算有兩個(gè)部分 , 一個(gè)是字符的讀取 , 一個(gè)是棧內(nèi)字符的存取 , 棧內(nèi)只有最上面的字符會(huì)被替換 ;

3 . 下推自動(dòng)機(jī) ( PDA ) 的指令格式 : 該指令包含了 上述講的兩個(gè)操作 ;

$$1,0\to \epsilon$$

① 自動(dòng)機(jī)字符讀取 : 左側(cè)的 $1$ 是從帶子上讀取的字符 ;

② 棧內(nèi)字符存取操作 : $0\to \epsilon$ 是需要在棧上進(jìn)行的操作 , 將棧頂?shù)?$0$ 取出 , 然后將 $\epsilon$ 放入到棧中 , 相當(dāng)于在棧中 , 使用 $\epsilon$ 將棧頂?shù)?$0$ 替換掉 ;

三、下推自動(dòng)機(jī) 計(jì)算結(jié)果

---

1 . 下推自動(dòng)機(jī) ( PDA ) 是否接受字符串 : 將帶子上的字符全部讀取完畢后 , 此時(shí)的狀態(tài)如果是 接受狀態(tài) , 那么帶子上的字符組成的字符串就可以被 下推自動(dòng)機(jī)接受 ;

2 . 計(jì)算能力 : 下推自動(dòng)機(jī) ( PDA ) 比 確定性有限自動(dòng)機(jī) ( DFA ) 多了棧上的操作 , 下推自動(dòng)機(jī) ( PDA ) 的計(jì)算能力比有限自動(dòng)機(jī) ( DFA ) 計(jì)算能力高 ;

3 . 語(yǔ)言識(shí)別能力 : 確定性有限自動(dòng)機(jī) ( DFA ) 是不能識(shí)別 $\{0^n{1}^n:n\ge 0\}$ 語(yǔ)言的 , 但是 下推自動(dòng)機(jī) ( PDA ) 是可以認(rèn)識(shí)該語(yǔ)言的 ;

四、下推自動(dòng)機(jī) 計(jì)算示例

---

上圖的下推自動(dòng)機(jī)有 $4$ 個(gè)狀態(tài) $q_1,q_2,q_3,q_4$ ;

讀取 $0011$ 字符串 , 并給出 下推自動(dòng)機(jī) 計(jì)算過程 ;

$\epsilon ,\epsilon \to S$ 指令含義 : 當(dāng)讀取 $\epsilon$ 字符后 , $\epsilon \to S$ 指的是在棧上的操作 , 從棧內(nèi)取出 $\epsilon$ 字符 , 向棧內(nèi)放入一個(gè) $S$ 字符 , 本質(zhì)是在棧中使用 $S$ 替換 $\epsilon$ 字符 ;

1 . 開始狀態(tài) 是 $q_1$ , 此時(shí)讀頭指向 $0$ 位置 , 棧內(nèi)是空的 ;

2 . 開始狀態(tài) $q_1$ : 讀取 $\epsilon ,\epsilon \to S$ 指令 , 讀取 $\epsilon$ 字符后 , $\epsilon \to S$ 指的是在棧上的操作 , 從棧內(nèi)拿走 $\epsilon$ , $\epsilon$ 是空字符 , 相當(dāng)于不用拿 , 并將 $S$ 字符放入棧 , 相當(dāng)于使用 $S$ 替換 棧內(nèi) 空字符 $\epsilon$ ,

$S$ 字符的作用 : 下推自動(dòng)機(jī)是無法識(shí)別棧底的 , $S$ 作用是輔助下推自動(dòng)機(jī)識(shí)別棧底元素 , 當(dāng)下推自動(dòng)機(jī)讀取到 $S$ 時(shí) , 就知道已經(jīng)讀取到棧底了 ;

開始狀態(tài) 讀取字符 操作 $\epsilon ,\epsilon \to S$ , 最終向棧中放入了字符 $S$ ;

狀態(tài)跳轉(zhuǎn) : 此時(shí) 自動(dòng)機(jī)狀態(tài) 跳轉(zhuǎn)到了 $q_2$ 狀態(tài) ;

3 . $q_2$ 狀態(tài) : 讀取 $0,\epsilon \to 0$ 指令 , 讀取到一個(gè) $0$ , 從棧內(nèi)拿走 $\epsilon$ , 使用 $0$ 替換 $\epsilon$ , 并將該替換后的 $0$ 放入棧中 ; 相當(dāng)于在棧中 , 使用 $0$ 替換 $\epsilon$ ; 之后依然保持 $q_2$ 狀態(tài)不變 ;

狀態(tài)跳轉(zhuǎn) : 下推自動(dòng)機(jī)狀態(tài) 仍保持 $q_2$ 狀態(tài) ;

4 . $q_2$ 狀態(tài) : 再次讀取 $0,\epsilon \to 0$ 指令 , 讀取到一個(gè) $0$ , 從棧內(nèi)拿走 $0$ 字符 , 使用 $0$ 替換 $\epsilon$ , 并將該替換后的 $0$ 放入棧中 ; 之后依然保持 $q_2$ 狀態(tài)不變 ;

狀態(tài)跳轉(zhuǎn) : 下推自動(dòng)機(jī)狀態(tài) 仍保持 $q_2$ 狀態(tài) ;

5 . $q_2$ 狀態(tài) , 讀取 $1,0\to \epsilon$ 指令 , 讀取到一個(gè) $1$ , 從棧中拿走一個(gè) $0$ , 并將 $\epsilon$ 放入棧中 , $\epsilon$ 是空字符串 , 從棧內(nèi)拿取放入 $\epsilon$ 棧不變 , 相當(dāng)于將一個(gè) $0$ 從棧內(nèi)拿出 ;

狀態(tài)跳轉(zhuǎn) : 下推自動(dòng)機(jī)狀態(tài) 從 $q_2$ 狀態(tài)跳轉(zhuǎn)到 $q_3$ 狀態(tài) ;

6 . $q_3$ 狀態(tài) : 讀取 $1,0\to \epsilon$ 指令 , 從棧中 , 拿走一個(gè) $0$ , 將 $\epsilon$ 放入棧內(nèi) , 相當(dāng)于在棧內(nèi)使用 $\epsilon$ 空字符 替換 $0$ , 操作完成后 , 棧內(nèi)少一個(gè) $0$ ;

狀態(tài)跳轉(zhuǎn) : 下推自動(dòng)機(jī)狀態(tài) 仍保持 $q_3$ 狀態(tài) ;

7 . $q_3$ 狀態(tài) , 讀頭讀取到了最右端 , 所有字符都讀取完畢 , 此時(shí)不需要讀取任何字符 , 讀取 $\epsilon ,S\to \epsilon$ 指令 , 從棧內(nèi)拿走 $S$ , 將 $\epsilon$ 放入棧中 , 跳轉(zhuǎn)到 $q_4$ 狀態(tài) ;

此時(shí) , 棧清空 , 下推自動(dòng)機(jī)停止計(jì)算 ;

$q_4$ 是個(gè)雙圈 , 接受狀態(tài) , 說明該下推自動(dòng)機(jī)接受該 $0011$ 字符串 ;

總結(jié)

以上是生活随笔為你收集整理的【计算理论】下推自动机 PDA 及 计算示例的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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