如果 L = P ∩ Q，其中 P 是上下文无关语言 (CFL)，Q 是常规语言，那么 L 在？

Question

context free language P 和 regular language Q 的交集据说总是 context free，但我仍然不明白为什么它是上下文无关的而不是规则的。

这种交集生成的语言具有被 PDA 和 DFA 接受的字符串。由于所有常规语言都是上下文无关的并且它被 DFA 接受，应该'不是 regular language 吗？

Answer 1

字母表中所有字符串的集合是一种常规语言，它与该字母表中任何其他语言 L 的交集恰好是 L.

或者换句话说，不仅仅是接受了哪些字符串。同样相关的是不接受哪些字符串。

Answer 2

以下引理是众所周知的。

引理 2.1 如果 L 是一种没有 e 的上下文无关语言，那么乔姆斯基语法就存在

正常

生成L的表格

引理 2.2 如果 L = ∅ 且 L 是正则则 L 是正则语言的并集 A1,...,An

哪里

每个 Ai 都被具有一个最终状态的 DFA 接受。

我们现在证明我们的主要定理。

定理2.3如果L1是上下文无关语言，L2是常规语言那么L1∩L2是

上下文

免费。

证明：

我们做 e ∈/ L1 和 L2 = ∅ 的情况。我们将所有其他情况留给 reader.

通过引理2.1wecanassumethereexistsaChomskynormalformgrammarG = (N,Σ,S,P)

对于 L1。由引理 2.2 L2 = A1 ∪___∪An where each Ai where each Ai are recognized by

一个 DFA

只有一个最终状态。注意

         L1 ∩L2 = L1 ∩(A1 ∪___∪An) = U(L1 ∩Ai).

                                         i=1

由于 CFL 在 union 下是封闭的（这可以使用 CFG 来证明，所以这不是

作弊）

我们只需要证明 L1 与 DFA 识别的常规语言的交集

与

一个最终状态是 CFL。设 M = (Q,Σ,δ,s,{f}) 是一个只有一个最终状态的 DFA。

我们为L1∩L(M)构建了CFG G0 = (N0,Σ,S0,P0)。

[p,A,r] → [p,B,q][q,C,r]

在 P0.

生产

在 P0

[p,A,q] → σ

if L = P ∩ Q where P is Context Free Language(CFL) and Q is Regular then L is in?