Permalink为L={aibjck |i*j=k；i，j，k构造一个图灵机≥ 1}

先决条件—— 图灵机 在给定的语言中，L={a ^我 B ^J C ^K |i*j=k；i、 j，k≥ 1} ，其中“a”、“b”和“c”的每个字符串都有一定数量的a，然后是一定数量的b，然后是一定数量的c。条件是这3个符号中的每一个都至少出现一次。”“a”和“b”可以出现多少次，但“c”的出现次数必须等于“a”和“b”出现次数的乘积。假设字符串以“$”结尾。

示例——

Input: a a b b b c c c c c c         Here a = 2, b = 3, c = 2 * 3 = 6  Output: ACCEPTED          Input: a a b b c c c       Here a = 2, b = 2, c = 3 but c should be 4 Output: NOT ACCEPTED 

使用的方法- 从左边扫描输入。

1. 首先，将“a”替换为“X”，然后向右移动1步。然后跳过所有a，向右移动。
2. 当指针到达第一个“b”停止点时。将一个“b”替换为“Y”，然后向右移动，跳过所有中间b，并对应于替换的“b”，现在将一个“c”替换为“Z”，然后向左移动。
3. 现在向左移动，跳过所有的“Z”和“b”。
4. 当指针到达最近的“Y”时，向右移动。
5. 如果指针指向“b”，则重复步骤2至4，否则如果指针指向“Z”，则向左移动，同时将所有“Y”替换为“b”，并跳过所有a。
6. 当指针指向最近的“X”时，向右移动一步。
7. 如果指针仍指向“a”，则重复上述所有步骤，否则如果指针位于“b”，则向右移动，跳过所有“b”和“Z”。
8. 当到达$时，向左移动。字符串被接受。