跳到主要内容

下推自动机

阐述​

形式定义​

六元组 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) 是转换函数
  • q0∈Qq_0\in Q 是起始状态
  • F⊆QF\subseteq Q 是接受状态

运算过程：接受 ww，如果 w=w1w2⋯wmw=w_1w_2\cdots w_m，其中 wi∈Σεw_i\in\Sigma_\varepsilon，状态 r1,⋯ ,rm∈Qr_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
  • rm∈Fr_m\in F

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

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

阐释​

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

性质​

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

实例​

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

性质​

相关内容​

参考文献​