递归可枚举文法
（重定向自0 型文法）
| 递归可枚举语言 | |
|---|---|
| 术语名称 | 递归可枚举语言 |
| 英语名称 | recursive enumerable language |
| 递归可枚举文法 | |
|---|---|
| 术语名称 | 递归可枚举文法 |
| 英语名称 | recursive enumerable grammar |
| 图灵可识别语言 | |
|---|---|
| 术语名称 | 图灵可识别语言 |
| 英语名称 | Turing-recognizable language |
| 0型语言 | |
|---|---|
| 术语名称 | 0型语言 |
| 英语名称 | type-0 language |
| 0型文法 | |
|---|---|
| 术语名称 | 0型文法 |
| 英语名称 | type-0 grammar |
递归可枚举语言(recursive enumerable language)指一种形式语言是该语言字母表上全部可能单词的一个递归可枚举的子集。图灵机可识别语言指语言可以被 Turing 机枚举出所有可能的串。两种说法等价。
对应的递归可枚举文法是一种生成文法，与 Chomsky 生成语法理论中的0型文法(type-0 grammar)相同。递归可枚举意味着任意合理的递归都能出现在这一生成文法中，仅要求生成式左侧至少含有一个非终结符。不施加任何其他限制，也称为无限制文法或短语结构文法。
定义
以下三种定义等价：
- 递归可枚举语言：对给定字母表，其上全部单词构成的一个递归可枚举的子集。
- Turing 机可识别语言：对给定符号表，存在一个 Turing 机可以枚举语言中的全部合法字符串。
- Turing 机可接受语言：对给定符号表，存在一个 Turing 机可以在接受语言中的全部合法字符串时在有限步内停机。
性质
递归可枚举语言的：
都仍然是递归可枚举的。
Turing 机等价
递归可枚举语言中的生成相当于无限制地从 Turing 机纸带上擦除符号并写入生成的符号。这一过程中可能写入任意的更短或更长的符号串。
尽管这一定义中属于这个语言的能在有限步内停机，但无法保证不属于这一语言的字符串是在有限步内停机并拒绝还是不停机， 因此对任意给出的字符串和任意递归可枚举语言，判定是否属于这一语言相当于判定这个串的字符是否可以通过给定规则在 Turing 机上停机，本身等价于 Turing 停机问题。