algorithm - O(n*log(n)) 图灵机，正好有 1 个磁带用于给定单词中的 "equal number of a' s 和 b”？

Question

我需要为语言 L = {w| 构建一个只有 1 个磁带的 TM w 是一个单词中 a 和 b 的个数相同，例如:abba, aababb}

TM 必须只有 1 个磁带并且必须在 O(nlog(n)) 时间内运行。我知道如何在 O(n^2) 中做到这一点，但我不知道如何使它成为 nlog(n)。

例如，如果我有输入 w = "aaaa....abbbbb....bb"，其中 w = a ^ n/2 * b ^n/2(这是最坏的情况)，那么我将每次都向后走(为每个 b 删除每个 a)，所采取的步骤大小为 1,2,3,4.....n。 Sum(1 到 n) 是 O(n^2)...

帮助？有什么想法吗？

Answer 1

在高层次上，我正在考虑的解决方案是按从左到右的顺序处理单词。任何时候，都有一个已经处理过的词的前缀，和一个没有被处理过的词的后缀。出租delta是 a 的数量前缀中的s减去b的个数s，磁带在每次迭代开始时看起来像这样:

<big-endian abs(delta)><sign(delta)><suffix>
                                    ^
                                tape head

要处理下一个字母(即后缀中的第一个字母)，请从 delta 中加/减一个取决于字母是否为 a或 b标志是否为+或 - , 移动 delta 的表示过程中向右一格。最后检查是否delta为零。

使用二进制补码表示可能更容易，其中假定最左边的数字无限重复，但我不确定是否有任何隐藏的障碍。