Computer Science 3331A/B Chapter Notes - Chapter 12: Pushdown Automaton, If And Only If, Context-Free Grammar
22 Jan 2020
School
Department
Course
Professor
Document Summary
Device similar to fsm but more power. Needs a stack: unlimited memory with restricted structure. Finite state machine augmented by a single stack. A configuration of m is an element k x * x *: captures 3 things that can make a diff to m"s future behavior, current state, input left to read, contents of stack. The initial configuration of m on input w is is (s,w,ep) If sequence c1, c2,c3,c4 cn is pushed onto stack with character s already in stakc, resulting stack is c1,c2,c3,c4 cn, s. Let c in or {ep}, let y1,y2,y3 in *, and w in * Then: (q1,cw,y1y) |-m(q2,w,y2y) iff ((q1,c,y1),(q2,y2)) in . |-m* is reflexive transitive closure of |-m. C1 yields configuration c2 iff c1 |-m* c2. Note how ((q1,c,y1),(q2,y2)) says about how m manipulates stack: m may only take transition if string y1 matches current top of the stack. M cannot peek at top of stack without popping off values that it examines.
