上下文无关语言的闭包性质是什么？

上下文无关语言 (CFG) 的闭包性质如下：

对并集运算封闭

为了证明上下文无关语言对并集运算封闭，考虑两个不同语言 L1 和 L2 的两个起始变量 S1 和 S2。

并集运算的语法如下所示：

S -> S1 | S2

如果两种语言都属于上下文无关语言，那么两种语言的并集也应该属于上下文无关语言。

根据上述定义，如果用户生成 S1 和 S2 字符串或两者，则会生成两种语言的并集。

因此，L1 U L2 ∈ CFL

所以，上下文无关语言对并集运算封闭。

对连接运算封闭

为了证明上下文无关语言对连接运算封闭，该运算考虑两个不同语言 L1 和 L2 的两个起始变量 S1 和 S2。

并集运算的语法如下所示：

S -> S1S2

如果两种语言都属于上下文无关语言，那么两种语言之一的连接也应该属于上下文无关语言。

∀L₁L₂∈CFL

{W₁W₂:W₁∈L₁∈ΛW₂∈L₂}∈CFL

根据上述定义，如果用户为语言 L1 生成 S1 字符串，然后为语言 L2 生成 S2 字符串，那么就会生成两种语言的连接。

因此，结果如下：

{W₁W₂:W₁∈L₁∈ΛW₂∈L₂}∈CFL

所以，上下文无关语言对连接运算封闭。

对 Kleene 星号运算封闭

为了证明上下文无关语言对 Kleene 星号运算封闭，考虑语言 L1 的一个起始变量 S1。

并集运算的语法如下所示：

S -> S1S | ε

如果该语言属于上下文无关语言，那么该语言的 Kleene 星号也应该属于上下文无关语言。

∀L₁∈CFL

根据上述定义，如果用户生成零个或多个字符串（这是 Kleene 星号的定义），那么上下文无关语言对 Kleene 星号运算封闭。

Bhanu Priya

更新于：2021年6月16日

4K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习