为语言L={ww | w&in；{0,1}构造一个图灵机

先决条件—— 图灵机 语言L={ww | w∈ {0，1}}告诉我们，0和1的每一个字符串都属于这种语言。解决这个问题的逻辑可以分为两部分：

1. 找到字符串的中点
2. 找到中点后，我们匹配符号

例如—— 让我们通过一个例子来理解它。让字符串1 0 1 1 0 1，因此w=1 0 1，字符串的形式为（ww）。 我们要做的第一件事就是找到中点。为此，我们将开头的1转换为Y，然后向右移动到字符串的末尾。这里我们把1转换成y。

现在我们的字符串看起来像y0110y。现在向左移动，直到找到一个X或Y。当我们这样做时，将它的0或1右边分别转换为X或Y，然后在右端执行相同的操作。现在我们的字符串看起来像yx1xy。之后，把这些1也转换成yx1xy Y X Y。

此时，您已经实现了第一个目标，即找到中点。现在将中点左侧的所有X和Y分别转换为0和1，使字符串变为1 01 Y X Y。现在，将1转换为Y并向右移动，直到在字符串右侧的开始处找到Y，并将Y转换为空白（用B表示）。现在字符串看起来像y01bxy。

同样地，在0和x后面加上1和Y。之后这个字符串看起来像Y x Y B。现在你没有0和1，字符串右边的所有x和Y都被转换成空格，所以我们的字符串将被接受。

假设： 我们将用X替换0，用Y替换1。

使用的方法- 第一件事是找到字符串的中点，将字符串开头的0或1分别转换为X或Y，并将相应的0或1转换为字符串结尾的X或Y。连续这样做之后，当所有0和1分别转换为X和Y时，达到一个点。此时，您位于字符串的中点。所以，我们的第一个目标实现了。

现在，将中点左侧的所有X和Y转换为0和1。此时，字符串的前半部分是0和1的形式。字符串的后半部分是X和Y的形式。

现在，从字符串的开头开始。如果你有一个0，那么把它转换成X，然后向右移动直到到达下半部分，这里如果我们找到X，那么把它转换成一个空白（B）。然后往回走，直到找到一个X或Y。我们将它右边的0或1分别转换成X或Y，相应地，将它在字符串后半部分的X或Y转换成空白（B）。

继续这样做，直到将字符串左侧的所有符号转换为X和Y，并将字符串右侧的所有符号转换为空白。如果任何一部分已完全转换，但另一半中的某些符号仍保持不变，则该字符串将不被接受。如果在下半部分中没有找到对应于上半部分中0或1的X或Y。那么字符串也将不被接受。

例如：

Input  : 1 1 0 0 1 1 0 0 Output : AcceptedInput  : 1 0 1 1 1 0 1Output : Not accepted

• 第一步： 如果符号为0，则将其替换为X并向右移动 如果符号为1，则将其替换为Y并向右移动， 进入状态Q1和步骤2 ——————————————— 如果符号为X，则将其替换为X，然后向左或向右移动 如果符号为Y，则将其替换为Y并向左移动， 进入状态Q4和步骤5

• 第二步： 如果符号为0，则将其替换为0并向右移动，保持相同状态 如果符号为1，则将其替换为1并向右移动，保持相同状态 ——————————————— 如果符号为X，则将其替换为X，然后向左或向右移动 如果符号为Y，则将其替换为Y，然后向左或向右移动 如果符号为$，则将其替换为$，然后向左移动，转到状态Q2和步骤3

• 第三步： 如果符号为0，则将其替换为X并向左移动，或 如果符号为1，则将其替换为Y并向左移动， 进入状态Q3和步骤4

• 第4步： 如果符号为0，则将其替换为0并向左移动，保持相同状态 如果符号为1，则将其替换为1并向左移动，保持相同状态 ——————————————— 如果符号为X，则用X替换，然后向右或向右移动 如果符号为Y，则用Y替换并向右移动， 转到状态Q0和步骤1

• 第五步： 如果符号为X，则用X替换，然后向左或向右移动 如果符号为Y，则用Y替换并向左移动 进入状态Q4和步骤6

• 第6步： 如果符号为X，则将其替换为0并向左移动，保持相同状态 如果符号为Y，则将其替换为1并向左移动，保持相同状态 – – – – – – – – – — – – – – – – – – – — 如果符号为$，则替换为$，然后向右移动 进入状态Q4和步骤7

• 第7步： 如果符号为0，则将其替换为X并向右移动，转到状态Q6和步骤8 如果符号为1，则将其替换为Y并向右移动，转到状态Q7和步骤9 – – – – – – – – – — – – – – – – – – – — 如果符号是B，用B替换它并向左移动，字符串被接受，转到最终状态Q9

• 第8步： 如果符号为0，则将其替换为0并向右移动，保持相同状态 如果符号为1，则将其替换为1并向右移动，保持相同状态 如果符号为B，则用B替换它并向右移动，保持相同状态 – — – – – – – – – – – – – – – – – – – – 如果符号为X，则用B替换，然后向左移动 进入状态Q8和步骤10

• 第9步：

如果符号为0，则将其替换为0并向右移动，保持相同状态 如果符号为1，则将其替换为1并向右移动，保持相同状态 如果符号为B，则用B替换它并向右移动，保持相同状态 – — – – – – – – – – – – – – – – – – – – 如果符号为Y，则用B替换，然后向左移动 进入状态Q8和步骤10

• 第10步： 如果符号为0，则将其替换为0并向左移动，保持相同状态 如果符号为1，则将其替换为1并向左移动，保持相同状态 如果符号为B，则用B替换并向左移动，保持相同状态 – — – – – – – – – – – – – – – – – – – – 如果符号为Y，则将其替换为Y，然后向右或向右移动 如果符号为X，则用X替换，然后向右移动 进入状态Q5和步骤7