文章目錄

• 一、上下文無關(guān)文法 CFG 轉(zhuǎn)為下推自動(dòng)機(jī) PDA 流程
• 二、上下文無關(guān)文法 CFG 轉(zhuǎn)為下推自動(dòng)機(jī) PDA 示例 2

參考博客 :

• 【計(jì)算理論】上下文無關(guān)語法 ( 語法組成 | 規(guī)則 | 語法 | 語法示例 | 約定的簡寫形式 | 語法分析樹 )
• 【計(jì)算理論】上下文無關(guān)語法 ( 代數(shù)表達(dá)式 | 代數(shù)表達(dá)式示例 | 確定性有限自動(dòng)機(jī) DFA 轉(zhuǎn)為 上下文無關(guān)語法 )
• 【計(jì)算理論】上下文無關(guān)語法 CFG ( CFG 設(shè)計(jì)示例 | CFG 歧義性 | Chomsky 范式 | 上下文無關(guān)語法 轉(zhuǎn)為 Chomsky 范式 )
• 【計(jì)算理論】下推自動(dòng)機(jī) PDA 及 計(jì)算示例
• 【計(jì)算理論】下推自動(dòng)機(jī) PDA ( 設(shè)計(jì)下推自動(dòng)機(jī) | 上下文無關(guān)語法 CFG 等價(jià)于 下推自動(dòng)機(jī) PDA )
• 【計(jì)算理論】上下文無關(guān)語法 ( CFG ) 轉(zhuǎn)為 下推自動(dòng)機(jī) ( PDA )
• 【計(jì)算理論】下推自動(dòng)機(jī) PDA ( 上下文無關(guān)語言 CFL 的 泵引理 | 泵引理反證示例 | 自動(dòng)機(jī)擴(kuò)展 )

一、上下文無關(guān)文法 CFG 轉(zhuǎn)為下推自動(dòng)機(jī) PDA 流程

---

上下文無關(guān)文法 CFG 轉(zhuǎn)為下推自動(dòng)機(jī) PDA 流程 :

① 開始狀態(tài) : 開始狀態(tài) ${\mathrm{q}}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}$ , 跳轉(zhuǎn)到 ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 狀態(tài)的指令 $\epsilon ,\epsilon \to \mathrm{K}$ , 使用 $\mathrm{K}$ 替換棧內(nèi)空字符 $\epsilon$ , 即將 $\mathrm{K}$ 放入棧中 ;

② 循環(huán)狀態(tài) : ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 狀態(tài)的指令都是從本狀態(tài)指向本狀態(tài) , 生成兩種指令 , 一種是基本指令 , 一種是終端字符指令 ;

基本指令 $\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}|\mathrm{b}$ 生成為 $\epsilon ,\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}$ 和 $\epsilon ,\mathrm{S}\to \mathrm{b}$ 兩條指令 , 前面都是讀取空字符作為棧讀取的信息 ;

終端字符指令 , 如果存在終端字符 $\mathrm{a}$ 和 $\mathrm{b}$ , 那么生成 $\mathrm{a},\mathrm{a}\to \epsilon$ 和 $\mathrm{b},\mathrm{b}\to \epsilon$ 兩條指令 , 含義是讀取棧頂 $\mathrm{a}$ 字符 , 將該字符使用空字符替代 , 即從棧中刪除該字符 ;

③ 接受狀態(tài) : ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 狀態(tài)跳轉(zhuǎn)到 ${\mathrm{q}}_{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}}$ 指令是 $\epsilon ,\mathrm{K}\to \epsilon$ , 棧頂讀取到 $\mathrm{K}$ 字符刪除 ;

④ 拆分指令 : 在循環(huán)狀態(tài) ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 中的基本指令中存在多字符指令 , 如 $\epsilon ,\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}$ , 讀取到空字符 $\epsilon$ , 使用 $\mathrm{a}\mathrm{T}\mathrm{b}$ 字符替換棧頂?shù)?$\mathrm{S}$ 字符 , 這是 $3$ 個(gè)字符 , 肯定不行 , 需要逐個(gè)放進(jìn)去 , 先放 $\mathrm{b}$ , 再放 $\mathrm{T}$ , 最后放 $\mathrm{a}$ ;

最終分解為
$\epsilon ,\mathrm{S}\to \mathrm{b}$ 讀取空字符放入 $\mathrm{b}$ 到棧頂 ,
$\epsilon ,\epsilon \to \mathrm{T}$ 讀取空字符放入 $\mathrm{T}$ 到棧頂 ,
$\epsilon ,\epsilon \to \mathrm{a}$ 讀取空字符放入 $\mathrm{a}$ 到棧頂 ;

二、上下文無關(guān)文法 CFG 轉(zhuǎn)為下推自動(dòng)機(jī) PDA 示例 2

---

將上下文無關(guān)語法 ( CFG ) 轉(zhuǎn)為下推自動(dòng)機(jī) ( PDA ) :

$\mathrm{R}\to \mathrm{X}\mathrm{R}\mathrm{X}|\mathrm{S}$
$\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}|\mathrm{b}\mathrm{T}\mathrm{a}$
$\mathrm{T}\to \mathrm{X}\mathrm{T}\mathrm{X}|\mathrm{X}|\epsilon$
$\mathrm{X}\to \mathrm{a}|\mathrm{b}$

上下文無關(guān)文法 CFG 轉(zhuǎn)為下推自動(dòng)機(jī) PDA 流程 :

① 開始狀態(tài) : 開始狀態(tài) ${\mathrm{q}}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}$ , 跳轉(zhuǎn)到 ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 狀態(tài)的指令 $\epsilon ,\epsilon \to \mathrm{K}$ , 使用 $\mathrm{K}$ 替換棧內(nèi)空字符 $\epsilon$ , 即將 $\mathrm{K}$ 放入棧中 ;

② 循環(huán)狀態(tài) : ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 狀態(tài)的指令都是從本狀態(tài)指向本狀態(tài) , 生成兩種指令 , 一種是基本指令 , 一種是終端字符指令 ;

基本指令 $\mathrm{R}\to \mathrm{X}\mathrm{R}\mathrm{X}|\mathrm{S}$ 生成為 : $\epsilon ,\mathrm{R}\to \mathrm{X}\mathrm{R}\mathrm{X}$ 和 $\epsilon ,\mathrm{R}\to \mathrm{S}$ 兩條指令 , 前面都是讀取空字符作為棧讀取的信息 ;

基本指令 $\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}|\mathrm{b}\mathrm{T}\mathrm{a}$ 生成為 : $\epsilon ,\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}$ 和 $\epsilon ,\mathrm{S}\to \mathrm{b}\mathrm{T}\mathrm{a}$ 兩條指令 , 前面都是讀取空字符作為棧讀取的信息 ;

基本指令 $\mathrm{T}\to \mathrm{X}\mathrm{T}\mathrm{X}|\mathrm{X}|\epsilon$ 生成為 : $\epsilon ,\mathrm{T}\to \mathrm{X}\mathrm{T}\mathrm{X}$ , $\epsilon ,\mathrm{T}\to \mathrm{X}$ , $\epsilon ,\mathrm{T}\to \epsilon$ 三條指令 , 前面都是讀取空字符作為棧讀取的信息 ;

基本指令 $\mathrm{X}\to \mathrm{a}|\mathrm{b}$ 生成為 : $\epsilon ,\mathrm{X}\to \mathrm{a}$ 和 $\epsilon ,\mathrm{X}\to \mathrm{b}$ 兩條指令 , 前面都是讀取空字符作為棧讀取的信息 ;

終端字符指令 : 如果存在終端字符 $\mathrm{a}$ 和 $\mathrm{b}$ , 那么生成 $\mathrm{a},\mathrm{a}\to \epsilon$ 和 $\mathrm{b},\mathrm{b}\to \epsilon$ 兩條指令 , 含義是讀取棧頂 $\mathrm{a}$ 字符 , 將該字符使用空字符替代 , 即從棧中刪除該字符 ;

③ 接受狀態(tài) : ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 狀態(tài)跳轉(zhuǎn)到 ${\mathrm{q}}_{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{p}\mathrm{t}}$ 指令是 $\epsilon ,\mathrm{K}\to \epsilon$ , 棧頂讀取到 $\mathrm{K}$ 字符刪除 ;

④ 拆分指令 : 在循環(huán)狀態(tài) ${\mathrm{q}}_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ 中的基本指令中存在多字符指令 , 如 $\epsilon ,\mathrm{R}\to \mathrm{X}\mathrm{R}\mathrm{X}$ , 讀取到空字符 $\epsilon$ , 使用 $\mathrm{X}\mathrm{R}\mathrm{X}$ 字符替換棧頂?shù)?$\mathrm{R}$ 字符 , 這是 $3$ 個(gè)字符 , 肯定不行 , 需要逐個(gè)放進(jìn)去 , 先放 $\mathrm{X}$ ( 第三個(gè) ) , 再放 $\mathrm{R}$ , 最后放 $\mathrm{X}$ ( 第一個(gè) ) ;

$\epsilon ,\mathrm{R}\to \mathrm{X}\mathrm{R}\mathrm{X}$ 最終分解為 :
$\epsilon ,\mathrm{R}\to \mathrm{X}$ 讀取空字符后 , 使用 $\mathrm{X}$ 字符替換棧頂 $\mathrm{R}$ 字符 ,
$\epsilon ,\epsilon \to \mathrm{R}$ 讀取空字符后 , 將 $\mathrm{R}$ 字符放到到棧頂 ,
$\epsilon ,\epsilon \to \mathrm{X}$ 讀取空字符后 , 將 $\mathrm{X}$ 字符放到到棧頂 ;

$\epsilon ,\mathrm{S}\to \mathrm{a}\mathrm{T}\mathrm{b}$ 最終分解為 :
$\epsilon ,\mathrm{S}\to \mathrm{b}$ 讀取空字符后 , 使用 $\mathrm{b}$ 字符替換棧頂 $\mathrm{S}$ 字符 ,
$\epsilon ,\epsilon \to \mathrm{T}$ 讀取空字符后 , 將 $\mathrm{T}$ 字符放到到棧頂 ,
$\epsilon ,\epsilon \to \mathrm{a}$ 讀取空字符后 , 將 $\mathrm{a}$ 字符放到到棧頂 ;

$\epsilon ,\mathrm{S}\to \mathrm{b}\mathrm{T}\mathrm{a}$ 最終分解為 :
$\epsilon ,\mathrm{S}\to \mathrm{a}$ 讀取空字符后 , 使用 $\mathrm{a}$ 字符替換棧頂 $\mathrm{S}$ 字符 ,
$\epsilon ,\epsilon \to \mathrm{T}$ 讀取空字符后 , 將 $\mathrm{T}$ 字符放到到棧頂 ,
$\epsilon ,\epsilon \to \mathrm{b}$ 讀取空字符后 , 將 $\mathrm{b}$ 字符放到到棧頂 ;

$\epsilon ,\mathrm{T}\to \mathrm{X}\mathrm{T}\mathrm{X}$
$\epsilon ,\mathrm{T}\to \mathrm{X}$ 讀取空字符后 , 使用 $\mathrm{X}$ 字符替換棧頂 $\mathrm{T}$ 字符 ,
$\epsilon ,\epsilon \to \mathrm{T}$ 讀取空字符后 , 將 $\mathrm{T}$ 字符放到到棧頂 ,
$\epsilon ,\epsilon \to \mathrm{X}$ 讀取空字符后 , 將 $\mathrm{X}$ 字符放到到棧頂 ;

最終的下推自動(dòng)機(jī)樣式 :

總結(jié)

以上是生活随笔為你收集整理的【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 2 ) ★★的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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