Permalink为语言L={wwr | w&in；{0，1}构造图灵机

先决条件—— 图灵机 语言L={ww ^R |w&in；{0，1}}表示一种只使用两个字符的语言，即0和1。语言的第一部分可以是0和1的任意字符串。第二部分与第一部分相反。把这两部分结合起来，就形成了一条细绳。任何属于这一类别的字符串都将被该语言接受。字符串的开头和结尾用$符号标记。

例如，如果第一部分w=1 1 0 0 1，则第二部分w ^R = 1 0 0 1 1. 很明显，w ^R 是w的倒数，所以字符串1010101是给定语言的一部分。

示例——

Input : 0 0 1 1 1 1 0 0
Output : Accepted
Input : 1 0 1 0 0 1 0 1 
Output : Accepted

基本表征——

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

使用的方法- 首先检查第一个符号，如果是0，则用Y替换，如果是1，则用X替换。然后走到绳子的末端。所以最后一个符号和第一个相同。根据它的不同，我们也用X或Y来代替它。 现在再次从起点回到符号替换旁边的位置，重复上述相同的过程。

需要注意的一件重要事情是 ^R 与w相反，两者的符号数相等。每次替换字符串开头的第n个符号时，都要替换字符串结尾对应的第n个符号。

• 第一步： 如果符号为0，则将其替换为Y并向右移动，转到状态Q2 如果符号为1，则将其替换为X并向右移动，转到状态Q1
• 第二步： 启用“按符号移动”，则“按符号移动”保持不变 如果符号为1，则将其替换为1并向右移动，保持相同状态 ——————————————————————- 如果符号为X，则将其替换为X并向右移动，转到状态Q3 如果符号为Y，则将其替换为Y并向右移动，转到状态Q3 如果符号为$，则用$替换并向右移动，转到状态Q3
• 第三步： 如果符号为1，则将其替换为X并向左移动，转到状态Q4 如果符号为0，则将其替换为Y并向左移动，转到状态Q5
• 第4步： 如果符号为1，则将其替换为1并向左移动 如果符号为0，则将其替换为0并向左移动 保持不变
• 第五步： 如果符号为X，则用X替换，然后向右移动 如果符号为Y，则用Y替换，然后向右移动 转到状态Q0
• 第6步： 如果符号为X，则用X替换，然后向右移动 如果符号为Y，则用Y替换，然后向右移动 转到状态Q6 其他的 转至步骤1
• 第7步： 如果符号为X，则将其替换为X并向右移动，保持相同状态 如果符号为Y，则将其替换为Y并向右移动，保持相同状态 如果符号是$用$替换它并向左移动，字符串被接受，转到最终状态Q7