c++ - 如何设计下推自动机

Question

我将如何设计一个接受平衡括号和括号的 PDA，例如 ([][])，我很难开始。我需要帮助为这个问题编写转换函数。任何帮助表示赞赏

Answer 1

我通常不会为他们完成某人的全部作业，但现实情况是，即使我这样做，它也不会对你有太大帮助，除非你真的了解这些东西是如何工作的，可悲的事实是，大多数学校一开始就教不好。

让我们考虑一下这个 PDA 是如何工作的，暂时忘记状态和转换等等：当我们的 PDA 获得输入时，它应该像这样工作：

• 如果没有输入：
  • 如果栈顶是空的（这通常由一些特殊的值来表示$，比如这个例子），那么我们的 PDA 接受这个字符串：它是一个适当平衡的括号和括号字符串。
  • 否则我们进入错误状态。该字符串不是正确平衡的括号和括号字符串。
• 如果输入是 an(或 a [，则将输入压入堆栈并查看下一个输入字符。
• 如果输入是 a)那么：
  • 如果栈顶是(弹出栈顶，再看下一个输入。
  • 否则，进入错误状态。该字符串不是正确平衡的括号和括号字符串。
• 如果输入是 a]那么：
  • 如果栈顶是一个[弹出栈顶的状态，再看下一个输入。
  • 否则，进入错误状态。该字符串不是正确平衡的括号和括号字符串。

现在，知道了我们的 PDA 必须做什么，让我们尝试考虑如何更正式地描述我们的 PDA。我们将假设：

• Τhe 组有效输入符号 Σ = { (, ), [and ]}
• 初始堆栈符号 Z =$
• Τhe 组有效堆栈符号 Γ = { (, [} ∪ Z
• 状态集 Q = { q0, ACCEPT, REJECT }
• 初始状态 q0。

使用类似于http://en.wikipedia.org/wiki/Pushdown_automaton上描述的符号来进行 PDA 状态转换，我们可以考虑状态以及事物如何流动：

• (q0, ε, top= $, ACCEPT, nil)这告诉我们的 PDA：当您处于状态 q0 并且没有更多输入并且堆栈顶部$进入 ACCEPT 状态时，堆栈保持不变。

• (q0, ε, top= (, REJECT, nil)这告诉我们的 PDA：当您处于状态 q0 并且没有更多输入并且堆栈顶部(进入 REJECT 状态时，堆栈保持不变。

• (q0, ε, top= [, REJECT, nil)这告诉我们的 PDA：当您处于状态 q0 并且没有更多输入并且堆栈顶部[进入 REJECT 状态时，堆栈保持不变。

• (q0, (, top=top, q0, push ()这告诉我们的 PDA：当您处于状态 q0 并且输入是 a(时，无论堆栈顶部是什么，进入状态 q0 并将 a 压(入堆栈。

• (q0, [, top=top, q0, push [)这告诉我们的 PDA：当您处于状态 q0 并且输入是 a[时，无论堆栈顶部是什么，进入状态 q0 并将 a 压[入堆栈。

• (q0, ), top= (, q0, pop)这告诉我们的 PDA：当你处于状态 q0 并且输入是 a)并且栈顶是 a(时，进入状态 q0，并弹出栈顶.

• (q0, ), top= [, REJECT, nil)这告诉我们的 PDA：当你处于状态 q0 并且输入是 a)并且堆栈的顶部是 a 时，[然后转到 REJECT 堆栈，保持堆栈不变。

• (q0, ), top= $, REJECT, nil)这告诉我们的 PDA：当你处于状态 q0 并且输入是 a)并且堆栈的顶部是 a 时，$然后转到 REJECT 堆栈，保持堆栈不变。

• (q0, ], top= [, q0, pop)这告诉我们的 PDA：当你处于状态 q0 并且输入是 a]并且栈顶是 a[时，进入状态 q0，并弹出栈顶.

• (q0, ], top= (, REJECT, nil)这告诉我们的 PDA：当你处于状态 q0 并且输入是 a]并且堆栈的顶部是 a 时，(然后转到 REJECT 堆栈，保持堆栈不变。

• (q0, ], top= $, REJECT, nil)这告诉我们的 PDA：当你处于状态 q0 并且输入是 a]并且堆栈的顶部是 a 时，$然后转到 REJECT 堆栈，保持堆栈不变。

我们可以使用更多状态来实现这一点，但有趣的是，一个“处理”状态就足够了。

您可能还需要注意，根据您的讲师，您可能不需要明确添加 REJECT 状态，尽管这样做是一种很好的形式。

我希望这有帮助。

Answer 2

这可能会帮助您入门：

bool check_and_pop(char c) {
  if (top() == c) {
    pop();
    return true;
  }
  return false;
}

int check_input() {
 char c;
 while ((c = getc())) {
  switch (c) {
    case '(': case '{': case '[': push(c); break;
    case ')': 
      if (!check_and_pop('(')
       return REJECT;
      break;
    case '}':
      if (!check_and_pop('{')
       return REJECT;
      break;
    // ...
 }
 // end of input, check the stack to accept/reject
 if (stack_size() == 0)
    return ACCEPT;
 else
    return REJECT;
}