rather is the general rule. As we now show, there is little we can say about these
languages. Recursively enumerable languages are so general that, in essence,
any question we ask about them is undecidable. Invariably, when we ask a
question about recursively enumerable languages, we find that there is some way
of reducing the halting problem to this question. We give here some examples to
show how this is done and from these examples derive an indication of the
general situation.
Theorem 12.3
Let G be an unrestricted grammar. Then the problem of determining whether or
not
L (G) = Ø
is undecidable.
Proof: We will reduce the membership problem for recursively enumerable
languages to this problem. Suppose we are given a Turing machine M and some
string w. We can modify M as follows. M first saves its input on some special
part of its tape. Then, whenever it enters a final state, it checks its saved input
and accepts it if and only if it is w. We can do this by changing δ in a simple
way, creating for each w a machine M w such that
L (M w ) = L (M) {w}.
Using Theorem 11.7, we then construct a corresponding grammar G w . Clearly,
the construction leading from M and w to G w can always be done. Equally clear
is that L (G w ) is nonempty if and only if w ∈ L (M).
Assume now that there exists an algorithm A for deciding whether or not
L(G) = Ø. If we let T denote an algorithm by which we generate G w , then we can
put T and A together as shown in Figure 12.5. Figure 12.5 is a Turing machine
that for any M and w tells us whether or not w is in L (M). If such a Turing
machine existed, we would have a membership algorithm for any recursively
enumerable language, in direct contradiction to a previously established result.
We conclude therefore that the stated problem “L (G) = Ø ” is not decidable.