Problem Solving in Automata, Languages, and Complexity

5.6 Undecidable Problems 269

First, we consider context-free grammars. We note that the membership

problem (given a context-free grammar G and a string X, determine whether

x E L(G)) and the emptyness problem (given a context-free grammar G,
determine whether L(G) = 8) for context-free grammars are decidable. The
following result shows that the totality problem for context-free grammars is
undecidable.

• Example 5.43 Show that the problem of determining whether a given
  context-free grammar G over the alphabet {O,l} has L(G) = {O,l}* is un-
  decidable.

Proof. We reduce the problem EMP to this problem. Let A4 be a DTM. Recall

that, in Section 5.1, we have defined a coding scheme for a configuration of

A4. We make a minor modification here. We encode the configuration

bY

11101@1@1.. .10im-1110j110i~10imt-11... l@-ql,

Next, we say a string x is a legal computation of A4 if

x = W-J (al)R a2 (Cr3)R l l ’ (cY,-l)R a, (5. 2)

for some even m > 0 (where (c@ denotes the reversal of the string CQ), or if

x = a() (al)R a2 (a3)R l l l %-n-l ( %?-A > R (5. 3)

for some odd m > 0, with the following properties:

(i) a0 is (the code of) an initial configuration of iU;

(ii) For each i, 0 < - i < - m - 1, cq kM ai+l;

...
(^111 > a, is a final configuration.
In other words, a legal computation here is a computation path of A4 with
every other configuration reversed. The reason to reverse every other config-
uration is to get the following claim:
Cluim. The set of all illegal computations of A4 is a context-free language.
Proof of the Cluim. For any string x E (0, l}“, we say x is a configurution-
block (or, simply, a c-block) of x if x is a substring of x of the form lllOyOlll,
with y containing no substring 111. A string z E (0, 1}* is not a legal com-
putation if and only if one of the following holds:
(a) x is not of the form (5.2) or (5.3) with each a; encoding a configuration.
(b) The first c-b1 oc k 00 of x is not an initial configuration.
(c) For some even i, 0 5 i < m., the ith c-block z and the (i + 1)st c-block
y of z do not satisfy 2 kM yR.