math - 每种常规语言都是可判定的

Question

我试图证明每一种常规语言都是可判定的。

因此，为了证明我试图证明我可以从确定性有限自动机（DFA）转移到图灵可判定机器。

所以我不确定如何构建一个模拟原始自动化（DFA）的图灵机。

状态（在自动机和图灵机中）当然会相似..但我不知道如何继续..

提前致谢。石然

Answer 1

这不可行吗：输入磁带带有要识别的单词，后跟来自输入字母表之外的一些字母#。对于 DFA 的每个状态 q，您都有一个带有转换的图灵机状态 q：

input letter -> tape operation,  next state, write symbol

c for each input letter -> move right, the state the DFA reaches from state q with letter c, write c
# -> STOP ACCEPT or STOP REJECT, depending on whether q is final in the DFA.