John Watrous 《Introduction to the Theory of Computing》07 -- 上下文无关语法和语言

前言

接下来在本课程中我们将要学习的语言类是上下文无关语言类，它是由上下文无关语法的概念来定义的，简称CFG。

知识点

上下文无关语法和语言的定义

我们先从上下文语法的定义开始。

定义7.1. 一个上下文无关语法（context-free grammar或者CFG）是一个4-元组

$$G=(V,\Sigma,R,S),$$

其中$V$是一个有限非空集合（它的元素被称作变量），$\Sigma$是一个字母表（与$V$不相交），$R$是规则的有限非空集合，对于$A\in V$和$w\in(V\cup \Sigma)^{*}$每条规则的形式为

$$A\rightarrow w,$$

还有$S\in V$是一个变量，被称作初始变量。

案例7.2. 对于我们首个CFG的案例，我们会选择$G=(V,\Sigma,R,S)$，其中$V=\{S\}$（这个语法中只有一个变量），$\Sigma=\{0,1\}$，$S$是初始变量，$R$包含两条规则：

$$\begin{align}S&\rightarrow 0S1 \\ S&\rightarrow \varepsilon\end{align}$$

　　通常为了方便我们仅像上面一样列出规则即可描述一个语法。当我们这样做时，默认变量集合$V$和字母表$\Sigma$是隐式地被决定了的：变量是出现在规则左边的大写字母，而字母表则包含了规则右手边剩下的符号。此外，初始变量默认是第一条规则左边的变量。注意这样做是为了方便和节约时间，你可以简单地列出$V、\Sigma、R、S$的元素，但这样反而会造成误解。
　　每个上下文无关语法$G=(V,\Sigma,R,S)$生成一个语言$L(G)\subseteq\Sigma^{*}$。通俗来讲，这个语言包含了所有通过以下流程获得的字符串：

1. 写下初始变量S。
2. 重复任意次数以下步骤：（i)从$R$选择任意规则$A\rightarrow R$。（ii)在你目前所写的变量和字母表符号的字符串中，将任意变量$A$替换成字符串$w$。
3. 如果你最后获得的字符串形式为$x\in\Sigma^{*}$，没有变量剩余，那么就结束了。通过这个流程获得的字符串$x$就是通过$G$生成的字符串之一。

案例7.3. 案例7.2中描述的CFG $G$生成的语言是

$$SAME=\{0^n1^n:n\in\mathbb{N}\}.$$

这是因为我们开始先写下初始变量$S$，然后我们选择两条规则之一来执行替换：始终都会有一个$S$出现在字符串中间，我们只能把它替换成$0S1$或者$\varepsilon$。一旦我们选择了$S\rightarrow\varepsilon$，整个流程就结束了，所以我们获得的字符串取决于我们使用规则$S\rightarrow 0S1$的次数。

$$\varepsilon,01,0011,000111,...$$

等等。这个集合中的字符串所有字符串和$SAME$所给出的字符串完全一样。
　　通过CFG生成语言的这个流程描述提供了一个直观的，人类可读的方式来解释这个概念，但是从数学角度来看并不是非常让人信服。我们更愿意接受基于集合、函数等等的定义。还有一个从数学上定义这个概念的方式是从规范执行概念替换的产出关系开始着手。

定义7.4. 已知$G=(V,\Sigma,R,S)$是一个上下文无关语法，产出关系通过$G$定义一对基于$V\cup\Sigma$的字符串的关系如下：

$$uAv\Rightarrow_G uwv,$$

其中字符串$u、v、w\in(V\cup\Sigma)^{*}$和变量$A\in V$，条件是规则$A\rightarrow w$包含在$R$中。

对于这个关系的解释是对于$x、y\in (V\cup\Sigma)^{*}$当可以将$x$中出现的某个变量通过$G$的规则替换后获得$y$就有$x\Rightarrow_G y$。
　　如果从这个关系的自反传递闭包来考虑也是很方便的，这个定义如下所示。

定义7.5. 已知$G=(V,\Sigma,R,S)$是一个上下文无关语法。对于任意两个字符串$x、y\in(V\cup\Sigma)^{*}$存在

$$x\stackrel{*}{\Rightarrow}_G y$$

的条件是存在一个整数$m$和字符串$z_1,…,z_m\in(V\cup\Sigma)^{*}$使得

1. $x=z_1$,
2. $y=z_m$,并且
3. 对于每个$k\in\{1,…,m-1\}$有$z_k\Rightarrow_G z_{k+1}.$

这样，此关系的解释就是当$x$可以根据$G$的规则执行零次或者多次替换后变成$y$时则存在$x\stackrel{*}{\Rightarrow}_G y$。
　　现在我们可以用这个刚定义的关系来正式定义通过上线文无关语法生成的语言。

定义7.6. 已知$G=(V,\Sigma,R,S)$是一个上下文无关语法。通过$G$生成的语言是

$$L(G)=\{x\in\Sigma^{*}:S\stackrel{*}{\Rightarrow}_G x\}.$$

　　如果对于一个CFG $G=(V,\Sigma,R,S)$有$x\in L(G)$，并且$z_1,…,z_m\in(V\cup\Sigma)^{*}$是一系列字符串，其中对于所有$k\in\{1,…,m-1\}$有$z_1=S、z_m=x、z_k\Rightarrow_G z_{k+1}$，那么序列$z_1,…,z_m$被称作$x$的推导。如果你拆分上面定义，那就是对于每个字符串$x\in L(G)$一定至少存在一个推导，但是普遍情况下对于一个已知字符串$x\in L(G)$都存在超过一个推导。
　　最后，我们将上下文无关语言类定义为那些通过上下文无关语法生成的语言。

定义7.7. 已知$\Sigma$是一个字母表，$A\subseteq\Sigma^{*}$是一个语言。语言$A$是一个上下文无关的仅当它存在一个上下文无关语法$G$使得$L(G)=A$。

案例7.8. 语言$SAME$是一个上下文无关语言，正如案例7.3上中所构建的那样。

上下文无关语法和语言的案例

目前我们已经见过一个上下文无关语言：$SAME$。让我们来看看更多的例子。

基本案例

案例7.9. 语言

$$PAL=\{w\in\Sigma^{*}:w=w^R\}$$

基于字母表$\Sigma=\{0,1\}$，我们在第5课中首次提到，它是上下文无关的（事实上无论你选择什么字母表它都是上下文无关的，但是让我们暂时只简单考虑二进制字母表）。为了验证这个语言是上下文无关的，我们需要找到一个上下文无关语法来生成它。这里有一个可行的语法：

$$\begin{align}S&\rightarrow 0S0 \\ S&\rightarrow 1S1 \\ S&\rightarrow 0 \\ S&\rightarrow 1 \\ S&\rightarrow \varepsilon\end{align}$$

　　我们通常用一个速记概念来描述规则左边都是同样变量的语法，就像上个例子那样。这种速记概念就是将变量写在左手边，而且箭头只有一个，画一个竖线将所有可能的右手边部分分隔开，就像这样：

$$S\rightarrow 0S0\ |\ 1S1\ |\ 0\ |\ 1\ |\ \varepsilon$$

当你手写这种速记概念时，比如在考试中，一定要确保你的竖线能够和1区分开来。
　　有时候很容易找到生成已知语言的特定CFG — 比如，前面这个例子看起来就很明显。在其他的情况下验证特定的语法生成某个语言可能会更具挑战，或者更困难。接下来的例子阐述了一种情况，这个验证不普通。

案例7.10. 已知$\Sigma=\{0,1\}$是一个二进制字母表，定义一个语言$A\subseteq\Sigma^{*}$如下：

$$A=\{w\in\Sigma^{*}:|w|_0=|w|_1\}.$$

这里我们使用了一个简便概念：$|w|_0$表示0在$w$中出现的次数，同样$|w|_1$表示1在$w$中出现的次数。因此语言$A$包含的所有字符串中的0和1数量相等。这是一个上下文无关语言，它由下面这个上下文无关语法生成：

$$S\rightarrow 0S1S\ |\ 1S0S\ |\ \varepsilon$$

　　现在，这个语法我们称作$G$，很明显它生成的每个字符串都包含在$A$中：我们从一个单独的$S$开始推导，最开始的字符串中0和1的数量是相等的（准确说数量是0），而且每条规则也保证了这个性质不变。
　　另外，这里不能明显看出每个$A$的元素都能由$G$生成。让我们来证明这个情况。

声明7.11. $A\subseteq L(G).$

证明：让$w\in A$是一个包含于$A$的字符串，$n=|w|$。我们将证明对$n$进行归纳来证明$w\in L(G)$。
　　基本情况是$n=0$，也就是$w=\varepsilon$。我们让$S\Rightarrow_G \varepsilon$表示一个$\varepsilon$推导，因此$w\in L(G)$。
　　至于归纳步骤，我们假设$n\geq 1$，假设对于每个$x\in A$并且$x<n$都有$x\in L(G)$。我们的目标是证明$G$生成了$w$。让我们写出

$$w=a_1\cdot\cdot\cdot a_n,$$

其中每个$a_1,…,a_n\in\Sigma$。我们已经假设了$w\in A$，因此

$$|a_1\cdot\cdot\cdot a_n|_0=|a_1\cdot\cdot\cdot a_n|_1.$$

　　接下来，让$m\in\{1,…,n\}$是一个最小值使得

$$|a_1\cdot\cdot\cdot a_m|_0=|a_1\cdot\cdot\cdot a_m|_1.$$

我们知道这个等式在$m=n$时也是成立的，而且也许存在一个比$n$小的值也成立。我们现在要证明$a_1\neq a_m$。
　　我们通过反证法来证明$a_1\neq a_m$。假设$a_1=a_m$，定义

$$N_k=|a_1\cdot\cdot\cdot a_k|_1-|a_1\cdot\cdot\cdot a_k|_0,$$

其中$k\in\{1,…,m\}$。我们知道$N_m=0$。此外，使用假设$a_1=a_m$，我们观察这个等式

$$|a_1\cdot\cdot\cdot a_m|_1=|a_1\cdot\cdot\cdot a_{m-1}|_1+|a_m|_1=|a_1\cdot\cdot\cdot a_{m-1}|_1+|a_1|_1$$ $$|a_1\cdot\cdot\cdot a_m|_0=|a_1\cdot\cdot\cdot a_{m-1}|_0+|a_m|_0=|a_1\cdot\cdot\cdot a_{m-1}|_0+|a_1|_0,$$

然后将上面第一个等式减去第二个得出

$$N_m=N_{m-1}+N_1.$$

因为$N_m=0$，并且$N_1$不等于0，那么$N_{m-1}$也一定不是0，更重要的是$N_1$和$N_{m-1}$的正负是相反的。然而，因为$N_k$的值是连续相差1的整数，我们得出一定存在某个$k$在范围$\{2,…,m-2\}$中使得$N_k=0$，否则$N_1$和$N_m-1$的正负不可能是相反的。然而这与我们对$m$的设定相矛盾。因此我们证明了$a_1\neq a_m$。
　　到了这个点上，我们可以描述一个$w$的推导。我们有$w=a_1\cdot\cdot\cdot a_n$，还有

$$|a_1\cdot\cdot\cdot a_m|_0=|a_1\cdot\cdot\cdot a_m|_1\ \ \ 和\ \ \ \ a_1\neq a_m,$$

其中$m\in\{1,…,n\}$。我们得出

$$|a_2\cdot\cdot\cdot a_{m-1}|_0=|a_2\cdot\cdot\cdot a_{m-1}|_1\ \ \ 和\ \ \ |a_{m+1}\cdot\cdot\cdot a_n|_0=|a_{m+1}\cdot\cdot\cdot a_n|_1.$$

根据归纳假设可知

$$S\stackrel{*}{\Rightarrow}_G a_2\cdot\cdot\cdot a_{m-1}\ \ \ 和\ \ \ S\stackrel{*}{\Rightarrow}_G a_{m+1}\cdot\cdot\cdot a_n.$$

因此字符串$w$满足

$$S\Rightarrow_G 0S1S\stackrel{*}{\Rightarrow}_G 0a_2\cdot\cdot\cdot a_{m-1}1a_{m+1}\cdot\cdot\cdot a_n=w$$

(这种情况下$a_1=0、a_m=1$)或者

$$S\Rightarrow_G 1S0S\stackrel{*}{\Rightarrow}_G 1a_2\cdot\cdot\cdot a_{m-1}0a_{m+1}\cdot\cdot\cdot a_n=w$$

(这种情况下$a_1=1、a_m=0$）。如此我们证明了$w\in L(G)$。

这里有另外一个例子与前面这个有关。而且贯穿整个课程我们会多次参考到它。

案例7.12. 已知字母表$\Sigma=\{(,)\}$。这个字母表中我们有两个符号：左括号和右括号。
　　我们说基于$\Sigma$的字符串$w$是平衡配对的，那就意味着我们通过重复移除子串$()$，最后你会得到$\varepsilon$。更直观来说，一个基于$\Sigma$的字符串是平衡配对的仅当这个字符串用作一个普通算数表达式的括号模式时是有意义的。这里有一些平衡配对的例子：

$$(()())(),\ \ \ ((()())),\ \ \ (()),\ \ \ 和\ \ \ \varepsilon.$$

还有一些字符串不是平衡配对的例子：

$$((())()\ \ \ 和\ \ \ ())(.$$

现在定义一个语言

$$BAL=\{w\in\Sigma^{*}:w是平衡配对的\}.$$

语言$BAL$是上下文无关的；这里有个CGF可以生成它：

$$S\rightarrow (S)S\ |\ \varepsilon$$

看看你能不能说你自己这个CFG确实可以生成$BAL$！

一个更复杂的案例

有时候要找出一个已知语言的上下文无关语法是很具有挑战性的。接下来的案例就是这样的语言。

案例7.13. 已知$\Sigma=\{0,1\}$，$\Gamma=\{0,1,\sharp\}$，然后定义

$$A=\{u\sharp v:u,v\in\Sigma^{*} 和 u\neq v\}$$

这儿有一个$A$的上下文无关语法：

$$\begin{align}S&\rightarrow W_01\Upsilon\ |\ W_10\Upsilon\ |\ Z \\ W_0&\rightarrow XW_0X\ |\ 0\Upsilon\sharp \\ W_1&\rightarrow XW_1X\ |\ 1\Upsilon\sharp \\ Z&\rightarrow XZX\ |\ X\Upsilon\sharp\ |\ \sharp X\Upsilon \\ X&\rightarrow 0\ |\ 1 \\ \Upsilon&\rightarrow X\Upsilon\ |\ \varepsilon.\end{align}$$

这个CFG背后的思路是这样的。首先，变量$Z$生成了形式为$u\sharp v$的字符串，其中$u$和$v$的长度不同。变量$W_0$生成的字符串是：

$$\underbrace{\Box\Box...\Box}_{n个}0\underbrace{\Box\Box...\Box}_{m个}\sharp \underbrace{\Box\Box...\Box}_{n个}$$

（其中$Box$表示0或者1），那么$W_01\Upsilon$生成字符串是：

$$\underbrace{\Box\Box...\Box}_{n个}0\underbrace{\Box\Box...\Box}_{m个}\sharp \underbrace{\Box\Box...\Box}_{n个}1\underbrace{\Box\Box...\Box}_{k个}$$

（其中$n、m、k\in\mathbb{N}$）。同样地，$W_10\Upsilon$生成的字符串是：

$$\underbrace{\Box\Box...\Box}_{n个}1\underbrace{\Box\Box...\Box}_{m个}\sharp \underbrace{\Box\Box...\Box}_{n个}0\underbrace{\Box\Box...\Box}_{k个}$$

综合起来看，这两种$u\sharp v$的所有二进制字符串$u$和$v$至少有一个位置不同（而且可能长度相同或者不同）。三种选择放到一起就覆盖了所有$v\sharp v$中$u$和$v$不相等的所有二进制字符串。

原文链接

https://cs.uwaterloo.ca/~watrous/ToC-notes/ToC-notes.07.pdf