Material for Quiz Nine

7.2:   2-7, 10
10.4:  1-10
10.5:  1, 11, 16-20, 22-28, 31-33, 41, 44

Quiz 9
Average Score: 7.03

1. Given the following state transition table, draw the transition diagram,
and find the language accepted by the automaton.

State  0  1
-> 0   0  1
   1   2  3
@  2   2  3
   3   2  3

	The language consists of all the strings with arbitrarily many 0's,
one 1, and at least one 0, i.e. 0*100* .

2.  Let A be the set (1,2,3,5,6,10,15,30).  Consider the relation R
defined as aRb iff a divides b.  Draw the Hasse diagram of this relation.

Answer: Ask me Friday.  There's no way I can do this in vi .

3.  Consider the set of natural numbers N and the relation R on NxN 
defined as (a,b)R(c,d) iff a<=c or b<=d.
a) is R reflexive?  Yes.
b) is R Antisymmetric?  No.  (1,10)R(5,5), and (5,5)R(1,10)
c) is R Transitive?  No.  (5,10)R(20,1) and (20,1)R(2,3), but 
	(5,10)/R(2,3)