Problem Solving in Automata, Languages, and Complexity

266 COMPUTABILITY THEORY Show that there exist integers m and n such that VVm = VVn = K and mEKandn$K. Use the recursion theore ...

5.6 Undecidable Problems 267 (c) We need to show that A3 = ((2, y, i) 1 A& enters state qi in its computation on input y} is ...

(^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 ...

5.6 Undecidable Problems 269 First, we consider context-free grammars. We note that the membership problem (given a context-free ...

270 COMPUTABILITY THEORY (d) For some odd i, 0 < i < nz, the ith c-block x and the (i + l)st c-block y of x do not satisfy ...

5.6 Undecidable Problems 271 regular expression of this set, and Q be the regular expression for the set of strings over (0, 1) ...

272 COMPUTABUJTY THEORY POST CORRESPONDENCE PROBLEM (PCP): Given a finite set of ordered pairs (~1, ~1) ,... , (zn, yn) of strin ...

5.6 Undecidable Problems 273 (1) [ H . [Bql1B* for each a E r U { *}. (4) cqia ---- cqza RR and for qjFb ’ qjcb , for each instr ...

274 COMPUTABILITY THEORY To prove this claim, the critical observation is that if we use top strings xi’s in -Pz to form a strin ...

5.6 Undecidable Problems 275 So, from the above induction proof, we know that either I[ a!0 * l l l * %+q+p* I I [ q) * l l l * ...

276 COMPUTABILITYTHEORY Then, L(G2) = {xi,xi, .*x;m$(yilyiz ..yim)R 1 i&,.. .,i, E (1,.. .,n}, m > 1). Now, if the instan ...

5.6 Undecidable Problems Exercises 5.6 277 1. For each of the following problems about Turing machines, determine whether it is ...

278 COMPUTABILITY THEORY Complete the details of the PDA Ml of Example 5.43. That is, construct a PDA A& which accepts the ...

5.6 Undecidable Problems 279 Figure 5.6: The problem TILING (cl,... , c4 denote four colors of tile to). Show that the problem T ...

6 Computational Complexity 6.1 Asymptotic Growth Rate In the last two chapters, we have established a computability theory and, ...

(^282) COMPUTATIONAL COMPLEXITY Figure 6.1: The Tower of Hanoi problem. from the third peg to the second peg. Let f(n) be th e n ...

6.1 Asymptotic Growth Rate 283 time f( 10) = 1023 is definitely acceptable; however, when the input size grows to n = 64, it bec ...

284 COMPUTATIONAL COMPLEXITY Exponential Sequence: { 2in 1 i = 1,2, l l 0). Superexponential Sequence: (an* 1 i = 1,2, l l l }. ...

6.1 Asymptotic Growth Rate 285 In the following, we any k > - 1, recall that Define log* n = min{k study a function that grow ...

286 COMPUTAT1ONAL COMPLEXITY Prove that log@+‘) 4 log(“) n for any k > - 0. Denote log* n = min{Ic 1 (log)% < - 1, k log* ...