CS 341 Automata Theory, Practice Quiz 1, Time = 12 minutes

1. The reflexive, transitive closure of the binary relation R = {(a, d), (d, c), (c, a), (d, d)} over the set A = {a, b, c, d} is :

1. {(a, a), (a, c), (a, d), (b, b), (c, a), (c, c), (c, d), (d, a), (d, c), (d, d)}
2. {(a, a), (a, c), (a, d), (c, a), (c, c), (c, d), (d, a), (d, c), (d, d)}
3. {(a, a), (a, b), (a, c), (a, d), (b, a), (b, b), (c, a), (c, b), (c, c), (c, d), (d, a), (d, b), (d, c), (d, d)}
4. {(a, a), (a, c), (c, c), (c, d), (d, a), (d, d)}
5. none of a-d

2. Which of the following is a partition of the set B = {a, b, c, d}

a. {{a, b}, {c}}

b. {{a, b}, {c, d}}

c. {{a, b}, {a, c, d}}

d. {{a, b}, {c, d}, {}}

e. none of a – d

3. Let A = {a, b, c, d, e}. How many elements are there in 2^A

a. 1

b. 25

c. 5

d. 32

e. none of a-d

4. Let A = {a, b, c, d, e}. How many elements are there in A^k (Generalized Cartesian Product)

a. 1

b. 5k

c. 5^k

d. k⁵

e. none of a-d

5. The relation R = {(a, a), (a, c), (b, c), (c, b)} over the set A = {a, b, c} is

a. reflexive

b. antisymmetric

c. symmetric

d. transitive

e. none of a – d

6. Which of the following sets is not equinumerous with the other four?

a. the set of integer

b. the set of all ordered pairs of integers

c. the set of positive integers

d. the set of even integers

e. the set of all subsets of integers

7. Let f: A ® B be a function such that its inverse f ^{–1 :} B ® A is also a function. f must be

a. 1-1 and into

b. many-one and into

c. 1-1 and onto

d. many-one and onto

e. none of a - d

8. What is the closure of even integers under subtraction?

a. the even integers

b. the postive integers

c. the odd integers

d. the negative integers

e. none of a – d

Answers: 1 a, 2 b, 3 d, 4 c, 5 e, 6 e, 7 c, 8 a