turing-machines - 有没有什么简单的方法可以解决“构建图灵机……”的问题？

Question

我理解图灵机的逻辑。当给出图灵机时，我可以理解它是如何工作的以及它是如何停止的。但是当它被要求构建一个图灵机时，它就更加困难了。

有什么简单的方法可以找到以下问题的答案：

Construct a Turing machine a*b* 
Construct a Turing machine a*b*a* 
etc.

我想绘制这些图灵机的图表？有没有什么方法，比如填表然后画图等等？

我在网上搜索了很多关于这个主题的内容。只有答案（只有图表）。没有解释它是如何解决的。

提前致谢

Answer 1

您给出的两个示例是正则表达式，并且确实存在将正则表达式转换为自动机的简单算法方法 - 即 NFA。一旦有了 NFA，您就可以使用简单的结构将它们变成 TM。

将正则表达式转换为 NFA 的算法如下所示：

规则 1：如果r = a对于某个字母符号 a，则 NFA 为r：

       a
--->q0--->(q1)

规则 2：如果r = st对于正则表达式s, t和M1和分别是和M2的 NFA ，那么对于 的 NFA是：str

       e
--->M1--->M2

也就是说，初始状态是 的M1，接受状态是 的，并且从 的所有（以前）接受状态到 的（以前）初始状态M2都有新的空转换。M1M2

规则 3：如果r = s + t, 对于正则表达式s, t, andM1和分别是和M2的 NFA ，那么对于 的 NFA是：str

       e
--->q0--->M1
     | e
     +--->M2

也就是说，初始状态是一个新状态q0，最终状态是M1和的状态M2，并且添加了两个空转换，从新的初始状态到 和 的（以前的）初始M1状态M2。

规则 4：如果r = s*对于正则表达式s，并且M是 的 NFA s，那么对于 的 NFAr是：

     +------+
     |  e   |
     V      |
--->(q0)--->M

也就是说，q0添加了一个新的初始状态，接受状态是 的M，q0并且从 的接受状态添加了新的空M转换q0。

在您的示例中，我们得出 NFA 如下：

a: Rule 1           a
             --->q0--->(q1)

b: Rule 1           b
             --->q0--->(q1)

a*: Rule 4         +-------------+
                   |      e      |
                   V             |
             --->(q0)--->q0'--->(q1)
                      e      a

b*: Rule 4         +-------------+
                   |      e      |
                   V             |
             --->(q0)--->q0'--->(q1)
                      e      b

a*b*: Rule 2      +-----------+
                  |           | e
                  V e      a  |
             --->q0--->q0'--->q1
                  |           |
                e |           | e
                  +-----------+--+
                  |              | e
                  V   e      b   |
                 (q2)--->q2'--->(q3)

a*b*: Rule 2      +-----------+
                  |           | e
                  V e      a  |
             --->q0--->q0'--->q1
                  |           |
                e |           | e
                  +-----------+
                  |           | e
                  V  e    b   |
                 q2--->q3'--->q3
                  |           |
                e |           | e
                  +-----------+--+
                  |              | e
                  V   e      a   |
                 (q4)--->q5'--->(q5)

有了 NFA，TM 可以按如下方式构建：

1. 与 NFA 相同的州
2. 消耗输入的转换将磁带头向右移动。
3. 空的转换根本不移动磁带头。
4. TM 永远不会覆盖其输入。
5. 当 TM 向右移动足够远后遇到空白时，如果它处于 DFA 的接受状态，则进入 halt-accept，否则进入 halt-reject。