automata - 在下推自动机中以相反的顺序压入/弹出堆栈

Question

所以我正在学习一项关于下推自动机和上下文无关语言的测试，但我陷入了这个结构。

除了我将在下面解释的一个部分之外，这个自动机的每个部分都完全工作正常。

它需要识别的语言是:{ x#y#z#w | {0, 1}+ 中的 x, y, z, w，其中 x ≠ w 且 y ≠ z }。

所以我遇到的问题是将 Xi 与 Wi 进行比较，因为在自动机开始处理 W 时 Wi 的元素是未知的，这是我设计的方式。

如果我存储X的内容，当需要弹出并将每个元素与W的元素进行比较时，它们将以相反的顺序弹出，因此认为000111和111000是相同的字符串，并且PDA将拒绝，当它应该明确接受时(它们是不同的字符串)。这只是一个例子，这也会导致其他输入分析错误。

如果有办法以相反的顺序将 X 的内容压入堆栈，它们将以原始形式弹出，从而使我能够正确比较字符串的内容。

如果有办法在正常压入后反转堆栈的内容，这也能让我找到解决方案。

任何帮助将不胜感激。谢谢。

Answer 1

解决方案有点棘手。

PDA中实际上没有办法反转堆栈的内容。这一切都与 npda 的非决定论性质有关，这使得这个问题可以解决。

从这个更简单的版本开始

L = {x#w: x,w in {0,1}+ and x≠w}.

解决方案:

从状态q开始。对 x 的每个字母推送一个 $ 直到第 k 个字母(k 不重要，选择 k 不确定)，然后检查第 k 个字母并转到 q0 0，则转至 q1；如果是 1，则转至 q1。忽略 x 的其余部分，直到到达 #。为 w 的每个字母弹出一个 $，直到到达堆栈底部(例如 z)。检查 w 的第 k 个字母。如果[您在q0并且字母不是0]或[您在q1并且字母不是 1]接受。

就是这样，魔法!