我必须确定一种语言（例如L = {a ^ n b ^ m c ^ s | 0 <= n <= m <= s}）是否是常规的，无上下文的，递归的，递归可枚举的或者都不是。
我知道如何确定一种语言是否规则（找到有效的DFA或正则表达式）或无上下文（找到一个有效的PDA或无上下文语法）;我知道递归语言有一个总是停止的图灵机，并且一个递归可枚举的语言有一个可能不会停止的图灵机。
所以问题是：是否有一个快速的标准来确定语言是递归还是递归可枚举或两者都没有？例如，我不需要构建一个PDA来理解语言是无上下文的，我不能通过它需要一个堆栈来看待它;有没有类似的快速解决问题的方法（希望能省去构建图灵机的麻烦）？
没有结构方法来检查语言是递归还是递归可枚举。实际上有一个非常酷的证据表明，对于任何能够识别递归语言的自动机，至少有一种RE语言不在R中，自动机也可以接受;它是用于显示存在不可判定问题的对角化参数的变体。
你证明一种语言的主要方式是RE而不是R是证明语言在RE中（也许是通过为它定义TM），然后减少RE中的已知问题而不是R来解决该问题。例如，如果您可以通过将其转换为问题实例来证明停止问题的任何实例都可以解决，那么您知道它不能具有递归解决方案，并且如果您使用TM进行后续操作你知道语言在RE中的语言。在RE中你有一种语言但不是R.
没有结构方法来检查语言是递归还是递归可枚举。实际上有一个非常酷的证据表明，对于任何能够识别递归语言的自动机，至少有一种RE语言不在R中，自动机也可以接受;它是用于显示存在不可判定问题的对角化参数的变体。
你证明一种语言的主要方式是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} 没有上下文，因为它只有一个比较（不常规）
希望这可以帮助