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 = {anbn: 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 L1 (M) = {ambn | m n ≥ 1}.

Here we see that M moves from q0 (initial state) to q1 (intermediate state), on the occurrence of a’s further on seeing ‘b’, M moves from q1 to q2 (Final state) and continues to be in the state q2 on getting more b’s.

Assume that the input string is given by

ambn

then the resulting state is final state and so M accepts ambn.

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

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

  1. Whether the first symbol is ‘b’ (to reject the string)
  2. Whether ‘a’ follows ‘b’ (to reject the string)
  3. 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 anbn where ‘n’ is larger than the number of states of M. The finite automata A does not accept the sets of the form {anbn | n ≥ 1}. This is taken care by a “PUSHDOWN AUTOMATA”.

LEAVE A REPLY

Please enter your comment!
Please enter your name here