Explain how a Turing Machine can simulate an arbitrary DFA. Use a 2-tape Turing Machine. It...

Explain how a Turing Machine can simulate an arbitrary DFA. Use a 2-tape Turing Machine. It can be done with a 1-Tape Turing Machine, but 2-tape will likely make the explanation more intuitive.

Expert Solution

Each transition in a DFA reads a character of input, follows a transition, then moves to the next character of input. Once all input has been read, the DFA accepts if it's in an accepting state and rejects otherwise.

You can directly simulate this with a Turing machine. Build the finite state control of the Turing machine by creating one state for each state in the DFA. For each transition in the DFA on the character c, replace that transition in the TM with one that, on reading character c, writes back some arbitrary character to the tape (it doesn't matter what) and then moving the tape head right (to the next spot on the tape). Then, for each state, introduce a transition on the blank symbol from that state either to the accept state of the TM or the reject state of the TM (based on whether that state is accepting or rejecting). This TM effectively runs the DFA by stepping manually across the input string and finally deciding whether to accept or reject at the end of the run

venereology answered 2 years ago

Create a 3-tape Turing machine that implements multiplication with binary numbers. The first tape and the...

Create a 3-tape Turing machine that implements multiplication with binary numbers. The first tape and the second tape hold the numbers being multiplied and the third tape holds the product of the first two tapes. The two binary numbers may be different lengths.

If you have a Turing machine with a tape that is not just linear at each...

If you have a Turing machine with a tape that is not just linear at each move, instead you have the ability to move up, down, left, or right. There is a single read/write head. The transition function looks like. The tape extends up and right infinitely. That is, you can never go left or down of where you start, but you can go infinitely up and to the right. Is this machine equivalent to the standard Turing machine model?...

Prove that a single-tape Turing Machine that is not allowed to write on the input portion...

Prove that a single-tape Turing Machine that is not allowed to write on the input portion of the tape can only recognize regular languages.

Turing machine A that does the following: • On its first and second tape, A receives...

Turing machine A that does the following: • On its first and second tape, A receives two strings w and v, w, v ∈ {0, 1}? , representing two integer numbers. When machine A is started, the tape heads are located on the left-most position, on the most significant bits of w and v. • If none of the inputs w and v is the empty word, the Turing machine A writes the binary representation of the sum of the...

Prove that the language L={(M, N): M is a Turing machine and N is a DFA...

Prove that the language L={(M, N): M is a Turing machine and N is a DFA with L(M) =L(N)} is undecidable. You need to derive a reduction from Atm={(M, w)|Turing machine M accepts w} to L. (In layman's terms please, no other theorems involved)

Find the output for the following Turing machine when run on the tape b1001b, assuming that...

Find the output for the following Turing machine when run on the tape b1001b, assuming that the machine begins in state 1 and on the left side of the tape. (1, 1, 1, 2, R) (1, 0, 0, 2, R) (1, b, 1, 2, R) (2, 0, 0, 2, R) (2, 1, 0, 1, R)

Can you give me a turing machine for the language c* n b2n a n+2 for...

Can you give me a turing machine for the language c* n b*2n a* n+2 for n>=0 . Please give the entire diagram with states, transition function, alphabet. Can use either one-tape or two-tape (both infinite). Describe the logic used to build the machine. Run the TM that accepts for any string of length > 1. Also run for string cbba.

This investigation will involve measuring how high people can jump. Use of tools, such as tape...

This investigation will involve measuring how high people can jump. Use of tools, such as tape measures and rulers, should be considered. 1. Collect data. 2. Calculate the means and the five-number summaries for the entire sample and for each of your categories of the qualitative variable (e.g., for male and for female) and make a chart that presents those statistics. 3. Create comparative boxplots for the different groups (e.g., male and female). 4. Describe where your own jump-height falls...

Explain, with reasons, whether you can use the following tests to simulate the behavior of sand...

Explain, with reasons, whether you can use the following tests to simulate the behavior of sand in liquefaction i) Unconsolidated Undrained Triaxial Test ii) Direct Shear Test iii) What is the most suitable type of triaxial test that should be used? (Does not have to be (i) or (ii))

Design a Turing Machine to construct the function f(n) = 4 [1/4 n] + 2, (that...

Design a Turing Machine to construct the function f(n) = 4 [1/4 n] + 2, (that is, 2 more than 4 times the integer part of 1/4 n) for n Element N. Do not just produce a TM, but also describe briefly how it works. There is a TM in the Cooper notes that does something similar. You may modify it to produce the required TM, or produce a machine totally independently.

Question