c – 如何设计下推式自动机

我通常不会为他们完成某人的整个作业,但事实是,当涉及到自动机时,即使我这样做,除非你真的理解这些事情是如何运作的,否则对你来说无济于事.学校开始时并没有很好地教他们.

让我们考虑一下这个PDA如何运作,忘记状态和转换以及现在的情况：当我们的PDA得到输入时,它应该像这样工作：

>如果没有输入：

>如果堆栈的顶部是空的(通常由一些特殊值表示,让我们说这个例子为$),那么我们的PDA接受字符串：它是一个适当平衡的括号和括号字符串.
>否则我们会进入错误状态.字符串不是括号和括号的正确平衡字符串.

>如果输入是(或[然后将输入推入堆栈并查看下一个输入字符.
>如果输入是a)则：

>如果堆栈的顶部是a(弹出堆栈的顶部,并查看下一个输入.
>否则,转到错误状态.字符串不是括号和括号的正确平衡字符串.

>如果输入是],那么：

>如果堆栈的顶部是[弹出状态的顶部,转到错误状态.字符串不是括号和括号的正确平衡字符串.

现在,知道我们的PDA必须做什么让我们试着想一想如何更正式地描述我们的PDA.我们假设：

>一组有效输入符号Σ= {(,),[和]}
>初始堆栈符号Z = $
>有效堆栈符号集Γ= {(,[}∪Z
>状态集Q = {q0,ACCEPT,REJECT}
>初始状态q0.

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

>(q0,ε,top = $,nil)这告诉我们的PDA：当你处于状态q0并且没有更多输入并且堆栈的顶部是$进入ACCEPT状态时,保持堆栈不变.
>(q0,top =(,REJECT,nil)这告诉我们的PDA：当你处于状态q0并且没有更多输入并且堆栈的顶部是a时(进入REJECT状态,保持堆栈不变) .
>(q0,top = [,nil)这告诉我们的PDA：当你处于状态q0并且没有更多的输入并且堆栈的顶部是[进入REJECT状态时,(,top = top,q0,push()这告诉我们的PDA：当你处于状态q0并且输入是a时(那么,不管堆栈顶部是什么,转到状态q0然后推(进入堆栈.
>(q0,[,push [)这告诉我们的PDA：当你处于状态q0并且输入是[然后,转到状态q0然后把[推到堆栈上.
>(q0,pop)这告诉我们的PDA：当你处于状态q0并且输入是a)并且堆栈的顶部是a(然后进入状态q0,然后弹出关闭的顶部.
>(q0,nil)这告诉我们的PDA：当你处于状态q0并且输入是a)并且堆栈的顶部是[然后转到REJECT堆栈,离开堆栈不变.
>(q0,nil)这告诉我们的PDA：当你处于状态q0并且输入是a)并且堆栈的顶部是$然后转到REJECT堆栈,],pop)这告诉我们的PDA：当你处于状态q0并且输入是一个]并且堆栈的顶部是[然后进入状态q0,nil)这告诉我们的PDA：当你处于状态q0并且输入是一个]并且堆栈的顶部是a(然后转到REJECT堆栈,离开堆栈)不变.
>(q0,nil)这告诉我们的PDA：当你处于状态q0并且输入是一个]并且堆栈的顶部是$然后转到REJECT堆栈,离开堆栈不变.

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

您可能还需要注意,根据您的教师,您可能不需要明确添加REJECT状态,尽管这样做很好.

我希望这有帮助.