Give a high level description of the Turing machine then giv

Give a high level description of the Turing machine then give formal description of the TM and draw state diagram. {w | w is a string over alphabet {0, 1} and, either (i) w contains more 0s than 1s if it starts with a 0, or (ii) w contains more 1s than 0s if it starts with a 1} Some examples words in the language are as follows: 00, 01010, 1110, 0011100, 1010111, 1111, 11001011 Some examples of strings NOT in the language are as follows: 10, 01, 1000, 01011, 0001010111, 110100

Solution

Give implementation-level descriptions of TMs to decide the following languages over the alphabet {0,1}: 1. {w | w contains an equal number of 0s and 1s} Answer: The TM should follow the steps: 1. Search from left-to-right for a 0; when one is found, write x on the cell 2. Go back to the beginning and search for a 1, if one is found, write x on the cell; if none is found, reject. 3. Go back to step 1 4. If there are only x’s then accept; otherwise, reject 2. {w | w contains twice as many 0s as 1s} Answer: The TM should follow the steps: 1. Search from left-to-right for a 0; when one is found, write x on the cell 2. Go back to the beginning and search for a 1, if one is found, write x on the cell; if none is found, reject. 3. Go back to the beginning and search for another 1, if one is found, write x on the cell; if none is found, reject. 4. Go back to step 1 5. If there are only x’s then accept; otherwise, reject 5. Proofs! Show that decidable languages are closed under the operations of union and intersection. Answer: Let there be two decidable languages L1 and L2. Since they are decidable, then each has a decider M1 and M2, respectively, such that L(M1) = L1 and L(M2) = L2. We can prove that the union of these languages L = L1 L2 is also decidable by showing how we can build a decider M for L using the deciders for L1 and L2. We shall build our decider for L using a two-tape Turing machine which accepts any string in L1 L2: M = “On input string w, 1. Copy input string w to tape 2, so that both tapes now contain w. 2. Run M1 on tape 1; if M1 accepts w, then accept; if M1 rejects w then go to step 3. 3. Run M2 on tape 2; if M2 accepts w, then accept; if M2 rejects w then reject.” Since both M1 and M2 are deciders (i.e., they always halt) then M is also a decider – it will never loop. Moreover, we have seen in our lectures that every multitape TM has an equivalent single tape TM, so we can manipulate the definition above and make it a single tape TM. The intersection is done similarly, but the machine is defined as follows: M = “On input string w, 1. Copy input string w to tape 2, so that both tapes now contain w. 2. Run M1 on tape 1; if M1 accepts w, then go to step 3; if M1 rejects w then reject. 3. Run M2 on tape 2; if M2 accepts w, then accept; if M2 rejects w then reject.”