令语言G={x#y|x,y∈{0,1}*且x≠y}，证明G是一个上下文无关语言。

这是一道非常简短的上下文无关语言题目，出自《计算理论导引》，不过解这道题的过程和思路比较有意思……所以记录下来。

一、起初的错误答案

证明一个语言是CFG (Context Free Language) 通常有两个途径：

i) 构造一个能够生成这个语言的CFG

ii) 构造一台能够识别这个语言的PDA (Pushdown Automaton)

都是构造性证明。看着这道题没过多久，我就得到了一个“答案”：

S → XSX | T

T → 0#1 | 1#0

X → BX | ε

B → 0 | 1

乍一看，好像是对的，S必须由T派生出来，而T的左边和右边是肯定不一样的，这样S的左边和右边也肯定不一样。然而稍加考虑就会发现反例：

S → XSX → XTX → 0T1 → 01#01

从S推出了一个串，#左边的部分等于#右边的部分，显然这个解答是错误的。

这一题确实容易误导人，原因就在于我们设计派生文法的时候，通常遵循这样的步骤：先设计文法“基元”，然后再补充派生规则。在做这题的时候，我先写下一个#左边不等于#右边的基元规则T → 0#1 | 1#0，再补充派生规则，然后想当然地认为：既然最基本的部分不一样，其它部分肯定也不一样。但这是不对，因为这个文法不能同时感知#左右的所有部分，而只能感知#左右各一个字符。

不过我的文法可以生成这样的串……那就是#左右不对称的串。

二、不确定性和简化的问题

初次尝试失败，我的直觉是很难设计出描述这个语言的CFG，因为在用CFG同时顾及到#左右两边这方面完全没有思路。于是果断放弃文法，尝试构造相应的PDA。

与DFA (Deterministic Finite Automaton) 相比，PDA多了一个栈，因此在转移的时候可以看过去的历史，但也只能多看一个（栈顶）。显然多看一个不足以判断#两边的所有字符相不相等。PDA还有一个问题：PDA的附加结构是栈，若要借助栈来识别x#y，那么将x压入栈中，读到#再弹出来时，已经是逆序的了！所以毫无疑问，单凭这个栈，肯定不能够解决这个问题。

可见一次性地让自动机顾及#两边是不可能的，但自动机还有一个重要的特性（是什么？）没有用到：既然一台自动机不能判断整个串，就让许多台自动机共同来判断，每个自动机判断一对特定的符号。这样简化过的任务，自动机是绝对能办到的！

准确地说，没有“许多自动机”，而是让一台自动机产生“许多个分支”，每一个分支猜测一对符号。第一个分支判定x1=y1、第二个分支判定x2=y2、第三个分支判定x3=y3……xn表示x的第n个符号，依此类推。能够让自动机完成这种行为的特性，就是不确定性。

利用自动机的不确定性，问题被分解。

三、不确定性下推自动机的正确解答

OK，现在栈的作用性重新体现出来：栈不仅能让自动机看到历史，还能计数。我们必须通过栈的辅助，才能知道当前所在的分支判定的是x或y的第几个符号。

有了上面的分析，就可以构造PDA了，在构造之前，先介绍本文描述PDA的记法，本文采用与《计算理论导引》一致的记法，用来表示PDA，例如：

http://s3/bmiddle/4dff8712gbedcebc19ba2&690

表示PDA在状态a且读取到0时，跳转到状态b，并弹出栈顶的1；但有时候无论栈顶符是什么都弹出，但又不知道栈顶内容，此时就写出所有可能：

http://s6/bmiddle/4dff8712gbedce156d2e5&690

这表示只要在状态a时读到0，无论栈顶是什么，都弹出；当然有时候只简单地跳转而不改变栈：

http://s16/bmiddle/4dff8712gbedce2c3b46f&690

现在可以展示最终答案了。哦，对了，接受状态还是老规矩：http://s10/bmiddle/4dff8712gbedce82d8349&690

http://s9/bmiddle/4dff8712gbedcecceeb28&690

（PDA真难画-0- 不过我还挺满意的，除了表示接受状态的双环=.=）

解释一下工作流程：

1) PDA首先把x左边读到的字符都压入栈，每压入一个字符就产生一个分支，直至遇到#。如串011#001，PDA读取0，产生一个分支；读取01，产生第二个分支；读取011，又产生一个分支。分支在状态b处产生，注意到b读取0或1之后各有两种选择，这样就形成了不确定性。由不确定性产生的第k个分支用于判断xk=yk。

2) PDA用状态本身保存了第k个字符的信息，即若进入到状态c、d、e，表示xk=0；若进入到状态f、d、e，表示xk=1。

3) PDA的分支进入状态c（或f）后，就忽略#之前的字符，因为它不关心这些内容，这个分支只关心yk是什么。

4) PDA的分支进入状态d（或g）后，就开始每读到1个字符就从栈里弹出1个字符，此时栈的计数功能就起作用了。并且依据y的内容，这个分支的未来有3种可能，以状态d为例：

i. 经过连续地读取和弹栈后，遇到压箱钱$，此时读到的符号是1，即yk=1，与xk不同，因此x≠y，该分支进入接受状态e，同时PDA也接受。

ii. 经过连续地读取和弹栈后，该分支还没遇到压箱钱$，串就已经读完了，这表明y的长度肯定比x短，因此x≠y，该分支进入接受状态e，同时PDA也接受。这就是为什么我把d（和g）都标成接受状态，因为PDA可能会在这个状态上停止，这说明|x|>|y|，此时应该接受。

iii. 经过连续地读取和弹栈后，遇到栈底符$，此时读到的符号是0，即xk=yk=0，图中并没有标出这种情况，所以一旦分支进入这种状态， 它就“死掉了”。

5) 如果所以的分支都“死掉了”，说明对于所有的k（1≤k≤|x|），都有xk=yk，即x=y，则PDA不接受；否则只要任意分支接受，PDA都接受。

6) 分支c-d-e和f-g-h能处理所有|x|≥|y|的情况，但却不能识别x是y的真前缀这种情况（如001#0010），识别|x|<|y|的任务落在分支i-j-k上。进入状态i表示#之前的字符已经全部压栈，接下来开始读取y并弹栈。若这个分支在i上停止，说明|x|>|y|，接受；若进入状态j，则栈中的所有符号已经弹出，此时若串还没有读完，则识别到|x|<|y|的情况，进入接受状态，i-j-k分支的任务完成！

至此，这个PDA已经考虑到所有可能情况，也就解决了文章最开始的问题。其实这只是一道小小的题目，但却给自己上了一课：遇到问题的时候，要动用手头工具的所有特性！