Permalink为语言L={0n1n2n | n构造一个图灵机≥1}

先决条件—— 图灵机 语言L={0 ^N 1. ^N 2. ^N |n≥1} 表示一种只使用3个字符的语言，即0、1和2。在开始时，语言有一些数字0，后面跟着相等数量的1，然后跟着相等数量的2。任何属于这一类别的字符串都将被该语言接受。字符串的开头和结尾用$符号标记。

示例——

Input  : 0 0 1 1 2 2
Output : Accepted

Input  : 0 0 0  1 1 1 2 2 2 2
Output : Not accepted

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

使用的方法- 首先用X替换前面的0，然后继续向右移动，直到找到1，然后用Y替换这个1。再次，继续向右移动，直到找到2，用Z替换，然后向左移动。现在继续向左移动，直到你找到一个X。当你找到它时，向右移动，然后按照上面相同的步骤。

当你发现一个X紧接着一个Y时，就会出现一个条件。此时，我们继续向右移动，并继续检查所有1和2是否已转换为Y和Z。如果不是，则字符串不被接受。如果我们达到$则字符串被接受。

• 第一步： 将0替换为X并向右移动，转到状态Q1。
• 第二步： 将0替换为0并向右移动，保持相同状态 用Y替换Y并向右移动，保持相同状态 将1替换为Y并向右移动，进入状态Q2。
• 第三步： 将1替换为1并向右移动，保持相同状态 将Z替换为Z并向右移动，保持相同状态 将2替换为Z并向右移动，进入状态Q3。
• 第4步： 将1替换为1并向左移动，保持相同状态 将0替换为0并向左移动，保持相同状态 将Z替换为Z并向左移动，保持相同状态 用Y替换Y并向左移动，保持相同状态 用X替换X并向右移动，进入状态Q0。
• 第五步： 如果符号为Y，则将其替换为Y，然后向右移动，进入状态Q4 否则请转至步骤1
• 第6步： 将Z替换为Z并向右移动，保持相同状态 用Y替换Y并向右移动，保持相同状态 如果符号是$，用$替换它并向左移动，字符串被接受，转到最终状态Q5