效绵鼎 PDA Formalism A PDA is described by: 1.A finite set of states (Q,typically). 2.An input alphabet(Σ，typically) 3. A stack alphabet(「，typically). 4. A transition function(δ，typically) 5. A start state (qo,in Q,typically) 6. A start symbol(Zo,in「，typically). 7.A set of final states (FQ,typically) 6
PDA Formalism ◼ A PDA is described by: 1. A finite set of states (Q, typically). 2. An input alphabet (Σ, typically). 3. A stack alphabet (Γ, typically). 4. A transition function (δ, typically). 5. A start state (q0 , in Q, typically). 6. A start symbol (Z0 , in Γ, typically). 7. A set of final states (F ⊆ Q, typically). 6
效绵鼎 Conventions ■ a,b,..are input symbols. 0 But sometimes we allow e as a possible value. ■.，X,Y,Z are stack symbols. ...w,X,y,z are strings of input symbols. a,B,...are strings of stack symbols. 7
Conventions ◼ a, b, … are input symbols. But sometimes we allow ε as a possible value. ◼ …, X, Y, Z are stack symbols. ◼ …, w, x, y, z are strings of input symbols. ◼ , ,… are strings of stack symbols. 7
效绵鼎 The Transition Function Takes three arguments: 1.A state,in Q. 2.An input,which is either a symbol in or E. 3. A stack symbol in「. 6(q,a,Z)is a set of zero or more actions of the form (p,a). o p is a state;a is a string of stack symbols. ◆8
The Transition Function ◼ Takes three arguments: 1. A state, in Q. 2. An input, which is either a symbol in Σ or ε. 3. A stack symbol in Γ. ◼ δ(q, a, Z) is a set of zero or more actions of the form (p, ). p is a state; is a string of stack symbols. 8
效绵鼎 Actions of the pda If 8(q,a,Z)contains (p,a)among its actions,then one thing the PDA can do in state q,with a at the front of the input,and Z on top of the stack is: 1. Change the state to p. 2. Remove a from the front of the input(but a may be e) 3. Replace Z on the top of the stack by a. 9
Actions of the PDA ◼ If δ(q, a, Z) contains (p, ) among its actions, then one thing the PDA can do in state q, with a at the front of the input, and Z on top of the stack is: 1. Change the state to p. 2. Remove a from the front of the input (but a may be ε). 3. Replace Z on the top of the stack by . 9
效绵鼎 Example:PDA Design a PDA to accept {on1n |n1). The states: q=start state.We are in state q if we have seen only 0's so far. o p=we've seen at least one 1 and may now proceed only if the inputs are 1's. o f=final state;accept. .10
Example: PDA ◼ Design a PDA to accept {0n1 n | n > 1}. ◼ The states: q = start state. We are in state q if we have seen only 0’s so far. p = we’ve seen at least one 1 and may now proceed only if the inputs are 1’s. f = final state; accept. 10