例如，我将如何设计一个接受平衡括号和括号的PDA ([][])，我很难开始。我需要帮助为此问题编写转换函数。任何帮助不胜感激
我通常不会为他们做别人的全部功课，但现实情况是，当涉及到自动机时，即使我这样做，它也不会对你有多大帮助，除非你真的了解这些东西是如何工作的，可悲的事实是，大多数学校一开始就没有教好它们。
让我们考虑一下这个PDA是如何运作的，暂时忘记状态和转换等等：当我们的PDA获得输入时，它应该像这样工作：
- 如果没有输入：
- 如果堆栈的顶部为空(通常由一些特殊值表示，例如在本例中为
$)，则我们的 PDA 接受字符串：它是一个适当平衡的括号和括号字符串。 - 否则，我们将进入错误状态。字符串不是括号和括号的适当平衡字符串。
- 如果堆栈的顶部为空(通常由一些特殊值表示，例如在本例中为
- 如果输入是
(或[则将输入推送到堆栈并查看下一个输入字符。 - 如果输入是
)则：- 如果堆栈的顶部是
(则弹出堆栈的顶部，然后查看下一个输入。 - 否则，请转到错误状态。字符串不是括号和括号的适当平衡字符串。
- 如果堆栈的顶部是
- 如果输入是
]则：- 如果堆栈的顶部是
[弹出状态的顶部，然后查看下一个输入。 - 否则，请转到错误状态。字符串不是括号和括号的适当平衡字符串。
- 如果堆栈的顶部是
现在，知道了我们的PDA必须做什么，让我们试着思考如何更正式地描述我们的PDA。我们将假设：
- 一组有效输入符号 Σ = {
(，)，[和]} - 初始堆栈符号 Z =
$ - Τ 有效堆栈符号集 Γ = {
(，[} ∪ Z - 状态集 Q = { q0， 接受， 拒绝 }
- 初始状态 q0。
使用类似于 PDA 状态转换 http://en.wikipedia.org/wiki/Pushdown_automaton 中描述的符号，我们可以考虑状态以及事物的流动方式：
-
(q0， ε， top=
$， ACCEPT， nil)这告诉我们的PDA：当您处于状态q0并且没有更多输入并且堆栈的顶部是$进入ACCEPT状态时，保持堆栈不变。 -
(q0， ε， top=
(， 拒绝， nil)这告诉我们的PDA：当您处于状态q0并且没有更多输入并且堆栈的顶部是(进入REJECT 状态时，保持堆栈不变。 -
(q0， ε， top=
[， 拒绝， nil)这告诉我们的PDA：当您处于状态q0并且没有更多输入并且堆栈的顶部是[进入REJECT 状态时，保持堆栈不变。 -
(q0，
(， top=top， q0， push() 这告诉我们的PDA：当您处于状态q0并且输入是(时，无论堆栈顶部是什么，都转到状态q0并将(推送到堆栈上。 -
(q0，
[， top=top， q0， push[) 这告诉我们的PDA：当您处于状态q0并且输入是[时，无论堆栈顶部是什么，都转到状态q0并将[推送到堆栈上。 -
(q0，
)， top=(， q0， pop) 这告诉我们的PDA：当你处于状态q0并且输入是)并且堆栈的顶部是(然后转到状态q0，然后弹出堆栈的顶部。 -
(q0，
)， top=[， 拒绝， nil)这告诉我们的PDA：当您处于状态q0并且输入是)并且堆栈的顶部是[然后转到REJECT 堆栈，保持堆栈不变。 -
(q0，
)， top=$， 拒绝， nil)这告诉我们的PDA：当您处于状态q0并且输入是)并且堆栈的顶部是$然后转到REJECT 堆栈，保持堆栈不变。 -
(q0，
]， top=[， q0， pop) 这告诉我们的PDA：当你处于状态q0并且输入是]并且堆栈的顶部是[然后转到状态q0，然后弹出堆栈的顶部。 -
(q0，
]， top=(， 拒绝， nil)这告诉我们的PDA：当您处于状态q0并且输入是]并且堆栈的顶部是(然后转到REJECT 堆栈，保持堆栈不变。 -
(q0，
]， top=$， 拒绝， nil)这告诉我们的PDA：当您处于状态q0并且输入是]并且堆栈的顶部是$然后转到REJECT 堆栈，保持堆栈不变。
我们本可以使用更多状态来实现这一点，但有趣的是，一个"处理"状态就足够了。
您可能还需要注意，根据您的教师，您可能不需要显式添加 REJECT 状态，尽管这样做是一种很好的形式。
我希望这有所帮助。
这可能有助于您入门：
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;
}