确定型下推自动机

定义

定义:如果PDA \(P = (Q, Σ, Γ, δ, q_0,Z_0,F)\) 满足

1. \(∀a ∈ Σ ∪ {ε}, δ(q, a, X)\) 至多有一个动作
2. \(∀a ∈ Σ\), 如果 \(δ(q, a, X)  ≠ ∅\), 那么 \(δ(q, ε, X) = ∅\)。

则称P为确定型下推自动机(DPDA)，在任何情况下都不需要去选择可能的移动就是DPDA，DPDA与PDA识别语言的能力不一样，是不等价的。

例：任何的DPDA都无法接受\(L_{wwr}\)，但是可以接受\(L_{wcwr}=\{wxw^R|w\in (0+1)^*\}\)

DPDA需要一个“标志”c来确定是否读取完第一个\(w\)部分

例：构造一个DPDA，使其接受语言\(\{0^n1^{n+2}|n≥0\}\)

确定的上下文无关语言DFCL

DPDA以终态方式接受的语言也称为DCFL

• 非固有歧义语言的真子集
• Knuth提出\(LR(k)\)文法的语言也恰好是DPDA接受语言的一个子集, 解析的时间复杂度为\(O(n)\)

定理

如果 \(L\) 是正则语言, 那么存在DPDA \(P\) 以终态方式接受L, 即\(L = \text{L}(P)\)