(a) Give the sequence of configurations that the following TM M enters when given as input...

Transcribed Image Text:

(a) Give the sequence of configurations that the following TM M enters when given as input strings 1# #1 and 0#0. Please use the same representation for your configurations as we did in lecture 10. The reject state and transitions to the reject state are not shown. Whenever the TM encounters a character for which there is no explicit transition that means that the TM goes to the reject state. We say that the head moves right in each of these transitions to the reject state. start x → R 91 0→x, R 0,1→ RC 92 #→R →R 94 0,1→ 0,1→L 97 #→→R 1→x, R x→R 98 0,1 → R 93 0→x, L #→L qaccept 1 R x→R 95 1 → x, L # → R 960, 1, x→ L (b) Give an implementation level description of a TM, possibly nondeterministic and/or with multiple tapes, that recognizes the following language over the alphabet {0,1}: {s#a1#az#... #an| where n is a positive integer, s, a₁,..., an are binary integers such that some subset of a₁,..., an sums to s}. (c) Give a state diagram of the TM whose implementation level description is below. "On input w 1. If the first symbol is blank then accept. If it is b then reject. If it is a then erase this a and go to the right and go to the next step. 2. Move the head on the tape right until the blank symbol is found. After it is found move the head to the left (to the last symbol of the string) and go to the next step. 3. If the last symbol is not b then reject. Otherwise, erase this b and go to the left and go to the next step. 4. Move the head on the tape left until the blank symbol is found. After it is found move the head to the right (to the first symbol of the string) and go back to step 1." (d) What language is decided by the TM from (c)? (a) Give the sequence of configurations that the following TM M enters when given as input strings 1# #1 and 0#0. Please use the same representation for your configurations as we did in lecture 10. The reject state and transitions to the reject state are not shown. Whenever the TM encounters a character for which there is no explicit transition that means that the TM goes to the reject state. We say that the head moves right in each of these transitions to the reject state. start x → R 91 0→x, R 0,1→ RC 92 #→R →R 94 0,1→ 0,1→L 97 #→→R 1→x, R x→R 98 0,1 → R 93 0→x, L #→L qaccept 1 R x→R 95 1 → x, L # → R 960, 1, x→ L (b) Give an implementation level description of a TM, possibly nondeterministic and/or with multiple tapes, that recognizes the following language over the alphabet {0,1}: {s#a1#az#... #an| where n is a positive integer, s, a₁,..., an are binary integers such that some subset of a₁,..., an sums to s}. (c) Give a state diagram of the TM whose implementation level description is below. "On input w 1. If the first symbol is blank then accept. If it is b then reject. If it is a then erase this a and go to the right and go to the next step. 2. Move the head on the tape right until the blank symbol is found. After it is found move the head to the left (to the last symbol of the string) and go to the next step. 3. If the last symbol is not b then reject. Otherwise, erase this b and go to the left and go to the next step. 4. Move the head on the tape left until the blank symbol is found. After it is found move the head to the right (to the first symbol of the string) and go back to step 1." (d) What language is decided by the TM from (c)?