用 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}是上下文无关的。
所以，最后得出结论，正则语言和上下文无关语言的交集产生了上下文无关语言。