一般地 若x是w的当前符号,栈顶符号为D <X,D,A1A2…Ak>表示: 将D弹出栈 将串AA2…Ak压入栈(A为新栈顶)
一般地 若x是w的当前符号,栈顶符号为D <x,D,A1A2… Ak>表示: 将D弹出栈 将串A1A2… Ak压入栈(A1为新栈顶)
例5-1算法的形式化描述 <a,Zo,AZo <b,Zo,BZo> <a,A,AA> <b,B,BB> <a,B,& <b,A,8> <8, Z0 >
例5-1 算法的形式化描述 <a,Z0,AZ0> < b,Z0,BZ0> < a,A,AA> < b,B,BB> < a,B,ε> < b,A,ε> < ε,Z0,ε>
规则<8,Z0’ 表示将w扫描结束后,将栈置成空 也表示该PDA可以接收空串
规则< ε,Z0,ε> 表示将w扫描结束后,将栈置成空 也表示该PDA可以接收空串ε
思考: 如何接收语言 L={ww∈(a,b)*,且a和b个数相等}?
思考: 如何接收语言 L={w|w∈(a,b)+ ,且a和b个数相等}?
例:语言L={abn≥0} <a, Z0’AZ02 <a,A,AA> <b,A, 8> <C, Z0’ 8>
例:语言L={a nbn |n≥0} <a,Z0,AZ0> <a,A,AA> <b,A,ε> <ε,Z0,ε>