Turing Machine Construction and reductions
Please show the graph of the machine with all edges labeled and please provide a brief description of the purpose of the states in your machines. You must use JFLAP to construct your Turng Machines.
For each TM you build, please add a BRIEF English description of how it operates. Make your English decription as clear as possible! Please note - this one may take some time so please get going on it SOON.
1. Construct a TM that recognizes the non-CFL language L = {wcw | w is in (0+1)*} and halts on all inputs. Please briefly explain the purpose of each state of your machine. So, for example the string 1110c1110 IS in L but the string 0010c0110 is NOT.
2. Construct a TM that expects a string of 0's and 1's and replaces all 1's with 0's and all 0's with 1's. For example, if started with the string 01110110 then the machine would halt with 10001001 on the tape. If it was started with 0001 then it would halt with 1110.
3 Suppose you had a Deterministic Turing Machine that at some point was in a state q over a tape that is completely blank except for one cell which contains a #. If the read/write head is currently over a blank cell and you do not know where the # lies with respect to the current position then what would you need to do to move the read/write head so that it is over the # and in state p how would you accomplish this? Describe how your machine would work. You do not need to actually construct the machine simply describe how it would work. NOTE - the TM MUST be deterministic.
4. Solve the previous problem with a non-deterministic Turing machine. Explain how the machine would work and how it differs from the deterministic version.
For each of the following languages - tell me if the language is Recursive, RE, or NON-RE. Prove your answer either by describing the TM for the language or by performing a Turing reduction of the appropriate form.
5. L1={ | L(M1) != L(M2) }
6. L2={ | there exists a w such that w ∈ L(M1) and w ∈ L(M2) }
7. L3 = { | 10001 ∈ L(M) }