我必须确定一种语言（例如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