语言L的车床= {a ^ m b ^ n a ^ m b ^ n ∣ m，n≥0}

Question

我在用图灵机制作语言L = {a ^ m b ^ n a ^ m b ^ n ∣ m，n≥0时遇到麻烦]

到目前为止我想的是：

如果我们以空白开头，则该字符串为空，并且应该接受，如果不是，则开始阅读as，我认为用X标记a为a，用Y标记b为OK

Answer 1

为此设计TM的高级策略如下：

1. 检查您是否正在查看a ^ 2k或b ^ 2k形式的字符串（包括空字符串）。在任何这些情况下，均应接受暂停。否则，请继续执行步骤2。
2. 切断a对，分别从第一部分和第三部分开始，直到其中一个部分用尽a。如果其中一个用尽而另一个仍具有a，则暂停。否则，请继续执行步骤3。
3. 切断b对，分别从第二部分和第四部分开始，直到其中一个部分用尽b。如果其中一个用尽而另一个仍具有b，则暂停。否则，请停止接受。