turing-machines - 有没有解决 "Construct a Turing machine ..."问题的简单方法？

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，则 r 的 NFA 是:

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

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

       e
--->M1--->M2

也就是说，初始状态是 M1 的状态，接受状态是 M2 的状态，所有(以前的)接受状态都有新的空转换M1 到 M2 的(以前)初始状态。

规则 3:如果 r = s + t，对于正则表达式 s, t，以及 M1 和 M2 分别是 s 和 t 的 NFA，那么 r 的 NFA 是:

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

也就是说，初始状态是一个新状态q0，最终状态是M1和M2，还有两个空的添加了从新的初始状态到 M1 和 M2 的(以前的)初始状态的转换。

规则 4:如果 r = s* 用于正则表达式 s，并且 M 是 s 的 NFA >，那么 r 的 NFA 是:

     +------+
     |  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 的接受状态，它将进入停止接受状态，否则进入停止拒绝状态。