recursion - 递归语言的属性

Question

有人可以帮我解决这些问题吗？

以下递归语言的哪些属性是可递归枚举的？

L_1 = { L | L 是正则}

L_2 = { L | L 包含一些 A 的 < A >，它在序列 000111000 上成立}

L_3 = { L | L 包含一些 A 的 < A >，它在 epsilon 上成立 }

Answer 1

递归语言（也称为可判定语言）是存在图灵机的语言，它接受该语言并在接受和不接受的词上都停止。

递归可枚举语言是存在图灵机的语言，它在接受字符串时停止。

因此，递归语言集是递归可枚举语言集的子集。

所以，如果我正确理解了这个问题，那么 L_1、L_2 和 L_3 是递归可枚举的。