语言模型

从求解问题到识别语言

在计算模型中，我们知道图灵机的计算对象是字符串，一切直觉上可计算的问题都可以被抽象为符号串的集合。我们把符号串称为句子，那么问题就被抽象为句子的集合，即语言。求解问题等价于图灵机的识别问题。

那么，如何构建一个可以接受以及产生一个语言的计算模型？进一步的，对于一个问题，如何判断它就是对应的语言？

为了解决这两个问题，我们引入语言的文法。文法可以描述一个语言的语法构成，自动构造有效的语言识别器。

文法

文法 $G=(V, T, S, P)$，其中：

• $V$ 是非终极符的有限集合，非终极符的意思是仅作为过程量出现；
• $T$ 是终极符的有限集合；
• $S$ 是开始符，显然 $S \in T$，必须在某个产生式的左边出现一次；
• $P$ 是产生式（规则）的集合，具有以下形式 $\alpha \to \beta$ 其中 $\alpha, \beta \in (V \cup T)^\star$

对于一个文法生成的语言，我们记为 $L(G)=\lbrace \omega \mid \omega \in T^\star , S \to^\star \omega \rbrace$。

例：

某语言有文法 $G$：

• $V=\langle alpha \rangle \langle number \rangle \langle sign \rangle$，$\langle sign \rangle:\langle sign \rangle \to \langle alpha \rangle \mid \langle sign \rangle \langle alpha \rangle \mid \langle sign \rangle \langle number \rangle$
• $T = \lbrace 0, 1, \cdots, 9, a, b, \cdots, z, A, B, \cdots Z \rbrace$
• $P = \lbrace \langle number \rangle \to 0, \langle number \rangle \to 1, \cdots, \langle number \rangle \to 9, \langle alpha \rangle \to a, \langle alpha \rangle \to b, \cdots, \langle alpha \rangle \to Z \rbrace$。

不难看出，这实际上定义了一个简单的以字符开头、字符和数字混合的一种字符串。

分类

对于 $(\alpha \to \beta) \in P$：

• 0 型文法：又称短语文法。$\alpha$ 中至少含有一个非终极符
• 1 型文法：又称上下文有关文法。在短语文法的基础上，要求 $\mid \alpha \mid \le \mid \beta \mid$（$S \to \varepsilon$ 除外，要求 $S$ 不得出现在产生式右部）
• 2 型文法：又称上下文无关文法。在上下文有关文法的基础上，要求产生式左部是一个非终极符，即 $\forall \alpha: \alpha \in V$
• 3 型文法：又称正则文法。在上下文无关文法的基础上，要求 $\alpha \to \beta$ 形如 $A \to a$ 或 $A \to aB$，$A$ 和 $B$ 是非终极符，$a$ 是终极符

例：

$G = (\lbrace A, B, C, S \rbrace, \lbrace a, b \rbrace, S, P = \lbrace S \to AB, S \to BC, B \to CC, B \to b, C \to AB, C \to a, A \to BA, A \to a \rbrace)$

1. 这是什么类型的文法？

   对照上文，可以看出是上下文无关文法。

2. 试证明给定串 $baaba, S \to^\star baaba$。

   显然 $baaba \in T^\star$，$S \to BC \to BAB \to BACC \to BAABC \to BAABa \to baaba$

正则文法

要点：所有产生式都形如 $A \to a$ 或 $A \to aB$。

正则语言的识别

该问题等价于证明是否有 $S \to^\star \omega$

设 $\omega = a_1 a_2 \cdots, a_n \in T^\star$

若 $n = 1$，那么只需要判断 $S \to a_1$ 是否在 $P$ 中；否则，判断 $S \to a_1 B_1, B_1 \to^\star a_2 \cdots a_n$ 是否成立。

实现：从右向左推导，在 $P$ 中选择右部为 $a_n$ 的产生式，其左部非终极符组成一个集合 $V_1 = \lbrace A_1 \mid (A_1 \to a_n) \in P \rbrace$

进一步，$V2 = \lbrace A_2 \mid (A_2 \to a{n-1} A1) \in P, A_1 \in V_1 \rbrace$，以此类推，最后得到 $V_n = \lbrace A_n \mid (A_n \to a{1} A{n-1}) \in P, A{n-1} \in V_{n-1} \rbrace$

$S \to^\star \omega$ 当且仅当 $V_n$ 非空。

有限自动机

和图灵机类似，可以认为是一个只有读功能的图灵机，因此完全没有记忆功能，只能确定输入的字符串是否接受。图灵机的术语同样适用于有限自动机。

根据每次转换后的状态是否唯一, 可将有限自动机分为确定有限自动机（DFA）和非确定有限自动机（NFA）。两者的区别在于：确定有限自动机在一个状态下，对于一个读入的数据只会有一个（或者没有）对应的转换函数，但非确定有限自动机可能会有多个不同的转换函数，使得非确定有限自动机两次的计算不同。需要注意的是，即使非确定有限自动机的计算不同，结果也是一致的。

定理：每一台非确定有限自动机都等价于某一台确定有限自动机。

准确地说，每一台非确定图灵机都等价于某一台确定图灵机。

定理：语言是正则的，当且仅当它可以被有限自动机接受。

正则语言的局限

• 不能描述配对或嵌套结构
• 不能描述重复串（即描述一个串，使它形如 $aba$）

上下文无关文法

要点：所有产生式的左部都是一个非终极符。

乔姆斯基范式

如果一个上下文无关文法中产生式形如 $A \to BC$ 或 $A \to a$，其中 $A, B, C$ 是非终极符，$a$ 是终极符，$B, C$ 不是开始符，允许有空产生式 $S \to \varepsilon$，那么这个文法称为乔姆斯基范式。任一上下文无关文法都可等价转换为乔姆斯基范式形式。

乔姆斯基范式的语法树是二叉树形式。

对于任意给定的串，将非终极符为树枝，终极符为树叶，则该串可以认为是树。任一上下文无关文法都可等价转换为乔姆斯基范式形式等价于可以将任何树转换为二叉树。

证明（操作）：

1. 替换开始符 $S$，即增加两个产生式 $S’ \to S$ 和 $S’ \to \varepsilon$。
2. 消除空产生式 $A \to \varepsilon$，同时对所有 $R \to \alpha A \beta$ 增加产生式 $R \to \alpha \beta$。若有 $R \to A$ 则增加产生式 $R \to \varepsilon$ 并重复这个步骤直到没有空产生式。
3. 消除单元产生式 $A \to B$，对所有 $B \to \alpha$ 增加 $A \to \alpha$。
4. 替换产生式，对所有 $A \to a_1 a_2 \cdots a_n$ 替换为 $A \to a_1 A_1$ 和 $A_1 \to a_2 a_3 \cdots a_n$ 并重复这个步骤直到所有产生式的右部长度小等于 2。

例：

$G = (\lbrace A, B, S\rbrace, \lbrace a,b \rbrace, S, P=\lbrace S \to ASA \mid aB, A \to B \mid S, B \to b \mid \varepsilon \rbrace)$

1. 替换开始符

   $S’ \to S$

   $ S \to ASA \mid aB$

   $ A \to B \mid S$

   $ B \to b \mid \varepsilon$

2. 消除空产生式

   $S’ \to S$

   $ S \to ASA \mid aB \mid a \mid AS \mid SA \mid S$

   $ A \to B \mid S$

   $ B \to b$

3. 消除单元产生式

   $S’ \to ASA \mid aB \mid a \mid AS \mid SA$

   $ S \to ASA \mid aB \mid a \mid AS \mid SA$

   $ A \to b \mid ASA \mid aB \mid a \mid AS \mid SA$

   $ B \to b$

4. 替换

   $S’ \to AA_1 \mid UB \mid a \mid AS \mid SA$

   $ S \to AA_1 \mid UB \mid a \mid AS \mid SA$

   $ A \to b \mid AA_1 \mid UB \mid a \mid AS \mid SA$

   $ B \to b$

   $ A_1 \to SA$

   $ U \to a$

上下文无关语言的识别

定义：对于串 $\omega = a1 a_2 \cdots a_n$，串 $\omega{ij} = ai a{i+1} \cdots a_{i+j-1}$

定义：$V{ij} = \lbrace A \mid A \to^\star \omega{ij} \rbrace$，即可以推导出 $\omega_{ij}$ 的非终极符集。

我们把$\lbrace A \mid (A \to BC) \in P, B \in V{ik}, C \in V{(i+k)(j-k)} \rbrace$ 简记为 $\lbrace \to V{ik}V{(i+k)(j-k)} \rbrace$，显然 $V{ij} = \cup \lbrace \to V{ik} V_{(i+k)(j-k)}\rbrace$

把语法转换为乔姆斯基范式后，对于 $\omega = a1 a_2 \cdots a_n$，若 $n = 1$ 则判断 $S \to a_1 \in P$，否则判断 $S \to BC \in P, BC \to^+ \omega$，也就是把串一分为二推导，最后等价于判断 $S \in V{1n}$。

接下来，我们考虑这样的一个倒三角形：

• 共 $n$ 行，第一行有 $n$ 个元素，然后递减，第 $n$ 行有 $1$ 个元素
• 第 $i$ 行的第 $j$ 个元素代表 $V{ji}$，显然最后一行的唯一一个元素就是 $V{1n}$

注意到 $V{ij} = \cup \lbrace \to V{ik} V{(i+k)(j-k)}\rbrace$ 中 $V{ik}$ 和 $V_{(i+k)(j-k)}$ 都一定在第 $j$ 行以前出现，因此这个倒三角形下方的元素一定可以在上方元素全部确定后只依靠上方元素确定。

这个方法称为倒三角形法。

例：

$G = (\lbrace A, B, C, S \rbrace, \lbrace a, b \rbrace, S, P$，$P = \lbrace S \to AB, S \to BC, B \to CC, B \to b, C \to AB, C \to a, A \to BA, A \to a \rbrace)$，判断 $baaba$ 是否是 $L(G)$ 的句子。

$G$ 已经是乔姆斯基范式。

确定第一行 $V_{i1}$：$\lbrace B \rbrace, \lbrace A, C\rbrace, \lbrace A, C\rbrace, \lbrace B \rbrace, \lbrace A, C\rbrace$

确定第二行 $V{i2}=\lbrace \to V{i1} V_{(i+1)1}\rbrace$：$\lbrace A, S \rbrace, \lbrace B \rbrace, \lbrace S, C \rbrace, \lbrace A, S\rbrace$

确定第三行 $V{i3}=\lbrace \to V{i1} V{(i+1)2}\rbrace \cup \lbrace \to V{i2} V_{(i+2)1}\rbrace$：$\emptyset, \lbrace B \rbrace, \lbrace B \rbrace$

确定第四行 $\emptyset, \lbrace A, C, S\rbrace$

确定第五行 $V_{15} = \lbrace A, C, S\rbrace$

$S \in V_{15}$，因此文法 $G$ 可以识别 $baaba$。

下推自动机

下推自动机（PDA）是一种计算模型，比有限状态自动机多一个长度无限的栈，同样有确定下推自动机和非确定下推自动机。

下推自动机 $M= (Q, \Gamma, \Sigma, \delta, q_0, Z_0, F)$，其中：

• $Q$ 有限状态集
• $\Gamma$ 栈符号集
• $\Sigma$ 输入符号集
• $q_0$ 初始状态
• $Z_0$ 栈初始符号
• $F \subseteq Q$ 终止状态集
• $\delta$ 状态转换函数集

对于确定下推自动机，转换函数形如 $Q \times (\Sigma \times \Gamma^\star) \to Q \times \Gamma^\star$

对于非确定下推自动机，转换函数形如 $Q \times (\Sigma \cup \lbrace \varepsilon \rbrace \times \Gamma^\star) \to \lbrace Q \times \Gamma^\star \rbrace$

定理：确定下推自动机和非确定下推自动机不等价（确定下推自动机缺少二义性）。

下推自动机的初始格局为 $(q_0, \omega, Z_0)$

接受格局：

• 空栈接受格局 $(q \in F, \varepsilon, \varepsilon)$
• 终态接受格局 $(q \in F, \varepsilon, \gamma \in \Gamma^\star)$

对于确定下推自动机，两者不等价；对于非确定下推自动机，两者等价。

定义下推自动机 $M$ 接受 $\omega$ 当且仅当存在格局序列 $C_0, C_1, C_2, \cdots, C_n$ 使得 $C_0 \vdash^\star C_n$，其中 $C_0$ 是初始格局，$C_n$ 是接受格局，并把这个序列称为 $M$ 进行的计算，$n$ 称为计算的长度或步骤。

下推自动机等价定理：

• 两个确定下推自动机 $A$ 和 $B$，$L(A)$ 和 $L(B)$ 是否等价是可判定的
• 两个非确定下推自动机 $NA$ 和 $NB$，$L(A)$ 和 $L(B)$ 是否等价是不可判定的

定理：语言是上下问无关的当且仅当它可以被一台非确定下推自动机识别。

泵引理

正则语言泵引理

设 $L(G)$ 是正则语言，则存在一常数 $p > 0$ ，对于语言 $L$ 中每个满足 $\mid \omega \mid \ge p$ 的字符串 $\omega$，存在一组字符串 $x, y, z$ 使得 $\omega = xyz$，且满足：

• $\mid xy \mid \le p$
• $y \ne \varepsilon$
• $\forall i \ge 0, xy^iz \in L$

证明：取 $p$ 为该正则语言的有限自动机的状态数，根据鸽巢原理容易证明。

泵引理用于判断语言不是正则的。

上下文无关语言泵引理

设 $L(G)$是上下文无关语言，则存在正整数 $p$，有字符串 $\omega = uvxyz, \mid \omega \mid \ge p$ 满足：

• $\mid vxy \mid \le p$
• $\mid vy \mid > 0$
• $\forall i > 0, uv^ixy^iz \in L$