我必须确定一种语言（例如 L={a^nb^mc^s | 0<=n<=m<=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}是上下文无关的，因为它只有一个比较（不是常规的）
希望这可以帮助