60. G 1 : V
S
T
=
=
{ , , },
{ , }
0 1
0 1 .
Production P: S
S S
S S
→
→
→
0
1
,
,
λ
G 2 : V
S A
T
=
=
{ , , , },
{ , }
0 1
0 1
Productions P: S
S S
A S
A
A A
S
→
→
→
→
→
→
0
1
1
1
1
,
,
,
,
,
.
λ
61. G V T S P
= ( , , , )
V = {0, 1, 2, S, A, B}
T = {0, 1, 2}
S = Starting state
Productions P: S
SAB S
BA
AB
A
A
B
B
→
→
→
→
→
→
→
0
0
01 1
11 1
12 2
22
,
,
,
,
,
,
.
λ
62. (a) S
S S
→
→
00 ,
λ
(b) S
AS S
ABS S
A AB
BA BA
AB A
B
→
→
→
→
→
→
→
,
,
,
,
,
,
0
1
(c) S
ABS S
AB
BA BA
AB A
B
→
→
→
→
→
→
,
,
,
,
,
λ
0
1
(d) S
ABS S T B U T
AT T
A
U
BU U
B AB
BA BA
AB A
B
→
→
→
→
→
→
→
→
→
→
→
,
,
,
,
,
,
,
,
,
,
0
1.
69. Let P(n) be
3 5
3 5
1 4
1
0
⋅ =
−
+
=
∑
j
n
j
n
(
) / .
Basis: P(0) is true time since 3 5
3 3 5 1 4
1
0
⋅ = =
−
=
∑
j
j
n
(
) / .
Induction: Assume that 3 5
3 5
1 4
1
0
⋅ =
−
+
=
∑
j
n
j
n
(
) / .
Then
3 5
3 5
3 5
3 5
1 4 3 5
0
1
0
1
1
⋅ =
⋅





 + ⋅
=
−
+ ⋅
=
+
=
+
+
∑
∑
j
j
n
j
j
n
n
n
n
(
)
+
+
+
+
=
+
−
=
−
1
1
1
2
3 5
45
1 4
3 5
1 4
(
.
)
(
) .
n
n
n
72. Postages are 5 cents, 6 cents, 10 cents, 11 cents, 12 cents, 15 cents, 16
cents, 17 cents, 18 cents and all postages of 20 cents or more.
CHAPTER 1
1. (a)
(b)
Answers to Exercises
307
q 0
q 1
b
a
b
q 0
q 1
b
a
b
a