这种语言如何不递归？

Question

这个问题在Gate 2009问过。我不明白这是不是递归？

L = {A^米乙^米 C A ^Ñ乙^Ñ | m，n≥0}
L'= {A ⁱ B ^j C ^k | i，j，k≥0}

为什么语言{L交点L'}不递归？

Answer 1

由于“递归”是包含所有较简单的语言类的语言的一般类别，因此该问题可能意味着要被理解为为什么给定语言比递归语言简单—说，它是一种类型1，2或3。否则的问题是没有意义的（因为它是清楚的递归。）

答案可以通过查看在交叉路口中找到：

大号∩L” = {A^米 B ^m C | m≥0}

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