1.1 A computer program which tells you the time returns different results at different times. Does this mean that it is non-deterministic?

1. Yes, it is non-deterministic.
2. Yes or no, it is non-deterministic because the results is different; but it is deterministic because it returns the correct time.
3. No, it is deterministic because the program performs the exact same operation.
4. No, it is deterministic because for any given time (i.e. for the same input) the result is same.

1.2 If A = {a,b} and B = {b,c}, what is A B and what is B A?

("" means difference, ref Formula Booklet)

1. A B = {a,b} and B A = {b,c}
2. A B = {b} and = B A = {b}
3. A B = {c} and = B A = {a}
4. A B = {a} and = B A = {c}

1.3 Which of the following regular expressions defines this language?

{ , 0, 1, 00, 01, 10, 11, 000, 001, }, that is, a set of all binary strings.

1. 0 | 1 | 00 | 01 | 10 | 11 | 000 | 001
2. (0 | 1)(00 | 01)(10 | 11)
3. (0 | 1)⁺
4. (0 | 1)*

1.4 Which of the following strings can NOT be described by the regular expression (a|b)*aaa(b)*?

1. aaa
2. baaab
3. aaaaaaabbaa
4. babaaaaaabb