跳到主要内容

下推自动机

阐述

形式定义

六元组 M=(Q,Σ,Γ,δ,q0,F)M=(Q,\Sigma,\Gamma,\delta,q_0,F),其中

  • QQ 是状态的有限集
  • Σ\Sigma 是输入的字母表
  • Γ\Gamma 是栈的字母表
  • δ:Q×Σε×ΓεP(Q×Γε)\delta:Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon\to\mathcal P(Q\times\Gamma_\varepsilon) 是转换函数
  • q0Qq_0\in Q 是起始状态
  • FQF\subseteq Q 是接受状态

运算过程:接受 ww,如果 w=w1w2wmw=w_1w_2\cdots w_m,其中 wiΣεw_i\in\Sigma_\varepsilon,状态 r1,,rmQr_1,\cdots,r_m\in Q,字符串 s0,,smΓs_0,\cdots,s_m\in\Gamma^* 满足

  • r0=q0,s0=εr_0=q_0,s_0=\varepsilon
  • (ri+1,b)δ(ri,wi+1,a)(r_{i+1},b)\in\delta(r_i,w_{i+1},a),其中 si=at,si+1=bts_i=at,s_{i+1}=bt 对于某些 a,bΓεa,b\in\Gamma_\varepsilon
  • rmFr_m\in F

在图上,a,bca,b\to c 意味着读取 aa,并且将栈顶的 bb 替换为 cc。它们都可以是 ε\varepsilon

  • a=εa=\varepsilon 意味着不需要读取即可行动
  • b=εb=\varepsilon 意味着不需要从栈顶弹出
  • c=εc=\varepsilon 意味着不需要向栈顶压入

阐释

下推自动机具有无限的内存,但是只能对栈的顶端进行弹出和压入操作。

性质

下推自动机与上下文无关文法等价。

实例

这个 PDA 可以识别语言 {0n1nn0}\{0^n1^n|n\ge0\}:

性质

相关内容

参考文献