Context-Free Languages Push-Down Automata

2 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 

Context-Free Grammars context-free grammatical rules — Pj are such 

The transition rule states that can be replaced by /3 only when it is preceded 

---