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

在这里，我们将了解如何为语言 L = {WW^r |W 属于 {0, 1}} 构建图灵机。所以这表示一种语言，我们只使用两个字符 0 和 1。w 是一个字符串，w^r 是它的逆序。所以如果 w = 10110，那么 w^r 将是 01101。因此，图灵机将接受字符串 z = 1011001101。

为了解决这个问题，我们将使用这种方法。首先检查第一个符号，如果它是 0，则使用 y 替换它，如果它是 1，则使用 x 替换它。然后转到字符串的末尾。所以最后一个符号与第一个符号相同。我们也根据它用 x 或 y 替换它。之后，再次回到从开始替换的符号旁边的位置，并重复上述相同过程。我们必须记住，由于 w^r 是 w 的逆序，因此两者将具有相同数量的符号。每次替换字符串开头处的第 n 个符号时，都替换结尾处的相应第 n 个符号。

状态转换图

Arnab Chakraborty

更新于: 2020年1月3日

5K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

立即开始