题目描述

图灵机是由数学家艾伦·麦席森·图灵（1912～1954）提出的一种抽象计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人们进行数学运算一个抽象模型。

实验背景

它由四部分「硬件」组成：一条无限长的纸带、一个读写头、有限长度的状态转移表（有限多个状态）、一个状态寄存器。纸带可以划分成一个个连续的格子，每一个格子上有且只有一个字符。

在此系列实验中，我们要通过设计状态转移表来让图灵机实现特定的功能。

在本题目中，我们对图灵机有如下约定：

• 图灵机的状态应是一个长度不超过 $100$ 的仅包含可见字符的字符串，初始状态为 q0。
• 读写头初始位置在纸带的第 $0$ 格，纸带向正负两个方向无限延伸。纸带每一个有且只有一个 ASCII 可见字符，初始字符为 B。
• 图灵机的输入从纸带的第 $0$ 格开始，向正向延伸。
• 每一时刻，图灵机将按照状态转移表的规则，根据当前状态和当前读写头位置读取的字符，对纸带进行写操作，控制读写头的移动并且在状态之间跳转。当图灵机的状态跳转至 qa 时，认为其停止。
• 由于难以判断图灵机能否停机，测试中图灵机最多模拟 $10000$ 步。若步骤超过 $10000$ 步，则认为图灵机不停机。
• 状态转移表中的一条规则是一个五元组，分别为当前状态、当前字符、写入字符、读写头移动方向、下一状态。当前状态、下一状态是长度不超过 $100$ 的仅包含可见字符的字符串；当前字符和写入字符是ASCII可见字符；读写头移动方向为 L、R、N 三个字符中的一个，分别表示读写头向左、向右移动和不移动。
• 每一条状态转移规则占一行，各部分之间用逗号格开。如，q0,1,#,R,q1。

题目

第三个实验要求设计一个可以完成任意位二进制加法的图灵机。

输入格式

图灵机的输入格式如下：

(若干 0/1)+(若干 0/1)=

除非加数为 $0$，保证两加数不会出现前导零。

以下输入不合法：

=
+=
+
11+=
+11=
1+1
11=

输出格式

图灵机的输出格式如下：

#######(若干0/1)B####

其中，若干$0/1$的位置必须从输入中的 = 号右侧开始，以 B 结尾。# 为任一 ASCII 可见字符。不应含有前导零。

1100+1100=

1100+1100=11000B…

0+0=

FB100BcWW…

1+0=

1+0=1B…

1111+11=

1111+11=10010B…

11+1010=

##+####=1101B…

数据范围与提示

数据保证有大量的图灵机可以在 $10000$ 步中完成计算。

由于平台限制，我们使用一个伪交互题的方式提交状态转移表。请将写好状态转移表用程序通过标准输出输出，在最前和最后分别添加一行 --- 和 ===。

程序输出的状态转移表示例：

---
q0, 1, #, R, q1
q1, #, #, R, q0
===

当然，你也可以写一个程序，帮你自动生成状态转移表。

对于不知道如何使用程序输出状态转移表的同学，请按下面的示例，用 Python 3 语言提交状态转移表。

print("""---
q0, 1, #, R, q1
q1, #, #, R, q0
===""")

本题源于中国科学院大学（UCAS）计算机科学导论课实验一。