【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★
文章目錄
- 一、上下文無關文法 CFG 轉為下推自動機 PDA 流程
- 二、上下文無關文法 CFG 轉為下推自動機 PDA 示例 1
參考博客 :
- 【計算理論】上下文無關語法 ( 語法組成 | 規則 | 語法 | 語法示例 | 約定的簡寫形式 | 語法分析樹 )
- 【計算理論】上下文無關語法 ( 代數表達式 | 代數表達式示例 | 確定性有限自動機 DFA 轉為 上下文無關語法 )
- 【計算理論】上下文無關語法 CFG ( CFG 設計示例 | CFG 歧義性 | Chomsky 范式 | 上下文無關語法 轉為 Chomsky 范式 )
- 【計算理論】下推自動機 PDA 及 計算示例
- 【計算理論】下推自動機 PDA ( 設計下推自動機 | 上下文無關語法 CFG 等價于 下推自動機 PDA )
- 【計算理論】上下文無關語法 ( CFG ) 轉為 下推自動機 ( PDA )
- 【計算理論】下推自動機 PDA ( 上下文無關語言 CFL 的 泵引理 | 泵引理反證示例 | 自動機擴展 )
一、上下文無關文法 CFG 轉為下推自動機 PDA 流程
上下文無關文法 CFG 轉為下推自動機 PDA 流程 :
① 開始狀態 : 開始狀態 qstart\rm q_{start}qstart? , 跳轉到 qloop\rm q_{loop}qloop? 狀態的指令 ε,ε→K\rm \varepsilon , \varepsilon \to Kε,ε→K , 使用 K\rm KK 替換棧內空字符 ε\varepsilonε , 即將 K\rm KK 放入棧中 ;
② 循環狀態 : qloop\rm q_{loop}qloop? 狀態的指令都是從本狀態指向本狀態 , 生成兩種指令 , 一種是基本指令 , 一種是終端字符指令 ;
基本指令 S→aTb∣b\rm S \to aTb|bS→aTb∣b 生成為 ε,S→aTb\rm \varepsilon , S \to aTbε,S→aTb 和 ε,S→b\rm \varepsilon , S \to bε,S→b 兩條指令 , 前面都是讀取空字符作為棧讀取的信息 ;
終端字符指令 , 如果存在終端字符 a\rm aa 和 b\rm bb , 那么生成 a,a→ε\rm a, a \to \varepsilona,a→ε 和 b,b→ε\rm b, b \to \varepsilonb,b→ε 兩條指令 , 含義是讀取棧頂 a\rm aa 字符 , 將該字符使用空字符替代 , 即從棧中刪除該字符 ;
③ 接受狀態 : qloop\rm q_{loop}qloop? 狀態跳轉到 qaccept\rm q_{accept}qaccept? 指令是 ε,K→ε\rm \varepsilon , K \to \varepsilonε,K→ε , 棧頂讀取到 K\rm KK 字符刪除 ;
④ 拆分指令 : 在循環狀態 qloop\rm q_{loop}qloop? 中的基本指令中存在多字符指令 , 如 ε,S→aTb\rm \varepsilon , S \to aTbε,S→aTb , S\rm SS 讀取到空字符 ε\varepsilonε , 使用 aTb\rm aTbaTb 字符替換棧頂的 S\rm SS 字符 , 這是 333 個字符 , 肯定不行 , 需要逐個放進去 , 先放 b\rm bb , 再放 T\rm TT , 最后放 a\rm aa ;
最終分解為
ε,S→b\rm \varepsilon , S \to bε,S→b 讀取空字符放入 b\rm bb 到棧頂 ,
ε,ε→T\rm \varepsilon , \varepsilon \to Tε,ε→T 讀取空字符放入 T\rm TT 到棧頂 ,
ε,ε→a\rm \varepsilon , \varepsilon \to aε,ε→a 讀取空字符放入 a\rm aa 到棧頂 ;
二、上下文無關文法 CFG 轉為下推自動機 PDA 示例 1
將上下文無關語法 ( CFG ) 轉為下推自動機 ( PDA ) :
S→aTb∣b\rm S \to aTb | bS→aTb∣b
T→Ta∣ε\rm T \to Ta|\varepsilonT→Ta∣ε
上下文無關文法 CFG 轉為下推自動機 PDA 流程 :
① 開始狀態 : 開始狀態 qstart\rm q_{start}qstart? , 跳轉到 qloop\rm q_{loop}qloop? 狀態的指令 ε,ε→K\rm \varepsilon , \varepsilon \to Kε,ε→K , 使用 K\rm KK 替換棧內空字符 ε\varepsilonε , 即將 K\rm KK 放入棧中 ;
② 循環狀態 : qloop\rm q_{loop}qloop? 狀態的指令都是從本狀態指向本狀態 , 生成兩種指令 , 一種是基本指令 , 一種是終端字符指令 ;
基本指令 S→aTb∣b\rm S \to aTb|bS→aTb∣b 生成為 ε,S→aTb\rm \varepsilon , S \to aTbε,S→aTb 和 ε,S→b\rm \varepsilon , S \to bε,S→b 兩條指令 , 前面都是讀取空字符作為棧讀取的信息 ;
基本指令 T→Ta∣ε\rm T \to Ta|\varepsilonT→Ta∣ε 生成為 ε,T→Ta\rm \varepsilon , T \to Taε,T→Ta 和 ε,T→ε\rm \varepsilon , T \to \varepsilonε,T→ε 兩條指令 , 前面都是讀取空字符作為棧讀取的信息 ;
終端字符指令 , 如果存在終端字符 a\rm aa 和 b\rm bb , 那么生成 a,a→ε\rm a, a \to \varepsilona,a→ε 和 b,b→ε\rm b, b \to \varepsilonb,b→ε 兩條指令 , 含義是讀取棧頂 a\rm aa 字符 , 將該字符使用空字符替代 , 即從棧中刪除該字符 ;
③ 接受狀態 : qloop\rm q_{loop}qloop? 狀態跳轉到 qaccept\rm q_{accept}qaccept? 指令是 ε,K→ε\rm \varepsilon , K \to \varepsilonε,K→ε , 棧頂讀取到 K\rm KK 字符刪除 ;
④ 拆分指令 : 在循環狀態 qloop\rm q_{loop}qloop? 中的基本指令中存在多字符指令 , 如 ε,S→aTb\rm \varepsilon , S \to aTbε,S→aTb , S\rm SS 讀取到空字符 ε\varepsilonε , 使用 aTb\rm aTbaTb 字符替換棧頂的 S\rm SS 字符 , 這是 333 個字符 , 肯定不行 , 需要逐個放進去 , 先放 b\rm bb , 再放 T\rm TT , 最后放 a\rm aa ;
ε,S→aTb\rm \varepsilon , S \to aTbε,S→aTb 最終分解為 :
ε,S→b\rm \varepsilon , S \to bε,S→b 讀取 S\rm SS 字符放入 b\rm bb 到棧頂替換 S\rm SS 字符 ,
ε,ε→T\rm \varepsilon , \varepsilon \to Tε,ε→T 讀取空字符放入 T\rm TT 到棧頂 ,
ε,ε→a\rm \varepsilon , \varepsilon \to aε,ε→a 讀取空字符放入 a\rm aa 到棧頂 ;
ε,T→Ta\rm \varepsilon , T \to Taε,T→Ta 最終分解為 :
ε,T→a\rm \varepsilon , T \to aε,T→a , 讀取 T\rm TT 字符放入 a\rm aa 到棧頂替換 T\rm TT 字符 ,
ε,ε→T\rm \varepsilon , \varepsilon \to Tε,ε→T , 讀取空字符放入 T\rm TT 到棧頂 ;
最終的下推自動機樣式
總結
以上是生活随笔為你收集整理的【计算理论】计算理论总结 ( 上下文无关文法 CFG 转为下推自动机 PDA 示例 1 ) ★★的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【计算理论】计算理论总结 ( 下推自动机
- 下一篇： 【计算理论】计算理论总结 ( 上下文无关