context-free-grammar - 非上下文无关语言，它们是什么？

Question

我在理解非上下文无关语言时遇到了很多麻烦。简单地说，它们是递归可枚举的吗？例如，可以使用图灵机来表示非上下文无关语言吗？它甚至可以被图灵机识别或共同识别吗？

Answer 1

许多非上下文无关语言都是递归的。考虑(a^n)(b^n)(c^n)；用于这种语言的简单图灵机可以在磁带上来回运行，一次删除每个符号中的一个，直到所有符号都被删除或者它先用完一种符号。递归语言也是递归可枚举的。

Chomsky 层次结构是规则的、上下文无关的、上下文相关的、递归的（大致）。在此之外还有一些级别，甚至还有介于这些规范级别之间的级别。