找到接受语言 L = { a^{n!} : n >= 0 } 的线性有界自动机

Question

我需要为语言 L = { a^{n!} : n >= 0 } 构造线性有界自动机。我知道 LBA 的功能，但是，我不知道它如何检查 n!那要在a的力量中。我可能想听听一些建议，因为我在为其开发特定的 LBA 时遇到困难。

Answer 1

线性有界自动机是一种多带非确定性图灵机，其带长度受输入长度的某个固定线性函数的限制。也就是说，必须根据输入的长度提前知道可用的磁带数量，并且该长度必须随输入大小线性增长。如果我们可以为这种语言确定一个图灵机并显示我们确切知道将使用多少磁带作为输入长度的函数，并且该函数是线性的。我们已将 TM 显示为 LBA。

考虑以下多带非确定性图灵机检查输入是否为^(n!)：

如果输入磁带是空的，halt-reject
在第二盘写一个
扫描输入磁带，如果只有一个剩余的实例，则停止接受
否则，回到输入的开头
然后，对于您找到的每 n 个实例，在输入中划掉 (n-1) 个 a 实例。为此，将第二个磁带头向右移动以计数到 n-1，当您到达第二个磁带上最后一个 a 之后的空白时，将您所在的 a 单独留在输入磁带上，重置第二个磁带头, 并继续这个过程
如果您在第 5 步中试图划掉除第 n 个以外的所有实例时最终运行在输入磁带上排除了 a 的实例，则停止拒绝，因为输入磁带更大比（n-1）！但不能被 n.
否则，如果您同时运行个 a 的实例，您完成了第二盘磁带的完整计数，重置两个磁带磁头，将另一个 a 写入第二盘磁带的末尾，然后从步骤 3 开始继续该过程。

以下是此 TM 功能的示例：

Input:  #aaaaaa#    #aaaaaa#    #xaaaaa#    #xaaaaa#
         ^       =>  ^       =>   ^      =>    ^
Second: ########    #a######    #a######    #a######
         ^           ^            ^          ^
       
        #xaxaaa#    #xaxaaa#    #xaxaxa#    #xaxaxa#
   =>       ^    =>      ^   =>       ^  =>   ^
        #a######    #a######    #a######    #aa#####
          ^          ^            ^          ^

        #xxxaxa#    #xxxxxa#
   =>       ^    =>       ^  => halt-accept since we are at the end
        #aa#####    #aa#####    of the tape and looking at a blank
          ^            ^        on the second tape and only one a
                                remains

找到接受语言 L = { a^{n!} : n >= 0 } 的线性有界自动机

Find a linear bounded automaton that accepts the language L = { a^{n!} : n >= 0 }

automata

automata-theory