Since G has no useless nonterminals, for each nonterminal A of G, there is a derivation tree for some string in L(G) in which A appears in a node label.
by Lemma 1, there are strings A decomposition of w ∈ Σ * is a finite binary tree satisfying the following conditions: • the root is labeled by some (w 1 , w 2 ) such that w = w 1 w 2 , • each internal node whose left and right children are labeled by (u 1 , u 2 ) and (v 1 , v 2 ), respectively, is labeled by one of (u 1 u • each leaf node is labeled by some (s 1 , the label of an internal node in a decomposition is obtained from the labels of its children by left concatenation, right concatenation, or wrapping.