具有不等变量的下推自动机

Pushdown automaton with unequal variables

我在想出一个成功接受以下内容的适当自动机时遇到了麻烦：

由任意数量的 {a, b, c}* 以任意顺序组成的字符串，当然，但是 n(a) + n(b) != n(c)

最初，我指定 'x' 被推入任何 'a' 或 'b' 的堆栈，并在 [=20] 时从堆栈中删除 'x's =] 遇到。这将根据需要在两个状态之间循环。当然，如果在 a 和 b 之前有任意数量的 c，这就很复杂了。我显然不能从空堆栈中移除。欢迎任何想法或建议！

这个掌上电脑不简单。您必须使用两个分支（一个用于递增（A 和 B），一个用于递减（C））。诀窍是放置一个栈顶标记并寻找这个标记。如果你击中它坚持下去（不要在你的乐队上走得更远）切换分支并在你的分支上推底片。

下面我用三元组定义了一个转换：(input, pop, push)

例如：

  1. (A,ϵ,#) 表示：从输入中读取 A，不弹出任何内容，将 # 压入堆栈
  2. (ϵ,#,B)表示：什么都不读（停在实际位置，这一步不要再往前了），pop #，push B
  3. (AB,ϵ,X) 表示：读取A或B并压入X

以你的例子为例：

S = starting state
Q1 = "switch branches" state, from here the stack is empty and we move in the branch we need in dependend of the next character read from the input band.
Q2, Q3 = States of the there-is-an-A-or-B-next branch
Q4, Q5 = States of the there-is-a-C-next branch
Q6 = State of acceptance (the only one. all other states are not accepting)

现在转换：

S -(ϵ,ϵ,#)-> Q1 ' # is our top-of-the-stack-marker

' first branch (for more As and Bs)
Q1 -(AB,ϵ,+)-> Q2 ' for every A or B push a + sign on the stack
Q2 -(AB,ϵ,+)-> Q2
Q2 -(C,+,ϵ)-> Q3 ' for every C consume a + sign
Q3 -(AB,ϵ,+)-> Q2
Q3 -(C,+,ϵ)-> Q3
Q3 -(ϵ,#,#)-> Q1 ' if we reach the top of the stack, return to the Q1 state
Q2 -(ϵ,#,#)-> Q1
Q2 -($,+,+)-> Q6 ' if the input is processed and the stack is not empty => go in the state of acceptance
Q3 -($,+,+)-> Q6 ' if the input is processed and the stack is not empty => go in the state of acceptance

' second branch (for more Cs)
Q1 -(C,ϵ,-)-> Q4 ' for every C push a - sign on the stack
Q4 -(C,ϵ,-)-> Q4
Q4 -(AB,-,ϵ)-> Q5 ' for every A or B consume a - sign
Q5 -(AB,-,ϵ)-> Q5
Q5 -(C,ϵ,-)-> Q4
Q5 -(ϵ,#,#)-> Q1
Q4 -(ϵ,#,#)-> Q1
Q4 -($,-,-)-> Q6 ' if the input is processed and the stack is not empty => go in the state of acceptance
Q5 -($,-,-)-> Q6 ' if the input is processed and the stack is not empty => go in the state of acceptance

逻辑描述：

我们在栈上压入一个#符号来检测栈顶。 现在我们在两个"zones"中操作。与 Cs 相比，第一个区域处理正数的 A 和 B，与 Cs 相比，另一个区域处理负数的 As 和 B。

我们正在处理 Stack 中的三个标志：

  1. '# = 顶部标记
  2. '+ =读到的As和Bs多于Cs
  3. '- =读到的Cs比As或Bs多

第一个转换是从起始状态到新的起始状态。此转换仅用于将顶部标记推入堆栈的原因。再也不会达到新的原始起始状态。 新的起始状态是开关，每次我们击中堆栈的顶部标记时都会被击中。从这个状态，我们正在访问依赖于下一个 A 和 B 或 C 的区域。

我希望能解释清楚。所描述的自动机应该会给你一个好主意。我认为其中有一点错误，但如果你按照这个想法做对了，那么你就可以修复它:)

我用在线模拟器构建了描述的自动机来测试它。你可以找到它here。这个模拟器使用 epsilon 作为输入波段的初始化并且什么也不做......所以它有点混乱。我通过单击 "Bulk Testing" 旁边的绿色箭头添加了一些可以 运行 的测试。

我们可以尝试将问题简化一些。你想要n(a) + n(b) != n(c)。在没有其他限制的情况下，这意味着就 PDA 而言，as 和 bs 是无法区分的；所以这种语言与 n(a) != n(c) 相同（如果我们让 PDA 假装 b 是 a）。如果我们可以为这种更简单的语言制作 PDA，我们就完成了。

我们可能会问目标是确定性的还是任何 PDA。并非所有上下文无关语言都具有确定性 PDA，因此，一般而言，PDA 指的是非确定性 PDA。如果我们假设这对这个问题没问题，我们可以通过写下等价条件 n(a) < n(c) or n(a) > n(c) 来进一步简化条件 n(a) != n(c)。这让我们的生活变得更轻松了，因为现在我们只需要为 n(a) < n(c) 想出一个 PDA，然后我们就完成了：我们语言的一个 PDA 将非确定性地分支到两个 PDA，一个用于每个方向.

那么我们如何获得 n(a) < n(c) 的 PDA？好吧，我们可以从 n(a) = n(c) 的 PDA 开始，而不是在没有输入和空堆栈的情况下接受，而是在没有输入和堆栈的情况下接受，表明 c 比 a 多秒。 n(a) = n(c) 的 PDA 是什么样子的？我们需要一个策略。诀窍是使用堆栈来跟踪 运行 差异 n(c) - n(a)，如下所示：

  • 如果n(c) - n(a) = 0，栈为空，栈顶符号Z，栈底符号
  • 如果 n(c) - n(a) > 0，堆栈包含 n(c) - n(a) 个 c 的实例。
  • 如果 n(c) - n(a) < 0，堆栈包含 n(a) - n(c) 个 a 的实例。

为了接受 n(a) = n(c)，我们读取 as 和 cs 并耗尽输入。然后，我们看看栈顶有什么：

  • 如果堆栈为空，n(a) = n(c)（参见上面的第一个项目符号）
  • 如果堆栈顶部有一个 c，则 n(a) < n(c)（参见上面的第二个项目符号）
  • 如果堆栈顶部有一个 a，n(a) > n(c)（参见上面的第三个项目符号）

为了接受 n(a) = n(c)，每当我们在堆栈顶部看到堆栈底部符号 Z 时，我们就不确定地转换到新的接受状态 q。

为了接受 n(a) < n(c)，每当我们在堆栈顶部看到 c 时，我们就不确定地转换到新的接受状态 q。在这种情况下，如果你想接受一个空栈，你可以在接受状态下清空栈。

为了接受 n(a) > n(c)，每当我们在堆栈顶部看到 a 时，我们就不确定地转换到新的接受状态 q。在这种情况下，如果你想接受一个空栈，你可以在接受状态下清空栈。

注意我们可以一起处理 n(a) < n(c) 和 n(a) > n(c)；我们甚至不需要预先非确定性地分支。这是刚刚描述的 PDA 的示例实现：

Q    x    s    Q'    s'
///////////////////////
// count a           //
///////////////////////
q0   a    Z    q0    aZ
q0   a    a    q0    aa
q0   a    c    q0    e
///////////////////////
// count c           //
///////////////////////
q0   c    Z    q0    cZ
q0   c    a    q0    e
q0   c    c    q0    cc
///////////////////////
// move to accepting //
///////////////////////
q0   e    a    q     a
q0   e    c    q     c
///////////////////////
// clear stack       //
///////////////////////
q    e    a    q     e
q    e    c    q     e

您需要为 b 添加转换规则，就像我们为 a 所做的那样，但是 b 与 a 在其他方面没有区别，因此应该这样对待.

以上table中的栏目如下：

  • Q：转换起源的状态
  • x：导致转换的输入字母符号，如果转换不消耗输入，则为空字符串e
  • s: 最顶层的栈符号
  • Q'：转换终止的状态
  • s': 转换时用什么替换最顶层的堆栈符号

例如，行

q0   a    Z    q0    aZ

编码一个可以描述如下的转换：

From state q0 with the bottom-of-stack symbol Z topmost on the stack, consume input symbol a and transition to state q0, pushing an a on top of Z.