1、Yinliang ZhaoXian Jiaotong University2013Pushdown Automata* 1Pushdown Automata A PDA is an automaton equivalent to the CFG in language-defining power. Only the nondeterministic PDA defines all possible CFLs. But the deterministic version models parsers. Most programming languages have deterministic
2、PDAs.Date 2Intuition: PDA Think of an -NFA with the additional power that it can manipulate a stack. Its moves are determined by:uThe current state (of its “NFA”),uThe current input symbol (or ), and uThe current symbol on top of its stack.Date 3Intuition: PDA (2) Being nondeterministic, the PDA can
3、 have a choice of next moves. In each choice, the PDA can:uChange state, and alsouReplace the top symbol on the stack by a sequence of zero or more symbols.uZero symbols = “ pop.”uMany symbols = one “ pop” and then sequence of “pushes.”Date 4PDA Formalism A PDA is described by: A finite set of state
4、s (Q, typically). An input alphabet (, typically). A stack alphabet (, typically). A transition function (, typically). A start state (q0, in Q, typically). A start symbol (Z0, in , typically). A set of final states (F Q, typically).Date 5Conventions a, b, are input symbols. But sometimes we allow a
5、s a possible value. , X, Y, Z are stack symbols. , w, x, y, z are strings of input symbols. , , are strings of stack symbols.Date 6The Transition Function Takes three arguments: A state, in Q. An input, which is either a symbol in or . A stack symbol in . (q, a, Z) is a set of zero or more actions o
6、f the form (p, ). p is a state; is a string of stack symbols.Date 7Actions 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:uChange the state to p.uRemove a from the front of the input (
7、but a may be ).uReplace Z on the top of the stack by .Date 8Example: PDA Design a PDA to accept 0n1n | n 1. The states: q = start state. We are in state q if we have seen only 0s so far. p = weve seen at least one 1 and may now proceed only if the inputs are 1s. f = final state; accept.Date 9Example: 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 1s as 0s. X = marker, used to count the number of 0s seen on the input.Date 10
