theory - 如何将 DFA 转换为图灵机？

Question

有了 DFA 的图表，如何将其转换为图灵机？我是否必须找到 DFA 接受的语言，然后创建图灵机？或者有直接的方法吗？

谢谢你。

Answer 1

DFA 中的每个转换读取输入的一个字符，跟随一个转换，然后移动到输入的下一个字符。一旦读取了所有输入，DFA 就接受它是否处于接受状态，否则拒绝。

你可以直接用图灵机模拟这个。通过为 DFA 中的每个状态创建一个状态来构建图灵机的有限状态控制。对于字符 c 上 DFA 中的每个转换，将 TM 中的该转换替换为在读取字符 c 时将一些任意字符写回磁带(无关紧要)然后向右移动磁带头(到磁带上的下一个位置)。然后，对于每个状态，在空白符号上引入从该状态到 TM 的接受状态或 TM 的拒绝状态的转换(基于该状态是接受还是拒绝)。该 TM 通过手动跨输入字符串并最终决定在运行结束时是接受还是拒绝来有效地运行 DFA。

希望这可以帮助!