确定型上下文无关文法与编译原理
计算理论课上讲上下文无关文法的时候跳过了这一部分。但是看起来这一块恰恰对编译原理相当重要。
所以浅浅看下书上这部分的内容，顺便跟编译原理联系联系。
能打开这个博客一定说明你已经会了，所以这里只说说相比起确定在哪里。
的定义本身是自带非确定性的，其中尤其以空转移最为麻烦，而在中，一个状态出发的所有转移只能是要么都读取字符，要么都为空转移，不可能存在部分转移读取字符，而另一部分转移是空转移。栈操作也是确定的，要么推入确定的字符，要么弹出。
形式化的说，有且仅有一个非空。这意味着任何情况下都总可以转移，而且如果存在空转移，那么一定只会有这一种转移方式。
在深入确定型上下文无关语言之前，首先我们利用来证明一些结论，以方便后续的讨论。
仅当读完全部输入后处于接受状态，才会接受字符串，其他情况下都拒绝。但并不是所有拒绝的情况下都会读完输入串，这只可能是由于在空栈状态下继续弹出，或者是进入了一个由空转移形成的环导致的。
我们其实就是解决上述的两种情况。对于第一种情况，之前在中已经有了成熟的经验，在最开始之前推入一个栈底符号总是有用的，如果发现栈底被弹出来了我们就读入所有剩下符号然后拒绝。
对于第二种情况，这种死循环是可以识别的（回忆一下逛公园中的找零环），把这些状态找出来，然后修改使得原本通向这些状态的转移走向一个人为设置的结束状态，读入剩下全部符号然后拒绝。不过有一种特殊情况要特殊处理——如果我们读完了最后一个符号然后接受了，那么就应当直接接受，当然这是容易的。
另外一个事情是为了方便后续定义的文法的。我们会希望给语言末尾加上一个特殊的结束符（后面会看到它的作用）。这么定义它：。
和显然不一样，但是我们希望和作为能有相通之处。
看起来这个结论似乎很显然但是实际上并不显然。从左往右很容易，但是从右往左就难了。书上的证明可以看，但是并不容易理解在做什么，这里按照个人理解简单说一下。
从右往左的问题主要的难点在于不知道何时结束对中字符串的读取。假设我们有一台能跑，它显然会在读入符号以后准备处理栈，最后接受或拒绝，而这就依赖于读入后栈里的内容。但是如果我们想要构造一台通过模拟来识别，由于确定性的制约，我们不能像一样“判断”读入是否结束（也就是判断读取到的字符是否为）然后进入处理栈的流程。
因此我们应该随时做好“结束读入”的准备，换句话说，在任意时刻都要能够判断“假设接下来读入了，会在一系列栈操作之后接受吗？”我们将这个问题的答案连同原本的栈中字符一起存在的栈里，用于模拟。
更具体的，把的状态集合的子集作为字符也存在的栈里，的栈总会是这样的结构：中的字符-状态集合-中的字符-状态集合-…
为了简单考虑，我们认为每一时刻只进行三种可能动作之一：读取，压栈，弹栈。
我们用模拟的这三种操作，并且保证如下原则：任意时刻栈顶集合中的状态满足如下条件——从这些状态出发，带有栈中的字符组成的栈，能够在不读取任何字符的情况下接受。
这其实就是个递推的过程，在刚开始，我们需要向的栈中推入“所有能从空栈出发，不读取任何字符能够被接受的状态的集合”，然后在模拟三种操作时维持上述原则即可。
对每个状态都可能会有读取的转移。相应的，对于而言，对于每次读入，都判断转移到的状态是否处于栈顶集合中，转移向接受状态（但是不一定接受，因为可能还未读完字符串）。如果读入结束了就立即接受了，否则就继续模拟。因此的状态集里也要有的接受状态。
这当然不是全部的证明，但是有了这些解释以后再去看书上证明可能会更好理解。
不同于自顶向下的派生，我们主要通过自底向上的规约来定义。稍微想一想编译原理，对于语法分析我们确实有“自顶向下派生”和“自底向上规约”两个路子。