为语言 L = {ww | w ∈ {0,1} 构建图灵机。
c++server side programmingprogramming更新于 2024/10/2 19:53:00
在这里我们将看到如何为语言 L = {WW |W 属于 {0, 1}} 构建图灵机。因此，这代表了一种语言，我们将只使用两个字符 0 和 1。w 是一个字符串。因此，如果 w = 10110，那么图灵机将接受字符串 z = 1011010110。
为了解决这个问题，我们将使用这种方法。首先要找到字符串的中点，我们将 0 转换为 x，将 1 转换为 y。经过不断的这样做，当所有 0 和 1 分别转换为 x 和 x 时，就会到达一个点。现在，我们位于字符串的中点。所以，我们的第一个目标完成了。
现在，将中点左侧的所有 x 和 y 转换为 0 和 1。现在字符串的前半部分是 0 和 1 的形式。字符串的后半部分是 x 和 y 的形式。
现在，再次从字符串的开头开始。如果有 0，则将其转换为 x 并向右移动直到到达后半部分，在这里如果我们找到 x，则将其转换为空白(B)。然后遍历回来直到找到 x 或 x。我们将其右侧的 0 或 1 分别转换为 x 或 y，并相应地将其在字符串后半部分的 x 或 y 转换为空白(B)。
继续执行此操作，直到将字符串左侧部分的所有符号转换为 x 和 y，将字符串右侧的所有符号转换为空白。如果一个部分完全转换，但另一半中的一些符号保持不变，则该字符串将不被接受。如果我们在后半部分中没有找到与前半部分中的 0 或 1 对应的 x 或 y。那么字符串也不会被接受。
状态转换图
