CHAPTER 4
1. M
Q
q q
q
= ( , , , , ,
,
).
Σ Π δ 1 accept reject
Σ = { }
0
Γ = {0, x, £}
q 1 — start state
q accept — accept state
q reject — reject state
δ is described by the state diagram shown below.
9. ( , , , , )
s s R
0
0
0 0
( ,*, , , )
s
s B R
0
5
( , *, , *, )
3
3
s
s
L
( , , , , )
s s L
3
3
0 0
( , , , , )
s s L
3
3
1 1
(
)
s , B, s , B, R
3
0
( , , , , )
s s B R
5
5
1
( , , , , )
s s B R
5
5
0
(
)
s , B, s , B, L
5
6
( , , , , )
s B s B L
6
6
( , , , , )
s s L
6
7
0 1
(
)
s , , s , , L
7
2
0
1
( , , , , )
s s R
0
1
1 0
( , , , , )
s s R
1
1
1 1
(
)
s , B, s , B, L
2
4
( , , , , )
s s L
4
4
0 1
( ,*, , , )
s
s B L
4
8
(
)
s , , s , B,L
8
8
0
( , , , , )
s s B L
8
8
1
where B = Blank cell, L = Left and R = Right
13. ( , , , , ), ( , , , , ), ( , , , , ), ( , ,
s s R s s R s s R s s
0
0
0
1
1
1
1
0
0 0
1 1
0 0
1 , , ), ( , , , , ).
1
0
2
R s B s B R
14. ( , , , , ), ( , , , , ), ( , , , , ), ( , ,
s s R s s R s s R s s
0
1
0
0
1
1
1
0
0 0
1 0
0 0
1 , , ), ( , , , , )
0
1
2
R s B s B R
15. ( , , , , ), ( , , , , ), ( , , , , ), ( , , ,
s s R s s R s s R s s
0
0
0
1
1
1
1
0 0
1 1
0 0
1 0, )
R
16. ( , , , , ), ( , , , , )
s s R s s R
0
1
0
0
0 1
1 1
20. Since the universal Turing machine that simulates every Turing
machine, the present problem is equivalent to the Halting problem of
Turing machines, therefore, it is unsolvable.
CHAPTER 6
1. (a) 0
Answers to Exercises
317
→
→
→
→
→
→
→
→
→
→
→