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 的所有信息。