查看“︁递归可枚举文法”︁的源代码

[[分类:形式语言]]
[[分类:计算理论]]
{{InfoBox
|name=递归可枚举语言
|eng_name=recursive enumerable language
}}
{{InfoBox
|name=递归可枚举文法
|eng_name=recursive enumerable grammar
}}
{{InfoBox
|name=图灵可识别语言
|eng_name=Turing-recognizable language
}}
{{InfoBox
|name=0型语言
|eng_name=type-0 language
}}
{{InfoBox
|name=0型文法
|eng_name=type-0 grammar
}}
'''递归可枚举'''语言('''recursive enumerable''' language)指一种[[形式语言]]是该语言字母表上全部可能单词的一个[[递归可枚举]]的子集。'''<ins>图灵</ins>机可识别'''语言指语言可以被 [[Turing 机]]枚举出所有可能的串。两种说法等价。

对应的'''递归可枚举'''文法是一种[[生成文法]]，与 [[Chomsky 生成语法理论]]中的'''0型文法'''('''type-0 grammar''')相同。递归可枚举意味着任意合理的递归都能出现在这一生成文法中，仅要求生成式左侧至少含有一个非终结符。不施加任何其他限制，也称为'''无限制文法'''或'''短语结构文法'''。

== 定义 ==

以下三种定义等价：

* '''递归可枚举'''语言：对给定字母表，其上全部单词构成的一个递归可枚举的子集。
* '''Turing 机可识别'''语言：对给定符号表，存在一个 Turing 机可以枚举语言中的全部合法字符串。
* '''Turing 机可接受'''语言：对给定符号表，存在一个 Turing 机可以在接受语言中的全部合法字符串时在有限步内停机。

== 性质 ==

递归可枚举语言的：

* [[Kleene 闭包]]
* [[连接]]
* [[并集]]
* [[交集]]

都仍然是递归可枚举的。

== Turing 机等价 ==

递归可枚举语言中的生成相当于无限制地从 Turing 机纸带上擦除符号并写入生成的符号。这一过程中可能写入任意的更短或更长的符号串。

尽管这一定义中属于这个语言的能在有限步内停机，但无法保证不属于这一语言的字符串是在有限步内停机并拒绝还是不停机，
因此对任意给出的字符串和任意递归可枚举语言，判定是否属于这一语言相当于判定这个串的字符是否可以通过给定规则在 Turing 机上停机，本身等价于 [[Turing 停机问题]]。