为 L = {aibjck | i*j = k; i, j, k ≥ 1} 构造图灵机
c++server side programmingprogramming更新于 2024/10/2 21:16:00
在这里我们将看到如何为语言 L = {AiBjCk | i * j = k; i, j, k ≥ 1} 构造图灵机。因此，这代表了一种语言，我们将只使用三个字符 A、B 和 C。w 是一个字符串。因此，如果 w = AABBBBCCCCCCCC，图灵机将接受它。
为了解决这个问题，我们将使用这种方法。
首先用 x 替换 A 并向右移动。然后跳过所有的 A 并向右移动
当头部到达第一个 B 时，用 y 替换一个 B，然后向右移动，跳过所有中间的 B，对应于替换的 B，现在用 z 替换一个 C 并向左移动。
现在向左移动，跳过途中的所有 z 和 B。
当指针到达最近的 y 时，向右移动。
如果指针指向 B，则重复步骤 2 到 4，否则当指针指向 z 时，向左移动，同时将所有 y 替换为 B 并跳过所有 A。
当指针到达最近的 x 时，向右移动。
如果指针仍指向 A，则重复上述所有步骤，否则当头部位于 y 时，向右移动，跳过所有 y 和z。
当到达 $ 时，向左移动。字符串被接受。
状态转换图
