計算機科學分類自動機理論automata

1、1Pushdown AutomataDefinitionMoves of the PDALanguages of the PDADeterministic PDAs2Pushdown AutomataThe PDA is an automaton equivalent to the CFG in language-defining power.Only the nondeterministic PDA defines all the CFLs.But the deterministic version models parsers.Most programming languages have

2、 deterministic PDAs.3Intuition: PDAThink of an -NFA with the additional power that it can manipulate a stack.Its moves are determined by:The current state (of its “NFA”),The current input symbol (or ), and The current symbol on top of its stack.4Picture of a PDAq 0 1 1 1XYZStateStackTop of StackInpu

3、tNext inputsymbol5Intuition: PDA (2)Being nondeterministic, the PDA can have a choice of next moves.In each choice, the PDA can:Change state, and alsoReplace the top symbol on the stack by a sequence of zero or more symbols.Zero symbols = “pop.”Many symbols = sequence of “pushes.”6PDA FormalismA PDA

4、 is described by:A finite set of states (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).7Conventionsa, b, are input symbols

5、.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.8The Transition FunctionTakes 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 mo

6、re actions of the form (p, ).p is a state; is a string of stack symbols.9Actions of the PDAIf (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:Change the state to p.Remove a from the front of the inpu

7、t (but a may be ).Replace Z on the top of the stack by .10Example: PDADesign 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.11Example: PDA (2)Th

8、e 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.12Example: PDA (3)The transitions:(q, 0, Z0) = (q, XZ0).(q, 0, X) = (q, XX). These two rules cause one X to

9、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.13Actions of the Example PDAq 0 0 0 1 1 1Z014Actions of the Example PDAq 0 0 1 1 1XZ015Actions of the Examp

10、le PDAq 0 1 1 1XXZ016Actions of the Example PDAq1 1 1XXXZ017Actions of the Example PDAp1 1XXZ018Actions of the Example PDAp1XZ019Actions of the Example PDApZ020Actions of the Example PDAfZ021Instantaneous DescriptionsWe can formalize the pictures just seen with an instantaneous description (ID).A ID

11、 is a triple (q, w, ), where:q is the current state.w is the remaining input. is the stack contents, top at the left.22The “Goes-To” RelationTo say that ID I can e ID J in one move of the PDA, we write IJ.Formally, (q, aw, X)(p, w, ) for any w and , if (q, a, X) contains (p, ).Extend to *, meaning “

12、zero or more moves,” by:Basis: I*I.Induction: If I*J and JK, then I*K.23Example: Goes-ToUsing the previous example PDA, we can describe the sequence of moves by: (q, 000111, Z0)(q, 00111, XZ0) (q, 0111, XXZ0)(q, 111, XXXZ0) (p, 11, XXZ0)(p, 1, XZ0)(p, , Z0) (f, , Z0)Thus, (q, 000111, Z0)*(f, , Z0).W

13、hat would happen on input 0001111?24Answer(q, 0001111, Z0)(q, 001111, XZ0) (q, 01111, XXZ0)(q, 1111, XXXZ0) (p, 111, XXZ0)(p, 11, XZ0)(p, 1, Z0) (f, 1, Z0)Note the last ID has no move.0001111 is not accepted, because the input is not completely consumed.25Language of a PDAThe common way to define th

14、e language of a PDA is by final state.If P is a PDA, then L(P) is the set of strings w such that (q0, w, Z0) * (f, , ) for final state f and any .26Language of a PDA (2)Another language defined by the same PDA is by empty stack.If P is a PDA, then N(P) is the set of strings w such that (q0, w, Z0) *

15、 (q, , ) for any state q.27Equivalence of Language DefinitionsIf L = L(P), then there is another PDA P such that L = N(P).If L = N(P), then there is another PDA P such that L = L(P).28Proof: L(P) - N(P) IntuitionP will simulate P.If P accepts, P will empty its stack.P has to avoid accidentally empty

16、ing its stack, so it uses a special bottom-marker to catch the case where P empties its stack without accepting.29Proof: L(P) - N(P)P has all the states, symbols, and moves of P, plus:Stack symbol X0 (the start symbol of P), used to guard the stack bottom.New start state s and “erase” state e.(s, ,

17、X0) = (q0, Z0X0). Get P started.Add (e, ) to (f, , X) for any final state f of P and any stack symbol X, including X0.(e, , X) = (e, ) for any X.30Proof: N(P) - L(P) IntuitionP” simulates P.P” has a special bottom-marker to catch the situation where P empties its stack.If so, P” accepts.31Proof: N(P) - L(P)P has all the states, symbols, and moves of P, plus:Stack symbol X0 (the start symbol), used to guard the stack bottom.New start state s and final state f.(s, , X0) = (q0, Z0X0). Get P started.(q, , X0) = (f, ) for any