递归可枚举语言
| 递归可枚举语言 | |
|---|---|
| 术语名称 | 递归可枚举语言 |
| 英语名称 | recursive enumerable language |
| 图灵可识别语言 | |
|---|---|
| 术语名称 | 图灵可识别语言 |
| 英语名称 | Turing-recognizable language |
| 0型语言 | |
|---|---|
| 术语名称 | 0型语言 |
| 英语名称 | type-0 language |
| 0型文法 | |
|---|---|
| 术语名称 | 0型文法 |
| 英语名称 | type-0 grammar |
递归可枚举语言(recursive enumerable language)指一种形式语言是该语言字母表上全部可能单词的一个可递归枚举的子集。图灵可识别语言指语言可以被 Turing 机枚举出所有可能的串。
对应的文法是一种生成文法，与 Chomsky 生成语法理论中的0型文法(type-0 grammar)相同。递归可枚举意味着任意合理的递归都能出现在这一生成文法中，仅要求生成式左侧至少含有一个非终结符。不施加任何其他限制，也称为无限制文法或短语结构文法。