computer-science - 无法在输入上写入的固定尺寸磁带图灵机相当于 DFA

我必须证明不能在输入上写入的固定大小磁带的图灵机等价于有限自动机（DFA 或 NFA）。

重要的是要补充一点，磁带的大小是不包括输入的磁带的大小。例如，如果输入的大小是 n，那么磁带的大小将是 k+n，其中 k 是不包括输入的磁带的长度。

我理解主要思想，但很难证明这一点。提前致谢。

标签： computer-scienceautomataformal-languages

我们可以看到，您可以在这样的图灵机上模拟 DFA——图灵机只有只读状态，每一步都消耗一个输入字符——本质上是在图灵机上实现 DFA。这是容易的方向。

证明你可以在 DFA 上模拟 TM 有点困难，但归根结底是只有k可能的地方可以写m字符，m机器的书写字母的大小在哪里。因此，您的 TMk^m除了机器具有的许多状态外，仅具有可能的磁带状态，我们将其称为n. 因此，具有n*k^m状态的 DFA 可以覆盖 TM 的状态。

显然，这是一个手摇证明的草图。你可以从这里拿走。