8. Since there are some grammars for which L(G) = L(G) * and some for which
this is not so, the undecidability follows from Rice's theorem. To do this
from first principles is a little harder. Take the halting problem (M, w) and
modify it(along the lines of Theorem 12.4), so that if (M, w) halts, will
accept {a} * and if (M, w) does not halt, accepts ø. From get the
grammar
by the construction leading to Theorem 11.7. If
.
But
if
,
then
. Therefore, if this problem were decidable, we
could get a solution of the halting problem.
Section 12.3
1. A PC-solution is w 3 w 4 w 1 = v 3 v 4 v 1 . There is no MPC solution because one
string would have a prefix 001, the other 01.
3. If |w i | > |v i | or |w i | < |v i | for all i, then clearly there is no solution. If this
condition does not hold, then either |w i | = |v i |, for some i, which has a trivial
solution, or there must exist a j and a k such that |w j | > |v j | and |w k | < |v k |. In
the latter case, the PCP has a solution
, where
.
5. (a) The problem is undecidable. If it were decidable, we would have an
algorithm for deciding the original MPC problem. Given w 1 , w 2 …; w n ,
we form
and use the assumed algorithm. Since
, the original MPC problem has a solution if
and only if the new MPC problem has a solution.
Section 12.5
1. (a) Find the middle of the string, then go back and forth to match
symbols. Both parts take O(n 2 ) moves.
(b) Count the number of symbols. If the count is done in unary, this is an
O(n) operation. Next, write the first half on the second tape. This is also
an O(n) operation. Finally, you can compare in O(n) moves.
(c) You can guess the middle of the string nondeterministically in one
move. But the matching still takes O(n 2 ) moves.
this is not so, the undecidability follows from Rice's theorem. To do this
from first principles is a little harder. Take the halting problem (M, w) and
modify it(along the lines of Theorem 12.4), so that if (M, w) halts, will
accept {a} * and if (M, w) does not halt, accepts ø. From get the
grammar
by the construction leading to Theorem 11.7. If
.
But
if
,
then
. Therefore, if this problem were decidable, we
could get a solution of the halting problem.
Section 12.3
1. A PC-solution is w 3 w 4 w 1 = v 3 v 4 v 1 . There is no MPC solution because one
string would have a prefix 001, the other 01.
3. If |w i | > |v i | or |w i | < |v i | for all i, then clearly there is no solution. If this
condition does not hold, then either |w i | = |v i |, for some i, which has a trivial
solution, or there must exist a j and a k such that |w j | > |v j | and |w k | < |v k |. In
the latter case, the PCP has a solution
, where
.
5. (a) The problem is undecidable. If it were decidable, we would have an
algorithm for deciding the original MPC problem. Given w 1 , w 2 …; w n ,
we form
and use the assumed algorithm. Since
, the original MPC problem has a solution if
and only if the new MPC problem has a solution.
Section 12.5
1. (a) Find the middle of the string, then go back and forth to match
symbols. Both parts take O(n 2 ) moves.
(b) Count the number of symbols. If the count is done in unary, this is an
O(n) operation. Next, write the first half on the second tape. This is also
an O(n) operation. Finally, you can compare in O(n) moves.
(c) You can guess the middle of the string nondeterministically in one
move. But the matching still takes O(n 2 ) moves.