写在前面
首先，默认读者已经了解 DFA/NFA (Finite Automaton) 的概念，及其和 RE (Regular Expression) 的等价性。
其次，默认读者已经了解 PDA (non-deterministic Pushdown Automaton) 的概念，及其和 CFG (Context-free Grammar) 的等价性。
如果你不知道，可以通过列出的全称来查阅相关资料，总之，这里需要频繁用到 DFA=NFA=RE，PDA=CFG 的性质。
问题背景
起因是 JustinRochester 考了我一个问题：
证明，DFA 和 CFG 的交是 CFG
想了想，干脆直接 PDA 同时模拟 DFA 和 CFG 即可，不过我一拍脑袋想的办法，加之没有图示，加上当时前额叶可能还没长出来，说的不清不楚，特此写一篇博客。
引理 1：PDA 可以模拟 DFA/NFA
这个引理是显然的，PDA 其实就是一个带栈的 NFA，不用栈即可。
引理 2：双状态单栈操作的 PDA 和单状态单栈操作的 PDA 等价
这里的名词定义是笔者自己定义的，仅在本文中有效。
单状态单栈操作的 PDA 就是读者所了解的普通的 PDA。
这里引入一个双状态单栈操作的 PDA 的定义，与普通 PDA 的不同仅在，从一个状态扩充到了两个状态，而对栈的操作仍然相同，一次只能做压入/弹出/压入并弹出/无操作。
主要扩充 2 个内容，以及修改一下起始状态和接受状态：
\(G = \Big(Q, \Sigma, \Tau, \delta, [u_0,v_0], F\Big)\)：
- \(Q\) 中的每个元素是一个二元组 \([u,v]\)，是两个状态；
- \(\delta\) 中的转移是从一个二元组状态经过读取输入和取出栈顶字符后 到 另一个二元组状态并压入字符的过程（注意字符可以是空串 \(\epsilon\)）；
- \([u_0,v_0]\) 是起始二元组状态；
- \(F\) 是一个接受二元组状态集。
下面证明双状态单栈操作的 PDA 与单状态单栈操作的 PDA 等价。
（\(\Leftarrow\)）
这个方向没什么好证的，二元组状态 \([u,v]\) 保持 \(u=v\) 即可。
（\(\Rightarrow\)）
构造 PDA \(G' = (Q', \Sigma, \Tau, \delta', q_0, F')\)：
- 对 \(G\) 中的每个二元组状态 \([u,v] \in Q\)，在 \(G'\) 中有 \(q_{u,v} \in Q'\)；
- 对 \(G\) 中的每个转移函数 \(\delta\big([u,v], x, \alpha \big) = ([m,n],\beta)\)，在 \(G'\) 中有 \(\delta\big(q_{u,v}, x, \alpha \big) = (q_{m,n},\beta)\)，其中 \(\alpha, \beta \in \Tau \cup {\epsilon}\)；
- 对 \(G\) 中的起始二元组状态 \([u_0,v_0]\)，在 \(G'\) 中有起始状态 \(q_{u_0,v_0}\)；
- 对 \(G\) 中的接受二元组状态 \([u_f,v_f] \in F\)，在 \(G'\) 中有接受状态 \(q_{u_f,v_f} \in F'\)。
显然，该单状态单栈操作的 PDA 通过扩充状态集就可以模拟双状态单栈操作的 PDA（扩充到 \(n \times m\) 个状态即可），故引理 2 得证。
下证：正则语言和上下文无关语言的交集是双状态单栈操作的 PDA 所能接受的语言
即证明：双状态单栈操作的 PDA 可以模拟 DFA 和 PDA 同时运行的结果。
这里有一个前提，就是 DFA 和 PDA 的字符集 \(\Sigma\) 相同。
对于正则语言 R，存在 DFA \(M(Q_1, \Sigma, \delta_1, q_1, F_1)\) 识别 R；
对于上下文无关语言 G，存在 PDA \(N(Q_2, \Sigma, \Tau, \delta_2, q_0, F_2)\) 识别 G；
接下来构造双状态单栈操作的 PDA \(S = \Big(Q_3, \Sigma, \Tau, \delta_3, [q_1,q_2], F_3\Big)\) 识别 R\(\cap\)G：
- 若状态 \(u \in Q_1 \land v \in Q_2\), 则 \([u,v] \in Q_3\)；
- 若状态 \(\delta_1(u,\alpha)=m\ \land\ \delta_2(v,\alpha,\tau)=(n,\theta)\), 则 \(\delta_3([u,v],\alpha, \tau) = ([m,n], \theta)\), 其中 \(\alpha \in \Sigma\) 且 $ \tau,\theta \in \Tau$；
- 若状态 \(u_f \in F_1\ \land\ v_f \in F_2\)，则 \([u_f,v_f] \in F_3\)。
显然，此时就相当于同时模拟了 M 和 N，并且 M 和 N 都接受时，S 才接受。
又由引理 2，可知存在一个普通的 PDA 与 S 等价，又一直存在 CFG 与普通 PDA 等价，故正则语言和上下文无关语言的交集仍然是一个上下文无关语言，原命题得证！
\( Q.E.D! \)
后记
这里聪明的读者可能会思考：双状态单栈操作的 PDA 是否也可以模拟 CFL 和 CFL 的交？
我们知道 PDA 不具有封闭性，两台 PDA 就可以模拟 TM (Turing Machine) 了，所能接受的语言大相径庭，而有一个例子（JustinRochester 告诉我的），\(0^n1^n2^m\) 和 \(0^m1^n2^n\) 的交是 \(0^n1^n2^n\)，显然前二者是上下文无关的，而第三者在《计算理论导引》一书上，已经可以用 CFL 泵引理证明非上下文无关了。
那么笔者的双状态单栈操作的 PDA 在此时会出什么问题呢？显然，问题就出在不断重复提到的“单栈操作”上，如果是两个 PDA 同时运行，他们都需要用到栈。而如果是一个 PDA 一个 DFA，栈只被 PDA 独享，后者不需要用到栈。
后记 2
笔者还想到了一种废弃的判定 DFA 是否接受的办法，即在运行 DFA 前，压入一个特殊字符，在 DFA 接受后，弹出这个特殊字符，表示 DFA 接受。经过思考之后，好像并不适用于交问题，但是也许可以用在 RE 和 CFL 的连接语言上。