This homework covers:
(10 points) The variables x1, …, xk have infinitely many possible settings. A Turing machine would require infinite time to try them all. But, we require that every stage in the Turing machine description be completed in a finite number of steps.
a){w| w contains and equal number of 0s and 1s} ANSWER IS IN BOOK
Chapter 3: 3.6, 3.7, and 3.8 (with a part d that I added).
Copyright By PowCoder代写 加微信 powcoder
CISC 4090, Theory of Computation HW6 Solutions (50 points total)
(10 points) In Stage 2 of this algorithm: “Run M on si”, if M loops on a certain input si, then E would not check any inputs after si. If that were to occur, E might fail to enumerate L(M) as required.
b) (10 points) {w|w contains twice as many 0s as 1s} On input string w:
1. Scan the tape and mark the first 0 which has not been marked. If there is no unmarked 0, go to stage 5.
2. Continue scanning and mark the next unmarked 0. If there is not any on the tape, reject. Otherwise, move the head to the front of the tape.
3. Scan the tape and mark the first 1 which has not been marked. If there is no unmarked 1, reject.
4. Move the head to the front of the tape and repeat stage 1.
5. Move the head to the front of the tape. Scan the tape for any unmarked 1s. If
none, accept. Otherwise, reject.
c) (10 points) {w|w does not contain twice as many 0s as 1s} On input string w:
1. Scan the tape and mark the first 0 which has not been marked. If there is no unmarked 0, go to stage 5.
2. Continue scanning and mark the next unmarked 0. If there is not any on the tape, accept. Otherwise, move the head to the front of the tape.
3. Scan the tape and mark the first 1 which has not been marked. If there is no unmarked 1, accept.
4. Move the head to the front of the tape and repeat stage 1.
5. Move the head to the front of the tape. Scan the tape for any unmarked 1s. If
none, reject. Otherwise, accept.
d) (10 points) This is the part I added: {w| w is of the form aibici} On the input string w:
1. Scan the tape once to make sure that the symbols are in the proper order. If not, reject. Otherwise, return the tape head to the start and continue.
2. Scan the tape for the first unmarked a. If none is found, check the rest of the tape for any unmarked b’s or c’s. If any found, then reject; else accept. If an unmarked a is found, then mark it and continue to step 3.
3. Scan the tape for the next unmarked b. If none is found, then reject. If one is found, then mark it and continue to step 4.
4. Scan the tape for the next unmarked c. If not found, then reject; else mark it and return the tape head to the start position. Loop back to step 2.
If step 1 is missing that is not exactly an error since I may have said that this is easy to check strings are in the proper format. But ideally you should check this.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com