Problem Solving in Automata, Languages, and Complexity

(^268) COMPUTABHJTY THEORY
(b) Given a grammar G and two strings x and y, determine whether x 3
Ye
(c) Given a grammar G and two strings x, y E L(G), determine whether
there is a derivation of x that is longer than the shortest derivation of
y. (The length of a derivation is the number of sentential forms in the
derivation.)
(d) Given a grammar G, determine whether L(G) = 8.
(e) Given two grammars G1 and G 2, determine whether L(G1) C - L(G2).
(f) Given a grammar G, determine whether L(G) is a context-free language
(i.e, for a given unrestricted grammar G, determine whether there is an
equivalent context-free grammar).
Proof (a) Let Al = {(G,x) 1 x E L(G)}. W e re d uce the halting problem I<* =
{(AI, x) 1 AI halts on 2) to Al. For any DTM M, let Gh be the grammar
defined in the proof of Theorem 4.20. Then, the mapping f(M, x) = (Gb, x)
is a reduction for li’o <m Al.
(b) Let A2 = {(GX,YJ I x a Yl- 73 e
G
mapping f (Al, x) = (GjM, S, x)
where S is the starting symbol of GIM, is a reduction for 1’0 <m AZ.
(c) Let A3 = {(G, x, y) 1 x, y E L(G) and th ere exists a derivation of x that
is longer than the shortest derivation of y}. We reduce Al to A3 as follows:
For any grammar Gr = (VI, Cl, Sr , RI) and any string x, we map them to
grammar G2 = (V2, Cl, S2, R2) and strings x and xa, where a is a symbol
in Cl, I.4 = V- U {Sz} and R2 contains all grammar rules of RI, plus the
following three rules: S2 + S1, S2 + x, and S2 + xa.
Then, x E L(G1) if and only if there is a derivation S2 ~~ x of length
greater than two. Since the shortest derivation of xa in G2 is of length two,
we see that x E L(G1) if and only if (G2, x, xa) E As.
(d) Let A4 = {G I L(G) = 0). The function f(M) = Gk is a reduction
from EMP to Ad.
(e) Let A5 = {(Gr, G2) I L(G1) C L(G2)). We can reduce A4 to A5 by the
function f(G) = (G, Go), w h ere GO;s the grammar with a single rule S -+ S,
where S is the starting symbol of Go and S $ C.
(f) Let As = {G I L(G) is context-free}. We observe, from Rice’s theorem,
that & = {x I VVz is a context-free language} is undecidable. The function
f(x) = G/M, is a reduction from I?6 to Ag, and so A6 is undecidable Cl
As we have seen
and grammars can
above, many undecidability resul ts about Turing machi
be proved by simple reductions from problems that h
.nes
ave
been proved undecidable in Section 5.4. For problems involving other compu-
tational models that are not known to be equivalent to the Turing machine
model (e.g., context-free grammars), the reductions for their undecidability
are more difficult.