Structure of Context-free Grammars

Context free grammars often contain collection of sentences in which phrases are nested in matched pairs. For example if A ® j AY is a production where j and Y are nonempty strings of terminal and nonterminal letters, this production permits the form of derivation shown below.

(Self-embedding derivation tree)

Each of the sentential forms j ^kAY ^k, k>=0 is derivable from A. This is the self-embedding property.

Structure Theorem

Let G=(N,T,P,S) be a well formed context-free grammar. For any A in N{S}, L(G,A) is infinite if and only if G permits the following derivatoinsfor some nonterminal B:

Aa Ab , a ,b Î T^*

Bj BY , j ,Y Î T^*-l

Bs, sÎ T^*-l

For any context-free grammar G, one can decide whether L(G) is finite or infinite.

Back to Table of contents of Chapter7