大门|大门-CS-2005 |问题55

考虑语言：

L1 = {anbncm | n, m > 0} 
L2 = {anbmcm | n, m > 0} 

以下哪项陈述是错误的？ （A） L1∩ 二语是一种与语境无关的语言 （B） l1u-L2是一种与上下文无关的语言 （C） L1和L2是上下文无关的语言 （D） L1∩ 二语是一种语境敏感的语言 答复: （A） 说明： 我们可以使用一个堆栈识别给定语言的字符串。这些语言是上下文无关的，因此也是上下文敏感的。 因为CFL在Union属性下是封闭的，所以给定语言的Union也将是上下文无关的。 但在交叉属性下，CFL不是封闭的，所以两个CFL的交叉可能不是CFL。 如果L1和L2是两种上下文无关的语言，那么它们的交叉点是L1∩ L2不是上下文无关的，因为我们无法通过一个堆栈来识别结果语言的字符串：

L1={a ^N B ^N C ^M |n>0和m>0}和L2={a ^M B ^N C ^N |n>0和m>0}

L3=L1∩ L2={a ^N B ^N C ^N |n>0}不是上下文无关的。

因此，选项（a）是错误的。

看见 维基百科页面 闭包属性。 这个问题的小测验