双向下降自动机如何工作？

Question

请注意，通过“双向下降自动机”，我的意思是下降自动机，可以在输入胶带上两种方式移动其读数。

我最近有一个问题，即确定乔姆斯基层次结构中双向PDA的计算能力。我不完全理解双向PDA，但是我可以看到如何在输入上读取两个方向的能力，它可以处理表单$ l = {0^n 1^n 2^n 的语言} $。我不能肯定地这么说，但这似乎使它足够强大，可以至少处理上下文敏感的语言。

这一切都是一个猜测，因为我不知道它们是如何工作的。有人可以解释双向PDA如何运行的过程，甚至在我的榜样中也许？

更新：

该模型是对俯卧撑自动机的概括，因为在输入胶带上允许双向运动，该磁带被假定为具有终结器。

Answer 1

双向PDA可以接受规范上下文敏感语言$ {0^{n} 1^{n} 2^{n} | n geq 1 } $。这样的自动机可以通过检查$ 0^{i} 1^{j} $的最大前缀是否具有$ i = j $，然后使用堆栈，然后它可以清空堆栈，并检查是否最大的后缀$ 1^{j} 2^{k} $的表格中有$ j = k $，再次使用堆栈。因此，$ cfl subsetneq l（2pda）$。

更详细地说，2向PDA将从从左到右读取，以确定为0个符号，将一个0的0读取到输入胶带上读取的每个符号。如果它读取任何0个符号并在找到1个符号之前找到2个符号，则它会崩溃。当它到达1时，它会更改状态，并开始读取所有1个符号，直到达到2。如果在执行此操作时读取0符号，则会崩溃。它从堆栈中弹出一个0符号，每1个符号在输入胶带上读取。如果，当它到达第一个2时，堆栈是空的，则PDA将胶带头移至输入胶带的末端。否则，它会崩溃。如果它遇到任何0或1，则崩溃。然后，它读取从左到右的输入胶带，每2个在输入胶带上读取2。当它达到1时，它会切换状态并开始读取1s并弹出2s。如果到达0时，堆栈为空，则将接受字符串。

如果输入字符串不是0的字符串，其次是1s，然后是2s；如果最长的前缀为0和1s，则它将崩溃。如果1s和2s的最长后缀不在规范的Cfl $ {1^{n} 2^{n} } $中，那将会崩溃。在这种情况下，倒带胶带的能力使您可以通过将PDA串在一起并将磁带倒入之间。

因此，双向PDA所接受的语言在交叉点上微不足道地关闭，这是普通PDA所接受的语言共享的属性。