grammar - 这种语言怎么不是递归的？

Question

这个问题是在 Gate 2009 上提出的。我不明白它为什么不是递归的？

L = {A ^m B ^m CA ⁿ B ⁿ | m, n ≥ 0}
L' = {A ⁱ B ^j C ^k | i, j, k ≥ 0}

为什么语言 {L 交集 L'} 不是递归的？

Answer 1

由于“递归”是一种通用的语言类别，包括所有更简单的语言类别，所以这个问题可能被理解为为什么给定的语言比递归语言更简单——比如说，它是一种类型 1、2、或 3. 否则问题没有意义（因为它显然是递归的。）

通过查看交叉点可以找到答案：

L ∩ L' = {A ^m B ^m C | 米≥0}

这只是所有平衡括号后跟 C 的语言，它可以被确定性下推自动机识别，因此是一种上下文无关语言。