Chapter 10: Decidability and Recursively Enumerable Languages Q 317
We state the following theorem by Emil Post without proof.
Theorem 10.7 The PCP over 2: for 12:1 ;::: 2 is unsolvable.
It is possible to reduce the PCP to many classes of two outputs
(yes/no) problems in formal language theory. The following results can be
proved by the reduction technique applied to PCP.
1. If L 1 and L 2 are any two context-free languages (type 2) over an
alphabet 2: and 12:1 ;::: 2, there is no algorithm to determine whether or
not
(a) L] (l L 2 = 0,
(b) L 1 (l L 2 is a context-free language,
(c) L] k L 2 , and
(d) L 1 = L 2 •
2. If G is a context-sensitive grammar (type 1), there is no algorithm to
determine whether or not
(a) L(G) = 0,
(b) L(G) is infinite, and
(c) Xo E L(G) for a fixed string Xcr
3. If G is a type 0 grammar, there is no algorithm to determine whether
or not any string x E 2:* is in L(G).
10.7 SUPPLEMENTARY EXAMPLES
EXAMPLE 10.4
If L is a recursive language over 2:, show that I (I is defined as 2:* - L) is
also recursive.
Solution
As L is recursive, there is a Turing machine M that halts and T(M) =L. We
have to construct a TM M 1 , such that T(M 1 ) = [ and M 1 eventually halts.
M] is obtained by modifying M as follows:
1. Accepting states of M are made nonaccepting states of MI'
2. Let M 1 have a new state qf After reaching qfi M] does not move in
further transitions.
3. If q is a nonaccepting state of M and 6(q, x) is not defined, add a
transition from q to qf for lvh
As M halts, M 1 also halts. (If M reaches an accepting state on w, then M]
d.~es not accept wand halts and conversely.)
Also M] accepts w if and only if M does not accept w. So I is recursive.