Context-Free Grammars from Pushdown Accepters

Let M=(Q,S,U,P,I,F) be a proper pushdown accepter. A move sequence of M

(q,j ,s )Þ (q',j ',s ')

is called a traverse of w from state q' to state q provided:

  1. s =s '
  2. j w =j

Each configuration (qi,j i,s i) ocurring within the move sequence satisfies |s i|³ |s |.

In such a case , we say that w is the string observed by the traverse. To indicate that a move sequence is a traverse, we write:

(q,j ,s )(q',j w ,s )

The traverse compromising no moves (q,j ,s )(q',j ,s ) observes the empty string and is called a trivial traverse.

Construction of a grammar:

In a traverse (q,j ,s )(q',j w ,s ) by a pushdown accepter, let s be the initial and final contents of the stack. A write move in the traverse is called a base write move if it is performed from a configuration in which the stack contents are s ; a read move is called a base read move if it leaves the stack containing s . A base write move and a base read move from a matched pair if the write move precedes the read move, and no other base write or read move intervene.

A traverse that contains a base read (write) move also contains a matching base write (read) move.

Let M be a proper pushdown accepter and suppose that (q,j ,s )(q',j w ,s ) is a traverse of w by M; that is, w Î T(q.q'). then exactly one of the following statements are true:

  1. The traverse consists of a single scan move: (q,j ,s )(q',j s,s ) and w =s.
  2. The traverse has more than one move, and the final move is a scan: (q,j ,s )(q',j y ,s )(q',j y ,s ) where w=y s and y Î T(q,q').
  3. If the traverse has more than one move, the final move is a read, and the matching write is not the first move: (q,j,s)(q'',j y ,s )(p,j y ,s )(p',j y q ,s u)(q',j y q ,s )
  4. The traverse has more than one move, the final move is a read, and the matching write is the first move of the traverse: (q,j ,s )(p,j ,s u)(p',j q ,s u)(q',j q ,s )where w =q and q Î T(p,p').

For any pushdown accepter M, one can construct a context-free grammar such that L(G)=L(M).

If M is a proper pushdown accepter and G is the grammar obtained from M, then for each w Î S* the traverses by which M accepts w correspond one-to-one with terminal leftmost derivations of w in G.

Back to Table of contents of Chapter6