CFL 在计算理论 (TOC) 中是指上下文无关语言。现在让我们了解 CFL 是如何在 Union 下关闭的。
CFL 在 UNION 下关闭
如果 L1 和 L2 是 CFL，则 L1 U L2 也是 CFL。
让 L1 和 L2 由上下文无关文法 (CFG) 生成。
G1=(V1,T1,P1,S1) and G2=(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 由 CFG G1=(V1,T1,P1,S1) 生成而不失一般性下标 G1 的每个非终端与 a1。
定义 CFG，G 生成 L1* 为 -
G=(v1 U {S}, T1, P1 U {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。