递归可列举语言

编辑
本词条由“匿名用户” 建档。
在数学、逻辑学和计算机科学中,如果一种形式语言是该语言字母表上所有可能的词语集合中的一个可递归可列举的子集,也就是说,如果存在一台图灵机可以列举出该语言的所有有效字符串,那么该语言就被称为递归可列举(也是可识别的、部分可解的、半可解的、图灵可接受的或图灵可识别的)。可递归列举的语言在乔姆斯基形式语言的等级体系中被称为0型语言。所有正规的、无语境的、对语境敏感的和递归的语言都是可递归列举的。所有可递...

递归可列举语言

编辑

在数学、逻辑学和计算机科学中,如果一种形式语言是该语言字母表上所有可能的词语集合中的一个可递归可列举的子集,也就是说,如果存在一台图灵机可以列举出该语言的所有有效字符串,那么该语言就被称为递归可列举(也是可识别的、部分可解的、半可解的、图灵可接受的或图灵可识别的)。可递归列举的语言在乔姆斯基形式语言的等级体系中被称为0型语言。所有正规的、无语境的、对语境敏感的和递归的语言都是可递归列举的。所有可递归枚举语言的类别被称为RE。定义递归可列举语言有三个等价的定义。递归可列举语言是在该语言的字母表上所有可能的词的集合中的一个递归可列举的子集。递归可列举语言是一种形式语言,对于这种语言存在一个图灵机(或其他可计算的函数),可以列举出该语言的所有有效字符串。请注意,如果语言是无限的,所提供的枚举算法可以被选择,以避免重复,因为我们可以测试数字n产生的字符串是否已经为一个小于n的数字产生。

递归可列举语言

递归可列举语言是一种存在图灵机(或其他可计算函数)的形式语言,当输入该语言中的任何字符串时,它将停止并接受,但当输入不在该语言中的字符串时,它可能停止并拒绝或永远循环。这与递归语言形成对比,后者要求图灵机在所有情况下都能停止。所有正规的、无语境的、语境敏感的和递归的语言都是可递归列举的。波斯特定理表明,RE与它的补数co-RE一起,对应于算术层次的xxx层。

递归可列举语言的例子

编辑

终止图灵机的集合是可递归列举的,但不是递归的。事实上,人们可以运行图灵机并接受机器是否停止,因此它是可递归列举的。另一方面,这个问题是不可判定的。其他一些非递归可列举的语言包括。

后对应问题

编辑

死亡率(可计算性理论)Entscheidungsproblem封闭属性递归可列举语言(REL)在下列操作下是封闭的。也就是说,如果L和P是两个可递归列举的语言,那么下面的语言也是可递归列举的。递归可列举语言在集差或补足下是不封闭的。集合差分{displaystyleL}{displaystyleP}是可递归枚举的,如果P{displaystyleP}是递归的。是递归的。如果L{displaystyleL}是可递归的。是可递归列举的,那么L的补集L{的补集}的补集是可递归列举的,当且仅当L{displaystyleL}的补集也是递归的。也是递归的。

内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/164067/

(3)
词条目录
  1. 递归可列举语言
  2. 递归可列举语言的例子
  3. 后对应问题

轻触这里

关闭目录

目录
尊敬的全球百科用户,全球百科新系统上线了!新增排名保障卡、词条年卡,更有增值功能——百度排名保障包年服务,详情访问“glopedia.cn/261472/”关注公众号可联系人工客服。