南京大学：《形式语言与自动机 Formal Languages and Automata》课程教学资源（PPT课件讲稿）Pushdown Automata

NANJING UNIVERSITY Pushdown Automata Definition Moves of the PDA Languages of the PDA Deterministic PDA's .1

Definition Moves of the PDA Languages of the PDA Deterministic PDA’s Pushdown Automata 1

效绵鼎 Pushdown Automata The PDA is an automaton equivalent to the CFG in language-defining power. ■ Only the nondeterministic PDA defines all the CFL's. ■ But the deterministic version models parsers. Most programming languages have deterministic PDA's. 2

Pushdown Automata ◼ The PDA is an automaton equivalent to the CFG in language-defining power. ◼ Only the nondeterministic PDA defines all the CFL’s. ◼ But the deterministic version models parsers.  Most programming languages have deterministic PDA’s. 2

效绵鼎 Intuition:PDa Think of an E-NFA with the additional power that it can manipulate a stack. Its moves are determined by: The current state(of its“NFA”), 2. The current input symbol (or E),and 3. The current symbol on top of its stack. 3

Intuition: PDA ◼ Think of an ε-NFA with the additional power that it can manipulate a stack. ◼ Its moves are determined by: 1. The current state (of its “NFA”), 2. The current input symbol (or ε), and 3. The current symbol on top of its stack. 3

赖绵县 Picture of a PDa Next input symbol 0111 Input State X Top of Stack Y Z Stack 4

Picture of a PDA 4 q 0 1 1 1 X Y Z State Stack Top of Stack Input Next input symbol

效绵鼎 Intuition:PDA-(2) Being nondeterministic,the PDA can have a choice of next moves. In each choice,the PDA can: 1.Change state,and also 2.Replace the top symbol on the stack by a sequence of zero or more symbols. u Zero symbols=“pop.” Many symbols=sequence of“pushes.” .5

Intuition: PDA – (2) ◼ Being nondeterministic, the PDA can have a choice of next moves. ◼ In each choice, the PDA can: 1. Change state, and also 2. Replace the top symbol on the stack by a sequence of zero or more symbols. u Zero symbols = “ pop.” u Many symbols = sequence of “pushes.” 5

效绵鼎 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