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