38. (a) only
40. Only (a) and (d) are onto functions.
41. (a) Yes (b) No (c) Yes (d) No.
46. (a) Bijection
(b) None
47. {(1,1), (2, 2), (3, 3), (4,4)}
48. f g x
x
g f x
o
o
=
+ +
=
+
2
2
8 14
2
49. (a) R = {(3, 3), (6, 2), (9, 1)}
(b) Domain = {3, 6, 9}
Range = {3, 2, 1}
50. (a) R = {(3, 2), (5, 2), (5, 4), (7, 2), (7, 4), (7, 6), (9, 2), (9, 4), (9, 6),
(9, 8)}
(b) Domain = {3, 5, 7, 9}
Range = {2, 4, 6, 8}
51. (a) Transistive
(b) Reflexive, symmetric, transitive
(c) Symmetric
(d) Antisymmetric.
52. (a) 2
2
1
n n
(
)
+
(b) 2 3
2
1
n n n
(
)
−
(c) 3
2
1
n n
(
)
−
(d) 2
1
n n
(
)
−
(e) 2
2
1
n n
(
)
−
(f) 2
2 2
2
1
n
n n
− ⋅
−
(
)
53. R is reflexive if and only if ( , )
a a R
∈ for all a A
∈ if and only if
( , )
a a R
∈
−1 if and only if R
−1 is reflexive.
54. No, Example R = {( , ), ( , )}
13 31
56. (a) {( , ) |
a b b
a
divides }
(b) {( , ) |
a b a
b
does not divide }
57. (a) Symmetric, transitive
(b) Reflexive, symmetric, transitive
(c) Antisymmetric
58. L(G) = {b, aaa}
59. G = (V, T, S, P) where V = {0, 1, S} T = {0, 1}, S is the start symbol and
productions are
S
S
S
→
→
0 1
λ.
306
Theory of Automata, Formal Languages and Computation