The description of Context-Free Languages (CFL) by means of context-free grammars is convenient, as illustrated by the use of BNF (Baucus Normal Form) in programming language definition. The class of automata that can be associated with context-free languages called **“Pushdown Automata”**. It is an extension of the non-deterministic finite automata with ε-transitions, which is one of the ways that define the regular languages. Intuitively, we understand that the finite automata have strictly finite memories, whereas to recognition of a context-free language may require storing an unbounded amount of information.

**For example**, when a string ‘w’ from the language L = {a^{n}b^{n}: n≥0}, we must not only check that all a’s precede the first b, we must also count the number of a’s. Since n is unbounded, this counting cannot be done with a finite memory thus this CFL is not proceeded with finite machine or finite automata. So solve this problem we want a machine that can count without limit. We might try to solve this problem with a stack as a storage mechanism that allowing unbounded storage that is restricted to operating like a stack. The resulting class of machine called Pushdown Automata. Hence the pushdown automaton is essentially an ε-NFA with addition of a stack. The stack can be read, pushed, and popped only at the top, just like the “stack” data structure.

## Why pushdown automata is necessary?

Let us consider one problem that clears the picture of limitation of the finite automata and the requirement of the Pushdown automata.

Assume a finite automata which accepts the language L_{1} (M) = {a^{m}b^{n} | m n ≥ 1}.

Here we see that M moves from q_{0} (initial state) to q_{1} (intermediate state), on the occurrence of a’s further on seeing ‘b’, M moves from q_{1} to q_{2 }(Final state) and continues to be in the state q_{2} on getting more b’s.

Assume that the input string is given by

**a ^{m}b^{n}**

then the resulting state is final state and so M accepts a^{m}b^{n}.

Consider the language L_{2}(M) = {a^{n}b^{n}| n ≥ 1} where the number of b’s and a’s are equal. The Finite automata constructed for L_{1} differs from that of L_{2}.

For the language L_{1}(M) {a^{m}b^{n} | m, n ≥ 1} there is not necessity to remember the number of a’s. The following have to be remembered.

- Whether the first symbol is ‘b’ (to reject the string)
- Whether ‘a’ follows ‘b’ (to reject the string)
- Whether ‘a’ follows ‘a’ and ‘b’ follows ‘b’ (to accept the string).

We know that finite automata has only a finite number of states, machine M cannot remember the number of a’s in a^{n}b^{n} where ‘n’ is larger than the number of states of M. The finite automata A does not accept the sets of the form {a^{n}b^{n} | n ≥ 1}. This is taken care by a **“PUSHDOWN AUTOMATA”**.