Push-down automata

Context-Free Languages allow only productions of the form a —> d, where a is an arbitrary string of terminal and non-terminal symbols there is also a fixed bound on the length of a (= 5- ). Recognized by Push-Down Automata. 

Context-Free Languages/ Push-Down Automata... 

Push-down Automata push-down automata generalize finite automata by introducing an internal memory. Just as for finite automata, push-down automata have a finite input alphabet and a finite set of intermediate states, a subset of which constitutes the set of its output (or accepting) states. The difference is that push-down automata have an additional stack-space, consisting of some or all of the symbols of the machine s alphabet (along with perhaps some additional symbols to be used as internal markers) which they can use to store information for later use. We can therefore generalize our definition for finite automata (equation 6.4) to ... 

DEFINITION A push -down automaton A4 is specified by four sets A, E, A and E and a finite set of state-transition functions 3 cp T, x A T, where... 

---