5.6 Undecidable Problems 271
regular expression of this set, and Q be the regular expression for the set
of strings over (0, 1) h aving no substring 111. Then, the set 5’5 of strings
satisfying condition (e) is
(ll1OQO111 lllOQOlll)* lllOQOlll Rs.Therefore, 5’s is regular.
Condition (f) is similar to condition (e). We can prove, in a similar way,
that set S6 of strings satisfying condition (f) is also regular. The above com-
pletes the proof that the set S of illegal computations of AI is context-free.
Note that our proof actually shows how to construct a context-free grammar
G from A4 such that L(G) = S. More precisely, for each j = 1,2,... ,6, our
proof above shows we can construct either a regular expression or a PDA
for set Sj. From the work of Chapter 3, there are uniform procedures to
transform regular expressions and PDA’s to equivalent context-free grammars.
(For conditions (b), (e) and (f), we also need the procedures of Chapter 2 to
transform a regular expression to the regular expression of its complement.)
Therefore, we may construct, from IV, context-free grammars Gj such that
L(Gj) = Sj and we can combine them together to form the desired grammar
G.
Finally, we observe that if M does not halt on any string, then there is no
legal computation and so all strings in {O,l} are illegal. That is, L(G) =
{O,l}. On th e o th er hand, if A4 halts on some string, then there exists at
least one legal computation, and so L(G) # (0, l}*. Therefore, the above
construction of grammar G from DTM A4 is a reduction from EMP to the
given problem.^0
Corollary 5.44 The following problems about context-free grammars are un-
decidable:
(a) Given two context-free grammars G1 and Ga, determine whether L(G1)
c - L(G2).
(b) Given two context-free grammars G1 and G2, determine whether L(G1)
= L(G2).Proof. Let Go be a context-free grammar such that L(Go) = (0, 1)“. The
function f(G) = (Go, G) is a reduction from the problem of determining
whether L(G) = {O,l}* to both problem (a) and problem (b). cl
Next, we introduce an undecidable combinatorial word problem, called
the Post correspondence problem, and use it to prove additional undecidable
problems about context-free grammars.