這種語言如何不遞歸？

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的語言，它可以被確定性下推自動機識別，因此是上下文無關語言。