如何确定一种语言是递归的还是递归可枚举的？
我必须确定一种语言（例如 L={a^nb^mc^s | 0<=n<=m<=s}）是否是常规的、上下文无关的、递归的、递归可枚举的，或者都不是。
我知道如何确定一种语言是正则语言（找到有效的 DFA 或正则表达式）还是上下文无关语言（找到有效的 PDA 或上下文无关语法）；我知道递归语言有一个总是停止的图灵机，而递归可枚举语言有一个可能不会停止的图灵机。
所以问题是：是否有一个快速的标准来确定该语言是递归的还是递归可枚举的，或者两者都不是？例如，我不必构建一个 PDA 来理解一种语言是上下文无关的，我无法通过它需要一个堆栈的事实来看到它；是否有类似的快速方法来解决这个问题（希望可以省去构建图灵机的麻烦）？
I have to determine whether a language (for example L={a^n b^m c^s | 0<=n<=m<=s}) is regular, context-free, recursive, recursively enumerable or none of them.
I know how to determine if a language is regular (find a DFA or regular expression that works) or context-free (find a PDA or context-free grammar that works); I know that a recursive language has a Turing machine that always halts and that a recursively enumerable language has a Turing machine that may not halt.
So the question is: is there a fast criteria to determine whether the language is recursive or recursively enumerable or neither? For example, I don't have to build a PDA to understand that a language is context-free, I can't see it by the fact that it requires one stack; is there a similar fast approach to the problem (that hopefully saves the trouble to build a Turing machine)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
没有结构性的方法来检查语言是否是递归的还是递归可枚举的。实际上有一个非常酷的证明，表明对于任何能够识别递归语言的自动机，至少有一种 R 中没有的 RE 语言该自动机也接受；它是对角化论证的一个变体，用于显示不可判定问题的存在。
证明一种语言在 RE 中而不是 R 中的主要方法是证明该语言在 RE 中（也许通过为其定义 TM），然后将 RE 中的已知问题（而不是 R 中的问题）简化为该问题。例如，如果您可以证明任何停止问题的实例都可以通过将其转换为您的问题的实例来解决，那么您就知道它不可能有递归解决方案，并且如果您用 TM 来跟进这个问题你知道该语言是 RE 语言。总之，您拥有 RE 语言，但没有 R 语言。
There's no structural way to check if a language is recursive versus recursively enumerable. There's actually a really cool proof that says that for any automaton capable of recognizing the recursive languages, there's at least one RE language not in R that the automaton also accepts; it's a variant of the diagonalization argument you use to show the existence of undecidable problems.
The main way in which you prove a language is in RE but not R is to prove the language is in RE (perhaps by defining a TM for it), then to reduce a known problem in RE but not R to that problem. For example, if you can show that any instance of the halting problem can be solved by transforming it into an instance of your problem, you know that it can't have a recursive solution, and if you follow this up with a TM for the language you know that the language is in RE. Together, you have a language in RE but not R.
对于上下文无关语言，一种快速方法就是查看比较的数量。
在示例中，请参阅
n<=m和m<=s。所以涉及到两个比较。所以你可以把它拿出来，简单地告诉它不是上下文无关的。如果涉及单个比较，则将其称为上下文无关语言。常规语言的情况也是如此。这两个变量之间不应该有任何关系，我的意思是说不能有任何类型的比较。例如，考虑语言 -
0^m+n 1^n 0^m。仔细观察，只进行了一次比较，即m+n = n+m（符号的推送和弹出），因此它是上下文无关的。现在看
0^n+m 1^n+m 0^m清楚地看到前2个和后2个之间的比较。我花了一些时间才弄清楚。但需要一些人来做出决定。相信我，它确实有效。这是常规语言的最后一个示例。
a^nb^2m是常规的（参见 n 和 m 之间没有比较），并且{a^nb^m |n=2m}是上下文无关的，因为它有只有一次比较（不定期）希望这有帮助
For context free language one quick method is just see the number of comparisions.
In the example see
n<=mandm<=s. So there are two comparisons involved. So you can take it out simply telling it is not context free. If there is a single comparison involved then call it as a context free language.Same is the case with the regular languages. There should be no relation between the two variables, I mean to say there must not be any kind of comparison. For Example consider the languages-
0^m+n 1^n 0^m. Carefully see that there is just a single comparison made which ism+n = n+m(pushing and popping of the symbols) So it is context free.Now see
0^n+m 1^n+m 0^mclearly see the comparison between the first 2 and the next two.I took some time to figure it out. But it will take some to make the decisions. Believe me it really works. Here is the last example for regular language.
a^n b^2mis regular( See there are no comparisons between n and m) and{a^n b^m |n=2m}is context free as it has only one comparison(not regular)Hope this helps