(i) L is infinite, hence there is no proper upper bound on the length of
strings belonging to L.
(ii) L does not contain λ.
(iii) G has no productions or λ-productions.
There are only a finite number of variables in a grammar and the
productions for each variable have finite lengths. The only way that a grammar
can generate arbitrarily long strings is if one or more variables is both useful
and recursive.
Suppose no variable is recursive.
Since the start symbol is nonrecursive, it must be defined only in terms of
terminals and other variables. Then since those variabls are non recursive, they
have to be defined in terms of terminals and still other variables and so on.
After a while we run out of “other variables” while the generated string is still
finite. Therefore there is an upperbond on the length of the string which can be
generated from the start symbol. This contradicts our statement that the
language is finite.
Hence, our assumption that no variable is recursive must be incorrect.
(b) Let us consider a string X belonging to L.
If X is sufficiently long, then the derivation of X must have involved
recursive use of some variable A.
Since A was used in the derivation, the derivation should have started as
S uAy
⇒
*
for some values of u and y. Since A was used recursively the derivation must
have continued as
S uAy uvAxy
⇒
⇒
*
*
Finally the derivation must have eliminated all variables to reach a string
X in the language.
S uAy uvAxy uvwxy x
⇒
⇒
⇒
=
*
*
*
This shows that derivation steps
A vAx
⇒
*
and
A w
⇒
*
are possible. Hence the derivation
A vwx
⇒
*
must also be possible.
172
Theory of Automata, Formal Languages and Computation