Problem Solving in Automata, Languages, and Complexity

150 CONTEXT-FREE LANGUAGES

By the same argument as above, we get ~1 = bj and yr = cj for some j,

1 < j < m.. Now, applying the derivation B 3 bj Bcj for t times, where

t %!/j + 1, we get a derivation of p as follows:

Apparently, the parse tree of this derivation is different from the parse tree of
the derivation (3.2): In the derivation (3.2)) all but nz occurrences of symbol b
are generated together with matching letters a, while in the derivation (3.3)
all but m occurrences of symbol b are generated together with matching letters
c. Thus, the string wn has two different parse trees, and G is ambiguous. This
is a contradition. cl

Finally, we present another interesting property of context-free languages.

Let Q! be a k-dimensional integer vector, and I = {rl,y2, l. l ,7-i} be a finite

set of k-dimensional integer vectors. We write cv + span(I’) to denote the set

A set of k-dimensional integer vectors is called linear if it is equal to a +

spur@‘) for some a and I. A set of k-dimensional integer vectors is said to

be semi&near if it is a union of finitely many linear sets.

For any string x over an alphabet {al, ~42,.. l , c&}, with a fixed ordering

a1 4 (32 4 l ‘* + ak, define $(x) = (711,?22, .*.,rzk), where ni is the num-

ber of occurrences of symbol ui in X. For any language L over alphabet

{al, a2, l ’ l ,ak}, we let o(L) = {o(x) 1 x E L}-

*Lemma 3.55 (Pa rikh’s Lemma) For any context-free language L, t+(L) is
semilinear.

Proof. Let G = (V, C, R, S) be a context-free grammar generating L. Let

m = IV(, and assume that each rule A -+ x in R has 1x1 < d. - Let K = dm2?

Also let Lo = {w E C* I lwl < K}. Clearly, Lo is finite. To show the lemma,

it suffices to prove that for any string w in L, there exist a E $(Lo) and

I? c - t$(LO) such that

This will be done by showing the following claim. In the following, we
generalize the term “parse tree” to include any subtree T’ of a parse tree T.
That is, the root of a parse tree could be any nonterminal symbol and the
leaves of a parse tree could be either terminal or nonterminal symbols.

Claim. For any w E L, let T be a parse tree for w, and let VI be the set of
nonterminals which occur in T (called the nonterminal set of T). Then, there
exist a E +(L 0 and ) I’ - C $(Lo) satisfying the following properties: