用 CFL 解释正则语言的并集和交集

我们知道有限自动机(FA)接受的语言称为常规语言，下推自动机(PDA)接受的语言称为上下文无关语言(CFG)。

关闭联盟下的节能灯

CFL 是上下文无关语言的简称。这里的 CFL 如下 -

G = (V, Σ, R, S) 使得L(G)= L(G1) ∪ L(G2)

因此，

• V = V1 ∪ V2 ∪ {S}（三组不相交）

• Σ = Σ1 ∪ Σ2

• R = R1 ∪ R2 ∪ {S → S1|S2}

正则语言与 CFG 的联合

如果所有常规语言都是上下文无关的，那么两个结果的并集也是上下文无关的语言。

示例

让我们 L1 = {0*1*} 是常规语言并且

        L2 = {0^n1^n |n>=0} 是上下文无关的

并令 L=L1 ∪ L2 是这两种语言的并集。在问题中，给定 L = {0*1*} 是正则语言。

我们知道每种常规语言都是上下文无关的。所以，显然我们可以说两者的结合总是导致上下文无关的语言。因为两种上下文无关语言的结合是一种上下文无关语言。

因此证明。

正则语言与 CFG 的交集

我们知道所有常规语言都是 CFG 的子集。

联合操作很容易理解，我们也证明了正则语言与上下文无关语言的联合生成了上下文无关语言。

现在来到十字路口，

常规语言和上下文无关语言的交集总是导致上下文无关语言。

示例

L1 = {0*1*} 是一种常规语言并且

L2 = {0^n1^n |n>=0} 是 CFL

两种语言的交集如下 -

L=L1∩L2

结果如下 -

L={0^n1^n | n>=0} 是上下文无关的。

所以，最后得出结论，正则语言和上下文无关语言的交集产生了上下文无关语言。