沒有上下文的遞歸可枚舉語言的示例

Question

什麼是不是上下文無關的遞歸可枚舉語言的簡單示例？我的教科書在明確提供這樣一個例子時非常糟糕。

要清楚這不是一個hmk問題。

Answer 1

遞歸可枚舉類確實非常廣泛。它包括任何語言，其中有一個圖靈機可停止和接受語言中的任何字符串（不要求圖靈機停止，如果給定的字符串不在語言中）。因此遞歸可枚舉語言的一個例子是在給定輸入上停止的圖靈機的描述（在一些形式中）的集合H。由於有一個模擬任何圖靈機（所謂的通用圖靈機）的圖靈機，當然可以識別有效的字符串，但是停機問題的不可判定性表明H不是遞歸的。

任何圖靈機可以表示爲一個不受限制的形式語法（因此形式語法是一個圖靈機的描述）。 （如果不是強大的話，實際的構造是單調乏味的，我不建議嘗試它）。因此，停止問題是不可判定的任何圖靈機都定義了一種不含上下文（甚至是上下文敏感）的遞歸可枚舉語言。

在更迂腐水平，這是不上下文上下文敏感的語言的實例包括：

{ ap | p is prime } 
{ anbncn | n ≥ 0 } 
{ α | α ∈ {a, b, c}* ∩ #a(α) = #b(α) ∩ #b(α) = #c(α) } 

（在最後一個，#x(α)是在α的x出現的次數。在其它。字，它是包含相同數量的字符串集合as，bs和cs。）