CFG 和 DFA 的交集为 CFG

起因是我队友问了我一个问题：

我后面看了一下那题，等价的题意是求一个 CFG 和 DFA 交集，能识别的最短串的长度。

虽然编译原理没学过，但是我在可计算理论上有学到过：有个结论是，CFG 和 DFA 的交集也是 CFG ；而 CFG 推导出的最短串可以用队列+贪心的方法求解。但并没有学过如何对于给定的 CFG 和 DFA，求出交集的 CFG。

我在国内某搜索引擎上并没有找到答案，最终在外网找到了一个比较靠谱的 答案 。所以我这篇笔记就是记录一下这个算法的流程。

定义

DFA

我们称一个确定型有穷状态自动机（Deterministic Finite Automaton, DFA）是一个五元组 \(\left<Q, \Sigma, \delta, q_0, F\right>\) ，其中五个参数依次为状态集、字符集、转移函数（\(\delta: Q\times \Sigma\to Q\)）、起始状态和接收状态集。

在 DFA 的计算过程中，我们从初始状态 \(q_0\) 出发，不断读入字符 \(c\in \Sigma\) ，并通过转移函数 \(\delta(q_i, c)=q_{i+1}\) 不断更新状态。当读入完成后，若状态 \(q_e\in F\) 则接受该读入，否则拒绝该读入。

对于一个 DFA \(M\) ，我们称所有能被 \(M\) 识别的字符串为 \(M\) 的语言 \(L(M)\) ，即 \(L(M)=\{s|\delta(q_0, s)\in F\}\) 。

这里我们拓展了转移函数的意义：当字符串 \(s\) 的长度大于 \(1\) 时，我们将其划分为最后的字符 \(c\) 和前缀 \(t\) ，我们定义 \(\delta(q,s)=\delta(\delta(q, t), c)\) 。

CFG

我们称一个上下文无关文法（Context-Free Grammer, CFG）是一个四元组 \(\left<V, \Sigma, R, S\right>\) ，其中五个参数依次为变元集、终结符集、产生式规则（\(R: V\to (V\cup \Sigma)^*\)）和起始变元。

其中，为了方便描述，产生式规则往往采用 A->BCdefG 的形式描述。其中产生式规则的左侧必须为变元。

在一个 CFG \(G\) 的计算过程中，我们从初始变元 \(S\) 出发，不断地选择当前串中的一个变元 \(A\) ，然后选择一个左侧为 \(A\) 的产生式规则进行替换：将 \(A\) 修改成产生式规则的右侧的串。

当我们将串推导成只含终结符的串 \(s\) 时，我们称该 CFG 接受串 \(s\) ，同理可定义语言 \(L(G)=\{s|S\Rightarrow^+ s\wedge (\forall c\in s\to c\in \Sigma)\}\) 。

其中 \(\Rightarrow\) 符号表示推导，即上述使用产生式规则的一次替换过程；而 \(\Rightarrow^+\) 符号表示若干正整数次的推导。

CNF

我们称一个 CFG 满足乔姆斯基范式（Chomsky Normal Form, CNF）指该 CFG 的产生式规则仅含有以下三种形式的产生式规则：

1. 由起始变元推导出空串：\(S\to \varepsilon\)
2. 由一个变元推导出两个变元：\(A\to BC\)
3. 由一个变元推导出一个终结符：\(A\to a\)

很显然，对于任何一个 CFG \(G\) ，必然存在 CNF \(G'\) 使得 \(L(G')=L(G)\)

CFG 可以模拟 DFA 的计算

我们常说 DFA 的描述能力是 CFG 描述能力的一个子集。即对于所有 DFA 语言构成的集合 \(S_1\) 和所有 CFG 语言构成的集合 \(S_2\) 必然有 \(S_1\subset S_2\) 。

一个比较经典的证明方法是，我们可以通过广义非确定型有穷状态自动机（Generalized Nondeterministic Finite Automaton, GNFA）将一个 DFA 转化成等价的正则语言 \(R\) 。

而我们众所周知：

1. 空语言为正则语言。
2. \(c\) 为正则语言（\(c\in \Sigma\)）。
3. \(\varepsilon\) 为正则语言。
4. 若 \(R_1, R_2\) 为正则语言，则 \(R_1R_2\) 为正则语言。
5. 若 \(R_1, R_2\) 为正则语言，则 \(R_1\cup R_2\) 为正则语言
6. 若 \(R\) 为正则语言，则 \((R)\) 为正则语言。
7. 若 \(R\) 为正则语言，则 \(R^*\) 为正则语言。

于是我们可以对于该正则语言 \(R\) 构造对应的 CFG：

1. 若 \(L(R)=\varnothing\) 则 \(P=\varnothing\) 。
2. 若 \(L(R)=\{c\}, c\in \Sigma\) 则 \(P=\{S\to c\}\) 。
3. 若 \(L(R)=\{\varepsilon\}\) 则 \(P=\{S\to \varepsilon\}\) 。
4. 若 \(R=R_1R_2\) 则分别构造 \(S_1, S_2\) 能表示 \(R_1, R_2\) ，然后添加产生式 \(S\to S_1 S_2\) 。
5. 若 \(R=R_1\cup R_2\) 则分别构造 \(S_1, S_2\) 能表示 \(R_1, R_2\) ，然后添加产生式 \(S\to S_1\) 和 \(S\to S_2\)。
6. 若 \(R=(R_1)\) 则构造 \(S_1\) 表示 \(R_1\) ，然后添加产生式 \(S\to S_1\) 。
7. 若 \(R=R_1^*\) 则构造 \(S_1\) 表示 \(R_1\) ，然后添加产生式 \(S\to S_1S\) 和 \(S\to \varepsilon\) 。

很显然，两者描述的是同一种语言。