文章目录
一、上下文无关文法 CFG 转为下推自动机 PDA 流程
二、上下文无关文法 CFG 转为下推自动机 PDA 示例 2
参考博客 :
【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )
【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )
【计算理论】上下文无关语法 CFG ( CFG 设计示例 | CFG 歧义性 | Chomsky 范式 | 上下文无关语法 转为 Chomsky 范式 )
【计算理论】下推自动机 PDA 及 计算示例
【计算理论】下推自动机 PDA ( 设计下推自动机 | 上下文无关语法 CFG 等价于 下推自动机 PDA )
【计算理论】上下文无关语法 ( CFG ) 转为 下推自动机 ( PDA )
【计算理论】下推自动机 PDA ( 上下文无关语言 CFL 的 泵引理 | 泵引理反证示例 | 自动机扩展 )
一、上下文无关文法 CFG 转为下推自动机 PDA 流程
上下文无关文法 CFG 转为下推自动机 PDA 流程 :
① 开始状态 : 开始状态 q s t a r t \rm q_{start}q
start
, 跳转到 q l o o p \rm q_{loop}q
loop
状态的指令 ε , ε → K \rm \varepsilon , \varepsilon \to Kε,ε→K , 使用 K \rm KK 替换栈内空字符 ε \varepsilonε , 即将 K \rm KK 放入栈中 ;
② 循环状态 : q l o o p \rm q_{loop}q
loop
状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;
基本指令 S → a T b ∣ b \rm S \to aTb|bS→aTb∣b 生成为 ε , S → a T b \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 字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;
③ 接受状态 : q l o o p \rm q_{loop}q
loop
状态跳转到 q a c c e p t \rm q_{accept}q
accept
指令是 ε , K → ε \rm \varepsilon , K \to \varepsilonε,K→ε , 栈顶读取到 K \rm KK 字符删除 ;
④ 拆分指令 : 在循环状态 q l o o p \rm q_{loop}q
loop
中的基本指令中存在多字符指令 , 如 ε , S → a T b \rm \varepsilon , S \to aTbε,S→aTb , 读取到空字符 ε \varepsilonε , 使用 a T b \rm aTbaTb 字符替换栈顶的 S \rm SS 字符 , 这是 3 33 个字符 , 肯定不行 , 需要逐个放进去 , 先放 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 示例 2
将上下文无关语法 ( CFG ) 转为下推自动机 ( PDA ) :
R → X R X ∣ S \rm R \to XRX | SR→XRX∣S
S → a T b ∣ b T a \rm S \to aTb | bTaS→aTb∣bTa
T → X T X ∣ X ∣ ε \rm T \to XTX | X |\varepsilonT→XTX∣X∣ε
X → a ∣ b \rm X \to a | bX→a∣b
上下文无关文法 CFG 转为下推自动机 PDA 流程 :
① 开始状态 : 开始状态 q s t a r t \rm q_{start}q
start
, 跳转到 q l o o p \rm q_{loop}q
loop
状态的指令 ε , ε → K \rm \varepsilon , \varepsilon \to Kε,ε→K , 使用 K \rm KK 替换栈内空字符 ε \varepsilonε , 即将 K \rm KK 放入栈中 ;
② 循环状态 : q l o o p \rm q_{loop}q
loop
状态的指令都是从本状态指向本状态 , 生成两种指令 , 一种是基本指令 , 一种是终端字符指令 ;
基本指令 R → X R X ∣ S \rm R \to XRX | SR→XRX∣S 生成为 : ε , R → X R X \rm \varepsilon , R \to XRXε,R→XRX 和 ε , R → S \rm \varepsilon , R \to Sε,R→S 两条指令 , 前面都是读取空字符作为栈读取的信息 ;
基本指令 S → a T b ∣ b T a \rm S \to aTb | bTaS→aTb∣bTa 生成为 : ε , S → a T b \rm \varepsilon , S \to aTbε,S→aTb 和 ε , S → b T a \rm \varepsilon , S \to bTaε,S→bTa 两条指令 , 前面都是读取空字符作为栈读取的信息 ;
基本指令 T → X T X ∣ X ∣ ε \rm T \to XTX | X |\varepsilonT→XTX∣X∣ε 生成为 : ε , T → X T X \rm \varepsilon , T \to XTXε,T→XTX , ε , T → X \rm \varepsilon , T \to Xε,T→X , ε , T → ε \rm \varepsilon , T \to \varepsilonε,T→ε 三条指令 , 前面都是读取空字符作为栈读取的信息 ;
基本指令 X → a ∣ b \rm X \to a | bX→a∣b 生成为 : ε , X → a \rm \varepsilon , X \to aε,X→a 和 ε , X → b \rm \varepsilon , X \to bε,X→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 字符 , 将该字符使用空字符替代 , 即从栈中删除该字符 ;
③ 接受状态 : q l o o p \rm q_{loop}q
loop
状态跳转到 q a c c e p t \rm q_{accept}q
accept
指令是 ε , K → ε \rm \varepsilon , K \to \varepsilonε,K→ε , 栈顶读取到 K \rm KK 字符删除 ;
④ 拆分指令 : 在循环状态 q l o o p \rm q_{loop}q
loop
中的基本指令中存在多字符指令 , 如 ε , R → X R X \rm \varepsilon , R \to XRXε,R→XRX , 读取到空字符 ε \varepsilonε , 使用 X R X \rm XRXXRX 字符替换栈顶的 R \rm RR 字符 , 这是 3 33 个字符 , 肯定不行 , 需要逐个放进去 , 先放 X \rm XX ( 第三个 ) , 再放 R \rm RR , 最后放 X \rm XX ( 第一个 ) ;
ε , R → X R X \rm \varepsilon , R \to XRXε,R→XRX 最终分解为 :
ε , R → X \rm \varepsilon , R \to Xε,R→X 读取空字符后 , 使用 X \rm XX 字符替换栈顶 R \rm RR 字符 ,
ε , ε → R \rm \varepsilon , \varepsilon \to Rε,ε→R 读取空字符后 , 将 R \rm RR 字符放到到栈顶 ,
ε , ε → X \rm \varepsilon , \varepsilon \to Xε,ε→X 读取空字符后 , 将 X \rm XX 字符放到到栈顶 ;
ε , S → a T b \rm \varepsilon , S \to aTbε,S→aTb 最终分解为 :
ε , S → b \rm \varepsilon , S \to bε,S→b 读取空字符后 , 使用 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 字符放到到栈顶 ;
ε , S → b T a \rm \varepsilon , S \to bTaε,S→bTa 最终分解为 :
ε , S → a \rm \varepsilon , S \to aε,S→a 读取空字符后 , 使用 a \rm aa 字符替换栈顶 S \rm SS 字符 ,
ε , ε → T \rm \varepsilon , \varepsilon \to Tε,ε→T 读取空字符后 , 将 T \rm TT 字符放到到栈顶 ,
ε , ε → b \rm \varepsilon , \varepsilon \to bε,ε→b 读取空字符后 , 将 b \rm bb 字符放到到栈顶 ;
ε , T → X T X \rm \varepsilon , T \to XTXε,T→XTX
ε , T → X \rm \varepsilon , T \to Xε,T→X 读取空字符后 , 使用 X \rm XX 字符替换栈顶 T \rm TT 字符 ,
ε , ε → T \rm \varepsilon , \varepsilon \to Tε,ε→T 读取空字符后 , 将 T \rm TT 字符放到到栈顶 ,
ε , ε → X \rm \varepsilon , \varepsilon \to Xε,ε→X 读取空字符后 , 将 X \rm XX 字符放到到栈顶 ;
最终的下推自动机样式 :
