Relation Between Sentential Forms and Derivation
Trees
Derivation trees give a very explicit and easily comprehended description of a
derivation. Like transition graphs for finite automata, this explicitness is a great
help in making arguments. First, though, we must establish the connection
between derivations and derivation trees.
Theorem 5.1
Let G = (V, T, S, P) be a context-free grammar. Then for every w ∈ L (G), there
exists a derivation tree of G whose yield is w. Conversely, the yield of any
derivation tree is in L (G). Also, if t G is any partial derivation tree for G whose
root is labeled S, then the yield of t G is a sentential form of G.
Proof: First we show that for every sentential form of L (G) there is a
corresponding partial derivation tree. We do this by induction on the number of
steps in the derivation. As a basis, we note that the claimed result is true for
every sentential form derivable in one step. Since S ⇒ u implies that there is a
production S → u, this follows immediately from Definition 5.3.
Assume that for every sentential form derivable in n steps, there is a
corresponding partial derivation tree. Now any w derivable in n + 1 steps must
be such that