设计一个接受L = {ww ^ r |的图灵机| w：（0,1）*}？

Question

任何人都可以帮助:(

L = {ww ^ r | （0,1）*}的w元素

就像：pseudo代码中的一样，请检查字符串是否反向等于自己？

任何人都可以提供帮助吗：（（L = {ww ^ r |（0,1）*的w元素}}就像在：pseudo代码中一样，检查字符串是否反向等于自己？

这可以通过PDA或TM完成。我假设您需要确定性TM，因为我假设这是作业。

策略是找到字符串的长度以确定中间位置，然后将磁带视为堆栈，以查看所有字符在该中点之前和之后是否都匹配。

这是可以做到的算法：

对于您直到击中#为止的每两个输入字符，请在最后一个0之后写一个#。这将跟踪“中间”的位置。阅读时标记输入。
1. 如果击中希望在其上找到数字的#，则字符串长度为奇数，因此机器可能会停止并拒绝。
2. 否则，请在您的零字符串后写另一个#。
3. 取消所有输入的标记，并将读取头移至第二个#。
4. 使用零个数，标记输入的右半部分。
5. 从中间开始，出路，标记左侧字符，如果匹配则取消标记右侧。
6. 如果遇到不匹配的一对，则暂停并拒绝。
7. 如果完全到达#，请停止并接受。
8. 例如，让我们看一下输入#101100#（这里的#表示输入的边缘）。读取头位于第一个#。
输入从# 1 0 1 1 0 0 #开始（留出标记空间）
1. 标记前两个输入，最后写一个0：# 1'0'1 1 0 0 # 0
9. 标记接下来的两个输入，最后写一个0：# 1'0'1'1'0 0 # 0 0
10. 标记接下来的两个输入，最后写一个0：# 1'0'1'1'0'0'# 0 0 0
11. 您已经找到第二个#，因此字符串的长度为偶数。在末尾写一个＃：# 1'0'1'1'0'0'# 0 0 0 #
12. 取消所有标记：# 1 0 1 1 0 0 # 0 0 0 #
13. 现在，从第二个#开始，从右侧标记输入，从左侧标记0直到标记所有0：
14. 第一次迭代：# 1 0 1 1 0 0'# 0'0 0 #
15. 第二：# 1 0 1 1 0'0'# 0'0'0 #
16. 第三：# 1 0 1 1'0'0'# 0'0'0'#
17. 您现在知道了字符串的中点（这是未标记输入在标记输入左侧的位置。
18. [从该中点开始，如果匹配，请标记左侧，而取消标记右侧：# 1 0 1'1 0'0'# 0'0'0'#
19. 继续向外工作，以这种方式进行比较：# 1 0'1'1 0 0'# 0'0'0'#
20. [在第三步，我们发现1和0不匹配。停止并拒绝。
21. 我将作为练习来决定如何将该算法转换为TM。

Answer 1

这可以通过PDA或TM完成。我假设您需要确定性TM，因为我假设这是作业。