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