Draw Turing machine configurations and find the output as asked in the questions below.
For questions 3 to 5, remember that a Turing machine starts in state 1, reading the leftmost nonblank cell.
1. Given the Turing machine instruction
(1,1,0,2,L)
and the configuration
... b 1 0 b ... (Tape read head is in state 1, and is over symbol 1 on the left)
Draw the next configuration.
2. A Turing machine contains only the following instructions:
(1,1,1,1,R)
(1,b,1,2,R)
Can this machine ever reach the following configuration? Explain your answer.
... b 0 1 b ... (Tape read head is in state 1, and is over symbol 1 on the left)
3. Find the output for the Turing machine
(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)
when run on the tape
... b 1 0 0 1 b ...
4. Find the output for the Turing machine
(1,1,1,2,L)
(2,b,0,3,L)
(3,b,1,4,R)
(4,0,1,4,R)
when run on the tape
... b 1 b ...
5. Describe the behavior of the Turing machine
(1,1,1,1,R)
(1,0,0,2,L)
(2,1,0,2,L)
(2,b,1,3,L)
(3,b,b,1,R)
when run on the tape
... b 1 0 1 b ...
Solution gives detailed explanations for question 2 and 5.
- Plain text response
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- Automata and Computability - A Turing machine with doubly infinite tape is similar to an ordinary Turing machine except that its tape is infinite to the left as well as to the right. The tape is initially filled with blanks exce ...
- Automata and Computability - Describe two different Turing machines, M and N, where, when started on any input, M outputs N and N outputs M.
- Automata and Computability - Show that all Turing-recognizable problems mapping reduce to ATM.
- Construct a turing machine to accept the language whose words are even palindromes. - Construct a turing machine that accepts the language {ww^R : w <- {a,b}+}, where w^R denotes w superscripted R - reverse of w. For example, if w = abb then w^R = bba ww^R = abbbba
- Construct a turing machine that checks the input sequence for equal number of 1s and 0s. - Give the transition list for a turing machine that will determine whether for an input sequence w over symbol set {0,1}, n0(w) = n1(w). n0(w) and n1(w) respectively indicate the count of 0s and 1s ...
