证明 CFL 在 union 和 star 下是封闭的，但在交集下不是？
CFL在计算理论(TOC)中是指上下文无关语言。现在让我们了解CFL是如何在Union下关闭的。
CFL在UNION下关闭
如果L1和L2是CFL，则L1UL2也是CFL。
让L1和L2由上下文无关文法(CFG)生成。
G1=(V1,T1,P1,S1)andG2=(V2,T2,P2,S2)不失一般性下标φ)。
后续步骤完全使用G1或G2的生产。
这样生成的每个单词要么是L1中的单词，要么是L2中的单词。
例子
令L1为回文，定义为：
S->aSa|bSb|a|b|^
令L2为{anbn|n>=0}，定义为-
S->aSb|^
那么联合语言被定义为-
S->S1|S2
S1->aS1a|bS1b|a|b|^
S2->aS2b|^
CFG在KLEENE星下关闭
现在，让我们了解CFG在星下是如何闭合的。
证明
如果L1是CFL，则L1*是CFL。
令L1由CFGG1=(V1,T1,P1,S1)生成而不失一般性下标G1的每个非终端与a1。
定义CFG，G生成L1*为-
G=(v1U{S},T1,P1U{S->S1S{^},S}
每个单词生成^或L1中相同的单词序列。
L1*中的每个单词都可以由G生成。
例子
令L1为{anbn|n>=0}由S->aSb|^定义
然后L1*生成为：
S->S1S|^
S1->aS1b|^
CFG在交叉路口下不闭合
现在让我们了解CFG在交叉点下是如何无法闭合的。
证明
如果L1和L2是CFL，则L1∩L2可能不是CFL。
L1={anbnam|n,m>=0}由CFG生成-
S->XA
X->aXb|^
A->Aa|^
L2-{anbmam|n,n>=0}由CFG生成-
S->AX
X->aXb|^
A->Aa|^
L1∩L2={anbnan|n>=0}这不是CFL。