我必須確定一種語言（例如L = {a^nb^mc^s | 0 < = n < = s = < = s}）是否是規則的，上下文無關的，遞歸的，遞歸的可枚舉的還是它們中的任何一個。如何確定一種語言是遞歸還是遞歸枚舉？
我知道如何確定一種語言是否正常（找到可用的DFA或正則表達式）或上下文無關的（找到一個PDA或上下文無關的語法）;我知道一個遞歸語言有一個圖靈機總是停下來，並且遞歸可枚舉語言有一個圖靈機可能不會停止。
所以問題是：是否有一個快速的標準來確定語言是遞歸的還是遞歸枚舉或兩者都不是？例如，我不必建立一個PDA來理解語言是無上下文的，我不能看到它需要一個棧，有沒有類似的快速方法來解決這個問題（希望能夠省去構建圖靈機的麻煩）？
沒有任何結構性方法來檢查語言是遞歸還是遞歸枚舉。實際上有一個非常酷的證據表明，對於任何能夠識別遞歸語言的自動機，至少有一個不在R中的自動機所接受的RE語言;它是用來表明存在不可判定問題的對角化參數的變體。
您證明語言的主要方式是在RE中，但不是R是爲了證明語言在RE中（可能通過爲它定義TM），然後在RE中減少已知問題但不是R中的問題問題。例如，如果您能夠證明暫停問題的任何實例可以通過將其轉換爲問題實例來解決，那麼您知道它不能有遞歸解決方案，並且如果您使用TM進行跟蹤您知道該語言在RE中。在一起，你有一種語言在RE但不是R.
對於上下文無關語言一個快速的方法是隻看到比較的數量。
在該示例中，參見n<=m和m<=s。所以有兩個比較涉及。所以你可以簡單地告訴它它不是上下文無關的。如果涉及單個比較，則將其稱爲上下文無關語言。
與常規語言的情況相同。這兩個變量之間應該沒有關係，我的意思是說不能有任何比較。例如，考慮語言 - 0^m+n 1^n 0^m。仔細看看只有一個比較是m+n = n+m（推送和彈出的符號）所以它是上下文無關的。
現在看0^n+m 1^n+m 0^m清楚地看到前兩個和後兩個之間的比較。
我花了一些時間弄清楚。但是需要做一些決策。相信我它真的有用。這是常規語言的最後一個例子。 a^n b^2m是有規律的（見有n和m之間沒有比較）和{a^n b^m |n=2m}是上下文無關，因爲它只有一個比較（不規律）
希望這有助於
這肯定不是我所期待的答案:(雖然它澄清了我有一些疑問，所以謝謝！ 因此，如果你必須解決我在開始時寫的例子，你將如何繼續（知道它不是上下文無關的）？ – Jacob 2011-02-16 19:36:36
@ Jacob- Are你確定它不是上下文嗎？ – templatetypedef 2011-02-16 20:04:24