II . 上下文无关语法 ( CFG ) 等价于 下推自动机 ( PDA )
假设某语言由 上下文无关语法 ( CFG ) 生成 , 找到一个 下推自动机 ( PDA ) 识别该语言 ;
构造下推自动机流程 ( PDA ) :
构造下推自动机 , 包含 3 33 个状态 , 开始状态 q s t a r t q_{start}q
start
, Loop 循环状态 q l o o p q_{loop}q
loop
, 可接受状态 q a c c e p t q_{accept}q
accept
;
1 . q s t a r t q_{start}q
start
开始状态 :
读取 ε \varepsilonε 字符 , 使用 T S TSTS 替换栈顶的 ε \varepsilonε , 对应的指令为
ε , ε → T S \varepsilon , \varepsilon \to TS
ε,ε→TS
其中的 S SS 是栈顶的标识 , T TT 是栈内的实际字符 ;
2 . q l o o p q_{loop}q
loop
循环阶段 , 根据 上下文无关语法 ( CFG ) 做替换 ;
① 当栈顶是变元时 , 作变换 , 读取 ε \varepsilonε , 即什么都不读取 , 将栈顶的变元 替换成 w ww , 生成的 下推自动机 指令为 " ε , A → w \varepsilon , A \to wε,A→w " , 对应着的上下文无关语法规则为 A → w A \to wA→w ;
② 当栈顶是终端字符 ( 常元 ) , 让带子上的 读头 读取一个终端字符 , 对应的栈中 , 将栈顶的终端字符删除 , 相当于使用 ε \varepsilonε 替换终端字符 , 生成指令 " a , a → ε a , a \to \varepsilona,a→ε " ;
一直读取 终端字符 , 并将栈顶的终端字符删除 , 一直循环该操作 , 直到 栈顶是一个变元 未为止 ;
3 . 跳转到 q a c c e p t q_{accept}q
accept
状态 : 当栈内的字符都出栈后 , 只剩下一个 S SS 字符作为栈底标识 , 此时 S SS 出栈 , 生成对应的 下推自动机指令 " ε , S → ε \varepsilon , S \to \varepsilonε,S→ε " , 即使用空字符 ε \varepsilonε 替换栈内的 S SS 字符 ;
之后跳转到最后一个状态 , q a c c e p t q_{accept}q
accept
可接受状态 ;
