通过构建枚举器证明 L∈RE
Proof that L∈RE by building an enumerator
根据定义：A language is Turing-recognizable if and only if some enumerator enumerates it
Given Lmn = {< M,N > | L(M) ∩ L(N) ≠ ∅, where M is a basic Turing machine, and N is an NFA}
Prove that Lmn ∈ RE by building an enumerator that enumerates it.
首先，我们可能应该将N转换为DFA，以确定输入的是NAccept还是Reject。
我们对M一无所知，所以它可以在X步后停止，或者无限循环，那么我们如何满足L(M) ∩ L(N) ≠ ∅的限制？
无需将 NFA 转换为 DFA。由于无法知道图灵机是否会停止，我们也可以对 NFA 做同样的事情。
首先，可以确定给定的字符串是否是 TM 的编码。 NFA 也是如此。您还可以轻松定义字母表中字符串的顺序，例如空字符串、a、b、aa、ab、ba、bb、...
枚举器可以这样定义。
- 运行 对于 m = 1,2,...,infinity
- 获取字母表中的第 m^th 个字符串。
- 检查它是否是有效的 TM。转到第 4 步，否则转到第 1 步。
- 如果它是 n = 1,2,..,m 的有效 TM 运行。当我们到达 m 时，转到步骤 1。
- 获取字母表中的第 n^th 个字符串
- 检查它是否是有效的NFA，如果不是则转到步骤4。
- 对字母表中所有前 m 个字符串进行最多 m 步的 TM 和 NFA 模拟。如果他们都接受相同的字符串，打印
<TM, NFA>
- 转到第 4 步
如果他们在某个时候接受相同的字符串 (L(M) ∩ L(N) ≠ ∅)，这台机器将打印所有 <TM, NFA>。
根据定义：A language is Turing-recognizable if and only if some enumerator enumerates it
Given Lmn = {< M,N > | L(M) ∩ L(N) ≠ ∅, where M is a basic Turing machine, and N is an NFA}
Prove that Lmn ∈ RE by building an enumerator that enumerates it.
首先，我们可能应该将N转换为DFA，以确定输入的是NAccept还是Reject。
我们对M一无所知，所以它可以在X步后停止，或者无限循环，那么我们如何满足L(M) ∩ L(N) ≠ ∅的限制？
无需将 NFA 转换为 DFA。由于无法知道图灵机是否会停止，我们也可以对 NFA 做同样的事情。
首先，可以确定给定的字符串是否是 TM 的编码。 NFA 也是如此。您还可以轻松定义字母表中字符串的顺序，例如空字符串、a、b、aa、ab、ba、bb、...
枚举器可以这样定义。
- 运行 对于 m = 1,2,...,infinity
- 获取字母表中的第 m^th 个字符串。
- 检查它是否是有效的 TM。转到第 4 步，否则转到第 1 步。
- 如果它是 n = 1,2,..,m 的有效 TM 运行。当我们到达 m 时，转到步骤 1。
- 获取字母表中的第 n^th 个字符串
- 检查它是否是有效的NFA，如果不是则转到步骤4。
- 对字母表中所有前 m 个字符串进行最多 m 步的 TM 和 NFA 模拟。如果他们都接受相同的字符串，打印
<TM, NFA> - 转到第 4 步
如果他们在某个时候接受相同的字符串 (L(M) ∩ L(N) ≠ ∅)，这台机器将打印所有 <TM, NFA>。