构造一个用于语言 L = {ww | w ∈ {0,1}} 的图灵机。

在这里，我们将学习如何为语言 L = {WW | W属于{0, 1}} 创建一个图灵机。这意味着我们将只使用两个字符 0 和 1 来构建一种语言。w 是一个字符串。所以如果 w = 10110，那么图灵机将接受字符串 z = 1011010110。

为了解决这个问题，我们将采用这种方法。首先是找到字符串的中点，我们将 0 转换为 x，将 1 转换为 y。持续进行此操作，直到所有 0 和 1 都分别转换为 x 和 y。现在，我们到达了字符串的中点。所以我们的第一个目标完成了。

现在，将中点左侧的所有 x 和 y 转换为 0 和 1。现在字符串的前半部分是 0 和 1 的形式。字符串的后半部分是 x 和 y 的形式。

现在，再次从字符串的开头开始。如果遇到 0，则将其转换为 x 并向右移动，直到到达后半部分，如果在这里找到 x，则将其转换为空白 (B)。然后返回，直到找到 x 或 y。我们将它右边的 0 或 1 分别转换为 x 或 y，并相应地将字符串后半部分的 x 或 y 转换为空白 (B)。

继续此操作，直到将字符串左半部分的所有符号转换为 x 和 y，并将字符串右半部分的所有符号转换为空白。如果一部分完全转换，但另一部分仍有一些符号未更改，则该字符串将不被接受。如果我们没有在后半部分找到与前半部分的 0 或 1 分别对应的 x 或 y，则该字符串也将不被接受。

状态转换图

更新于：2020年1月3日

5K+ 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告