效绵鼎 Example:PDA-(2) The stack symbols: o Zo=start symbol.Also marks the bottom of the stack,so we know when we have counted the same number of 1’sas0's. 0 X=marker,used to count the number of 0's seen on the input. .11
Example: PDA – (2) ◼ The stack symbols: Z0 = start symbol. Also marks the bottom of the stack, so we know when we have counted the same number of 1’s as 0’s. X = marker, used to count the number of 0’s seen on the input. 11
效绵鼎 Example:PDA-(3) The transitions: oδ(q,0,Zo)={(q,XZ)}. o 5(q,0,X)={(q,XX)).These two rules cause one X to be pushed onto the stack for each 0 read from the input. o (q,1,X)={(p,E)).When we see a 1,go to state p and pop one X. 0 6(p,1,X)={(p,E)}.Pop one X per 1. 0 (p,E,Zo)={(f,Zo)).Accept at bottom. .12
Example: PDA – (3) ◼ The transitions: δ(q, 0, Z0 ) = {(q, XZ0 )}. δ(q, 0, X) = {(q, XX)}. These two rules cause one X to be pushed onto the stack for each 0 read from the input. δ(q, 1, X) = {(p, ε)}. When we see a 1, go to state p and pop one X. δ(p, 1, X) = {(p, ε)}. Pop one X per 1. δ(p, ε, Z0 ) = {(f, Z0 )}. Accept at bottom. 12
赖绵县 Actions of the Example PDA 000111 q Zo .13
Actions of the Example PDA 13 q 0 0 0 1 1 1 Z0
赖绵县 Actions of the Example PDA 00111 q X Zo .14
Actions of the Example PDA 14 q 0 0 1 1 1 X Z0
赖绵县 Actions of the Example PDA 0111 q X×石 .15
Actions of the Example PDA 15 q 0 1 1 1 X X Z0