电子科技大学：《有限自动机理论 Finite Automata Theory》课程教学资源（课件讲稿）第05章 下推自动机（简化版）

初始 栈为空 从左到右逐个扫描串w∈(a,b)

初始 栈为空 从左到右逐个扫描串w∈(a，b) *

入栈 若栈为空，当前符号是a,则A入栈 若栈为空，当前符号是b,则B入栈 若栈顶为A,当前符号是a,则A入栈 若栈顶为B,当前符号是b,则B入栈

入栈 若栈为空,当前符号是a,则A入栈 若栈为空,当前符号是b,则B入栈 若栈顶为A,当前符号是a,则A入栈 若栈顶为B,当前符号是b,则B入栈

出栈 若栈顶为A,当前符号是b,则A出栈 若栈顶为B,当前符号是a,则B出栈

出栈 若栈顶为A,当前符号是b，则A出栈 若栈顶为B,当前符号是a，则B出栈

若串w有相同个数的a和b 当且仅当 w扫描结束后，栈为空

若串w有相同个数的a和b 当且仅当 w扫描结束后，栈为空

注意 PDA在两种情况下停机： 串扫描结束 没有对应的规则

注意 PDA在两种情况下停机： 串扫描结束 没有对应的规则