计算理论 CH3
Ch3:Context-free Language and Pushdown Automata
第二章介绍了正则语言、有限状态机；我们知道了有大量的非正则语言是无法通过这个方法描述的。于是，在这一章里探究如何表达这样的非正则语言
3.1 Context-free Grammar
可以被CFG表示的语言称为CFL（context-free language）
对于我们的例子anbn，得到的CFG的各个部分定义如下：
也就是说，S是一个抽象的概念，然后下面的规则会定义如何从一开始一个抽象的S一步步生成我需要的整个语言。
再注意一下上面的这个定义中的内容：也就是说，所有可能出现在语言中的字符就是终结符集；字母表是终结符集+非终结符，这点与第二章的定义不同。
有关的一个定理：所有的正则语言都是CFL
这个的证明就是尝试构造出一个CFG的方式：
其实就是一种形式化的简单构造方式
这页展示了对于文法的推导规则，也就是说这部分语言的核心是在于不断通过规则将一个字符串生成为另一个字符串。根据我的“语法”G生成的语言称为L(G)
3.2 Parse Tree
针对语法树和前面的CFG，定义了一个similarity：
相当于，前面的部分都一样；后面相邻的两部交换了前后展开的顺序，这两步之后的得到的结果一样。这个时候称为两个推导是similar的。 事实上，similar是等价关系；并且，在对于similar关系的一个等价类下，其parse tree是相同的，也就是说实际上就是对于同一颗语法树的不同展开方式。
这里需要注意，两个推导结果一样，就可以认为他们是similar的；similar和前面的precede的关系是，similar是precede的最小（等价）闭包
以及一个对于所谓语法树yield的定义：这是指将语法树所有的叶子节点从左到右连起来的结果字符串
leftmost derivation和rightmost derivation：分别表示优先从左边展开以及优先从右边展开一个语法树；并且紧接着上面的定义，可以知道leftmost是similar下这个等价类中的mininal（找不到比它更小的）
我们规定，对于两种推导方法D和D’，我们称D procedes D’,如果这两种展开方式途中只有一步不一样，并且在这一步的时候，D会先展开前面部分的字符串A，而D’会先展开后面部分的字符串B。
- 两个错误的结论！
一个直观的理解：可能树不一样，但是得到的结果不一样；另一个方面的理解，也就是说前面的similar要求每两步之间必须是precede的（也就是只差了一步），但你如果中间某一步跳跃了一下，得到的结果可能也是相同的，但是并不similar。因此，引入如下的概念：
- ambiguous：如果在一个grammar中，存在一个string，这个string的parse tree有很多，那么这个语法就是ambiguous的（有歧义的） 因此
对于这里的ambigous的一种直观的理解：就是理解为有歧义的，也就是对于同一个string可以有多种理解它的方式：比如说，我们一个有歧义的语法生成了 a+bc，这里我们通过不同的语法树对其进行解构，可以将其理解为 (a+b)c，或者a+(b*c)，这时候就有歧义。
3.3 Pushdown Automata
这个东西就是用来识别CFL的一种机器。 对于前面的识别正则语言的一个机器，如果想用其识别CFL，一个直观的感受就是最好需要一个模式来记忆之前发生了什么
因此，PDA多引入了一个用于写和操作的stack，具体如下：
总体的计算过程是一样的，都是读入一个，然后转移，只不过同时需要维护这样一个新的stack；最终判断可接受是字符串读完、到达最终状态，并且stack被清空
对于PDA的核心定义部分如下：
关键就在于这个转移关系：我从左边的三元组转化为右边的二元组，比如((s,a,e),(s,a)),其意义就是我从状态s读到字符a，我不pop任何东西，进入状态s，并且向stack中push一个字符a。 一般地，一次操作小于等于一个字符（在栈中）
容易发现：对于每一个FA，相当于将其看成每次不对栈进行任何操作的PDA。
注意：PDA和之前的FA一样，也有空转移的概念：
能够有空转移的PDA能力会更强（这里与FA不同，确定性的PDA和非确定性的PDA能力是不一样的，前者会更弱一些）
这里，一般只有非确定性的PDA才可以解决大多数问题。比如说我们要识别abba，这个时候需要我们人为知道读到第一个b的时候就要从push变成pop了，这时候就需要空转移；这个行为无法预判，因此不能使用确定性PDA
类似地，我们在这里也定义了一个configuration（对于当前时刻的快照），如图所示：
三元组分别记录： 1. 当前的状态p 2. 当前等待被读的字符串x 3. 当前stack中的内容α
因此，很容易理解：
看这个例子：我要判断字符串是a和b数量相等的，这个时候我们想要做的是：首先放入一个c，标志字符串的终止；然后，我们想要的是stack中只有单一的a或者b，并且读到一个a，就消掉一个stack中的b，否则push a，反之亦然。
3.4 PDA and CFL
我们有定理：一个语言是CFL 等价于 其为PDA （这个部分证明先欠着）
3.5 Languages that are and are not CF
一个不属于CFL的语言的一个直观的例子： anbncn 因为CFL处理语言的核心就是多了这样一个栈的功能，而对于栈这种先进后出的结构，其处理问题的能力是有限的；比如说我要记忆三个量的数据关系，而我通过不断的push和pop只能处理两个数量的关系，因此这样的三个就不好处理。 
这个是比较好理解的，因为可以认为我的DFA操作是不涉及到stack的；那么我构造的规则就相当于：我两个字符串的intersection中，涉及到DFA的部分就直接在状态上操作；否则再对于stack操作，相当于是一个并行操作的概念：一部分对于栈里面的内容操作，一部分只是对于状态之间进行操作。
我们的FA对于所有的五个操作都是等价的，但是CFA实际上只对于 union, concatenation, and Kleene star 是等价的，对于intersection和complement不是等价的。
结合语法树，对于我们的CFL也有对应的泵定理pumping theorem
总结一下对于非CFL的直观判断： 1. 比如说记忆a的数量为质数、有多少个a的问题 2. 可以处理判断a b数量相等之类的一种关系的问题，但如果是判断abc三者数量相等，那么会超出处理范围 3. 以这个例题为例：
4. 这个的结果为false，因为堆栈的性质是先进后出，我们一开始记忆了a和b的数量之后，后面想要判断，由于我所有的a都在底部，后面我们在栈中的都是b的信息，无法比较a的数量。