在图灵机中,合并输入符号和删除空格的最快算法是什么



我正在寻找一种算法,它可以让我从中间包含空格的输入字符串的最右边开始,合并输入符号,这样就没有空格了。

例如,0 _ 0 _ 0=000。

我知道在状态图中显示的方法,当输入符号之间没有空格时,可以合并输入符号,但我想知道在没有空格的情况下有什么好的方法。

我所说的删除中间输入符号的更多例子(目前假设字母表为1,0(:

  • 示例输入:10011输出:101
  • 示例输入:11101101输出:1110

我不确定你只需要两个字母符号就能做到这一点。基本思想是使用字母表中的附加(空白(符号,并在磁带上移动时将其用作跳过字符。

如果您知道如何解决初始问题,例如0_1_0,您可以将只有0和1的任意磁带转换为空白磁带,然后从那里开始。

最新更新