Question

Let G be any context-free grammar. Show that the number of strings that have a derivation in G of length n or less, for any n > 0, is finite.

Could you please answer with clear explanation. The question is from Elaine Rich's Automata, Computability and Complexity Chapter 11 Exercise 14.

Answer 1

Question: Let be any context-free grammar. Show that the number of strings that have a derivation in G of length n or less, for any n > 0, is finite.

Sol: Define ()to be the set of strings in () that have a derivation in of length n or less. We can give a (weak) upper bound on the number of strings in ().

Let be the number of rules in and let be the largest
number of nonterminals on the right hand side of any rule in .

For the first derivation step, we start with and
have choices of derivations to take. So at most strings can be generated. (Generally there will be many fewer, since many rules may not apply, but we're only producing an upper bound here, so that's okay.)

At the second step, we may have strings to begin with (any one of the ones produced in the first step), each of them may have up to nonterminals that we could choose to expand, and each nonterminal could potentially be
expanded in ways.

So the number of strings that can be produced is no more than ⋅⋅. Note that many of them aren’t strings in since they may still contain nonterminals, but this number is an upper bound on the number of strings in that can be produced.

At the third derivation step, each of those strings may again have nonterminals that can be expanded and ways to expand each. In general, an upper bound on the number of strings produced after derivation steps is , which is clearly finite.

The key here is that there is a finite number of rules and that each rule produces a string of finite length.