Bre*_*ren 5 enumerable turing-machines context-free-grammar context-free-language
非上下文无关的递归可枚举语言的简单示例是什么？我的教科书在明确提供这样的例子方面非常糟糕。
需要明确的是，这不是一个 hmk 问题。
递归可枚举的类别确实非常广泛。它包括任何有图灵机的语言，该图灵机将停止并接受该语言中的任何字符串（如果给出的字符串不属于该语言，则不需要图灵机停止）。因此，递归可枚举语言的一个例子是在给定输入上停止的图灵机的描述集合H （以某种形式主义）。由于存在模拟任何图灵机（所谓通用图灵机）的图灵机，因此H中的有效字符串当然可以被识别，但是Halting问题的不可判定性表明H不是递归的。
任何图灵机都可以表示为不受限制的形式语法（因此形式语法是图灵机的描述）。（实际的构造即使不是艰巨的，也是乏味的，我不建议尝试它。）因此，任何停止问题不可判定的图灵机都定义了一种不是上下文无关（甚至上下文敏感）的递归可枚举语言。
在更迂腐的层面上，上下文相关语言并非上下文无关的示例包括：
{ ap | p is prime }
{ anbncn | n ≥ 0 }
{ α | α ∈ {a, b, c}* ∩ #a(α) = #b(α) ∩ #b(α) = #c(α) }
（最后一个是in出现的次数。换句话说，它是包含相同数量s、s 和s 的字符串集合。）#x(α)xαabc