如何设计下推式自动机

Question

我如何设计一个接受平衡括号和括号的PDA([] []),我很难入门.我需要帮助编写此问题的转换函数.任何帮助表示赞赏

Answer 1

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

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

• 如果没有输入:
  • 如果堆栈的顶部是空的(通常用一些特殊值表示$,比如本例),那么我们的PDA接受字符串:它是一个正确平衡的括号和括号字符串.
  • 否则我们会进入错误状态.字符串不是括号和括号的正确平衡字符串.
• 如果输入是a (或a,[则将输入推入堆栈并查看下一个输入字符.
• 如果输入是a )则:
  • 如果堆栈的顶部是(弹出堆栈的顶部,并查看下一个输入.
  • 否则,转到错误状态.字符串不是括号和括号的正确平衡字符串.
• 如果输入是a ]则:
  • 如果堆栈的顶部是[弹出状态的顶部,并查看下一个输入.
  • 否则,转到错误状态.字符串不是括号和括号的正确平衡字符串.

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

• Τhe组有效输入码元的Σ= { (,),[和]}
• 初始堆栈符号Z = $
• 一组有效的堆栈符号Γ= { (,[} ∪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 =先顶,Q0,推()这告诉我们的PDA:当你在状态Q0和输入是(的话,不管是什么在堆栈的顶部,进入状态Q0,并推(到堆栈.

• (Q0,[,top =先顶,Q0,推[)这告诉我们的PDA:当你在状态Q0和输入是[的话,不管是什么在堆栈的顶部,进入状态Q0,并推[到堆栈.

• (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状态,尽管这样做很好.

我希望这有帮助.