Now when we make decisions on what state to move to, we must consider what's on the stack as well as the next input character. Also, when we make a transition from one state to another, we may wish to push more data onto our stack. Thus, every transition must be labeled with three things:
_ _ _ _ _ _ INPUT: aabbb aabbb aabbb aabbb aabbb aabbb STACK: |S ==> x|S ==> xx|S ==> xx|S ==> x|S ==> |S ==> STUCK! Can't read last character STATE q0 q0 q0 q1 q1 q1The machine gets stuck with b left to read, because reading that b requires popping x off the stack, and the stack is empty! Hopefully you can convince yourself that this machine will accept exactly {ambn | m ≥ n}.
Definition A Push Down Automaton is a 6-tuple (Q,Σ,Γ,Δ,s,W) whereThe transition (p,a,x,q,y) is a interpreted as starting at state p, reading a from the input, popping x off the stack, moving to state q, and pushing y onto the stack. Note that we can push and pop strings, not just individual characters. We will define precisely how to interpret this next lecture. For the moment, let this suffice: the stack is treated as a string, pushing is equivalent to prefixing, and what can be popped off the stack are prefixes.
- Q is the set of states (must be finite!)
- Σ is the alphabet for input strings (must be finite!)
- Γ is the set of symbols that can appear on the stack (must be finite!)
- Δ is the set of transitions, Δ ⊆ Q × (Σ ∪ {λ}) × Γ * × Q × Γ *
- s is the start state, s ∈ Q
- W are the accepting states, W ⊆ Q