如何将DFA转换为图灵机？

Question

有了DFA图,我怎样才能将它转换为图灵机？我是否必须找到DFA接受的语言然后创建图灵机？或者有直接的方法吗？

谢谢.

Answer 1

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

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

希望这可以帮助!