0:0.R 1:1,R 0ju, R 1;u.R U;u,L 0 91 92 0;u,L 1:4.L 1;0,L 0:0,L 93 94 1;1,L 0;1,L u;0,R u;1,R 95

Systems Architecture
7th Edition
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Stephen D. Burd
Chapter3: Data Representation
Section: Chapter Questions
Problem 7RQ
icon
Related questions
Question

(b) The following is the state diagram of a Turing machine M1 with input
alphabet {0, 1} and accept state q5. (Missing transition arrows are assumed to lead to a reject state, not shown.)

(i) Give the sequence of configurations of M1 on the input string 01,
starting with initial configuration q001. [6]
(ii) In general, given any input string w, what will the tape contents
of M1 look like after halting? [3

0:0.R
1:1,R
0ju, R
1;u.R
U;u,L
0
91
92
0;u,L
1:4.L
1;0,L
0:0,L
93
94
1;1,L
0;1,L
u;0,R
u;1,R
95
Transcribed Image Text:0:0.R 1:1,R 0ju, R 1;u.R U;u,L 0 91 92 0;u,L 1:4.L 1;0,L 0:0,L 93 94 1;1,L 0;1,L u;0,R u;1,R 95
Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Recommended textbooks for you
Systems Architecture
Systems Architecture
Computer Science
ISBN:
9781305080195
Author:
Stephen D. Burd
Publisher:
Cengage Learning
Programming Logic & Design Comprehensive
Programming Logic & Design Comprehensive
Computer Science
ISBN:
9781337669405
Author:
FARRELL
Publisher:
Cengage
Fundamentals of Information Systems
Fundamentals of Information Systems
Computer Science
ISBN:
9781305082168
Author:
Ralph Stair, George Reynolds
Publisher:
Cengage Learning
Operations Research : Applications and Algorithms
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
C++ Programming: From Problem Analysis to Program…
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
CMPTR
CMPTR
Computer Science
ISBN:
9781337681872
Author:
PINARD
Publisher:
Cengage