0^n1^n2^n的Python图灵机

Question

我得到的指令是“创建一个图灵机来识别0^n1^n2^n形式的字符串。这意味着如果字符串的格式正确，图灵机将停止在空白磁带上，而如果它的格式不正确，它将停止在非空白单元格上”。在

我知道图灵机器是如何工作的，但不知道如何用Python实现它。我在网上找到的任何例子都很复杂，有多个类和所有东西。我不认为这对我的申请是完全必要的。在

我发现此问题的以下psuedocode：

On input string w
   while there are unmarked 0s, do
      Mark the left most 0
      Scan right to reach the leftmost unmarked 1;
         if there is no such 1 then crash
      Mark the leftmost 1
      Scan right to reach the leftmost unmarked 2;
         if there is no such 2 then crash
      Mark the leftmost 2
   done
   Check to see that there are no unmarked 1s or 2s;
      if there are then crash
   accept

然而，在我看来，实现这个精确的伪代码最终不会成为一个合法的图灵机器。我是不是走错了路？欢迎任何指导。在

Answer 1

对于我来说，pesudo代码似乎是正确的，如果您向我们展示一个可以接受的不太复杂的问题的示例，我不知道python中的TM究竟接受什么。在