7.3.1. 确定的下推自动机¶

定义（Definition）： 一个 PDA \(M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)\) 是 确定性的（deterministic） ，如果对每一个 \(q \in Q\)、\(a \in \Sigma \cup \{\lambda\}\)、\(b \in \Gamma\)：

1. \(\delta(q, a, b)\) 至多包含一个元素

2. 如果 \(\delta(q, \lambda, b)\) 非空，则必须对每一个 \(c \in \Sigma\) 都有 \(\delta(q, c, b)\) 为空。

定义（Definition）： \(L\) 是 确定的上下文无关语言（deterministic context-free language） （DCFL），当且仅当存在一个确定性的 PDA \(M\) ，使得 \(L = L(M)\) 。

示例（Example）

语言 \(L = \{a^nb^n | n \ge 0\}\) 是确定的 CFL。

接受上述语言。它满足确定性的条件。

注意，这台机器确实 有 \(\lambda\) 转移。关键在于，仍然只有一个选择（这是由栈顶是什么决定的）。从这个意义上说，它并不仅仅是一条"免费搭车"（free ride）的转移。

示例（Example）

我们之前用于 \(\{ww^R | w\in{\Sigma}^{+}\}, \Sigma = \{a, b\}\) 的 PDA 是非确定性的。

这违反了确定性的条件。（你知道为什么吗？）

现在，我们的 PDA 不是确定性的这一事实，当然 并不能 证明 \(\{ww^R | w\in{\Sigma}^{+}\}, \Sigma = \{a, b\}\) 不是确定的 CFL。

但是，确实存在不是确定性的 CFL。我们将会看到，其中之一就是它。这是符合直觉的。当从左到右扫描输入时，我们怎么能确定性地知道何时从 \(w\) 切换到 \(w^R\) 呢？

示例（Example）：

\(L = \{a^nb^n|n \ge 1\} \cup \{a^nb^{2n}| n\ge 1\}\) 是 CFL ，但不是 DCFL。

显然，这两种语言都是 CFL。显然，它们的并集也是 CFL。但请想象一下这个"显然的"PDA 是如何工作的：起始状态转移到"正确的"机器，让它识别某一种语言中的字符串。但我们怎样才能确定性地做到这一点呢？我们需要一种完全不同的方法。

虽然这还不是该语言不是确定性的证明，但下面有一个证明。

定理（Theorem）： \(L_1 \cup L_2\) 不是 DCFL （因为 \(a^nb^nc^n\) 不是 CFL）。

证明（Proof）：

创建两个副本的 \(M: M_1\) 和 \(M_2\) 。 \(M_1\) 和 \(M_2\) 中的相同状态称为表亲。

基于这些信息，我们现在可以更新形式语言宇宙（Formal Languages Universe）的模型。

7.3.2. 确定的上下文无关语言的文法¶

现在我们知道：

• 所有 CFL 都可以由 CFG 生成，并由 NPDA 实现。

• 并非所有 CFL 都能用 DPDA 生成。

• 因此，某些 CFG 只与非确定性的 PDA 相关联。 就能力而言，非确定性给了我们更多的东西。

我们为什么关心？因为我们希望高效地分析（parse）。也就是说，我们希望快速确定给定的字符串是否能由给定的文法生成。如果我们要做到这一点，确定性似乎是一个基本要求。

可以把 PDA 看作一种分析设备。无回溯（no backtracking）要求我们能在每一步都对下一步做什么作出决定。这等同于知道下一步该用哪一条文法产生式。显然，当文法已经被简化时（没有单位产生式），这是线性时间，因为每一步推导都会消耗一个输入字符。嗯……除了 \(\lambda\) 产生式。但我们很快就会看到，对于线性时间处理来说，它们其实并不是什么问题。