where u, v, and z are in T*. But then
is possible for all n, so that L (G) is infinite.
If no variable can ever repeat, then the length of any derivation is bounded
by |V|. In that case, L (G) is finite.
Thus, to get an algorithm for determining whether L (G) is finite, we need
only to determine whether the grammar has some repeating variables. This can
be done simply by drawing a dependency graph for the variables in such a way
that there is an edge (A, B) whenever there is a corresponding production
Then any variable that is at the base of a cycle is a repeating one. Consequently,
the grammar has a repeating variable if and only if the dependency graph has a
cycle.
Since we now have an algorithm for deciding whether a grammar has a
repeating variable, we have an algorithm for determining whether or not L (G) is
infinite.
Somewhat surprisingly, other simple properties of context-free languages are
not so easily dealt with. As in Theorem 4.7, we might look for an algorithm to
determine whether two context-free grammars generate the same language. But
it turns out that there is no such algorithm. For the moment, we do not have the
technical machinery for properly defining the meaning of “there is no
algorithm,” but its intuitive meaning is clear. This is an important point to which
we will return later.
EXERCISES
1. Is the complement of the language in Example 8.8 context-free?
2. Consider the language L 1 in Theorem 8.4. Show that this language is linear.
3. Show that the family of context-free languages is closed under