递归可枚举语言

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

递归可枚举语言

递归可枚举语言在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。形式定义. 递归可枚举语言定义：设"S" ⊆ Σ*为一个语言，"E"是一个枚举器，若"L"（"E"） = "S"，则称"E" 枚举了语言"S"。若存在这样的"E"，"S"就称为递归可枚举语言。注意，枚举器"E"可以以任意的顺序枚举语言"L"（"E"），而且"L"（"E"）中的某个串可能会被"E"多次重复地打印。图灵可识别语言定义：设formula_1是一台图灵机，若在输入串formula_2上formula_1运行后可进入接受状态并停机，则称formula_1接受串formula_2。formula_1所接受的所有字符串的集合称为formula_1所识别的语言，简称formula_1的语言，记作formula_9。设formula_10是一个语言，若存在图灵机formula_1使得formula_12，则称图灵机formula_1 识别formula_14，且formula_14称为图灵可识别语言。两个定义的等价性. 下列定理揭示了递归可枚举语言和图灵可识别语言的联系。定理：一个语言是图灵可识别的，当且仅当它是递归可枚举的。证明：若有枚举器"E"枚举语言"S"，构造一个图灵机"M"如下： "M" = 对于输入ω 注意当ω ∉ "S"时，"M"可能永不停机，但"M"所接受的语言集合恰好是"S"，所以"M"识别了"S"。假设我们有图灵机"M"识别语言"S"，构造一个枚举器"E"如下： "E" = 忽略输入显然，这样构造的枚举器"E"最终输出的语言恰好就是"S"。注意"S"中的字符串并没有在"E"中按字典序输出，而且同一个串可能会被"E"输出多次，但根据枚举器的定义，这些都是允许的。闭包性质. 递归可枚举语言在下列运算下是闭合的。就是说，如果"L"和"P"是两个递归可枚举语言，则下列语言也是递归可枚举的：注意递归可枚举语言不闭合于差集和补集之下。图灵可识别语言与图灵可判定语言的关系. 注意图灵可识别语言和图灵可判定语言的区别：若formula_14是图灵可识别语言，则只需存在一台图灵机formula_1，当formula_1的输入formula_23时，formula_1一定会停机并进入接受状态；当formula_1的输入formula_26时，formula_1可能停机并进入拒绝状态，或者永不停机。而若formula_14是图灵可判定语言，则必须存在图灵机formula_1，使得对于任意输入串formula_30，formula_1总能停机，并根据formula_2 属于或不属于 formula_14分别进入接受或拒绝状态。并不是所有的语言都是图灵可识别的，可以证明存在图灵不可识别语言。

基金会

欧几里得空间

王旭烽

杭州大学

五权宪法

尚武文化

龙生九子

电台司令

锑

碲

铋

澳大利亚大奖赛