turing-machines - 图灵机 - 学习技巧

Question

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

Consider the last two letters of your login (if both letters are the same, please pick the next letter in the Latin alphabet as your second symbol). Write a Turing Machine that will recognise the language Stretch(x+1). This is the language of all strings that contain a continuous string of occurrences of the two letters, followed by ‘*’, followed by another string of letters with x+1 occurrences of the each letter where there was a single occurrence in the first string of letters. Here, x = 1. Input to the machine is non-null strings of a, b, *. As an example, where the letters are ‘a’ and ‘b’ (and x=1) aba*aabbaa, bb*bbbb and baab*bbaaaabb are in the language, but abb*abbb is not. You may assume that you have subroutines for writing 0 in the first cell and deleting the rest of the tape and for writing 1 in the first cell and deleting the rest of the tape.

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

Answer 1

为每个唯一的字母使用一个堆栈(在您的示例中为两个堆栈)。这不是正式编写的或任何东西，但您所要做的就是提供一个算法来证明 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's Intro to Theory of Computing .在为该文本掏出一只胳膊和一条腿后，您可以翻到第 137 页以了解有关 TM 的所有信息。