2

我花了整整一个月的时间来解决这个问题，因为我是从练习一书中得到的，我很想知道如何在图灵机上写这个；我真的很想学这个。请问有人可以提供帮助吗？

考虑您登录的最后两个字母（如果两个字母相同，请选择拉丁字母中的下一个字母作为您的第二个符号）。编写一个能够识别语言 Stretch(x+1) 的图灵机。这是所有字符串的语言，这些字符串包含两个字母的连续出现字符串，后跟“*”，然后是另一个字母字符串，其中每个字母出现 x+1 次，其中第一个字符串中出现了一次的字母。这里，x = 1。机器的输入是 a、b、* 的非空字符串。例如，如果字母是“a”和“b”（并且 x=1），则 aba*aabbaa、bb*bbbb 和 baab*bbaaaabb 在该语言中，但 abb*abbb 不是。

如果您能帮助我，我将不胜感激。

4

1 回答 1

3

为每个唯一字母使用一个堆栈（在您的示例中为两个堆栈）。这不是正式写的或任何东西，但您所要做的就是提供一种算法来证明 TM 可以解决问题。

F1:
FOREACH letter DO
  IF letter = '*' THEN F2
  ELSE push letter twice onto its respective stack

F2:
FOREACH letter DO
  IF tape is empty THEN F3
  IF respective stack is empty THEN *fail state*
  ELSE pop respective stack

F3:
IF both stacks are empty THEN *accept state*
ELSE *fail state*

明白了吗？TM 证明很有趣。

编辑：针对您的其他帖子，如果您不了解如何构建 TM 证明，您需要阅读一些关于一般证明的内容。我建议Michael Sipser 的 Intro to Theory of Computing。在为该文本掏出一条胳膊和一条腿后，您可以翻到第 137 页以了解有关 TM 的所有信息。

于 2010-11-07T02:22:14.217 回答