Quiz 04 (March, 1st)

Statistics

There were 2 problems, each worth 10 points.

Problem 1

Informally argue that ALLDFA, the problem of whether a given DFA accepts all strings in its alphabet, is decidable. Argue from basic concetps rather than by citing any theorems that you might recall.

Solution

Let M be the input automaton. It is enough to test if any nonaccepting state is reachable from the start state of M. Reject if there is, accept otherwise.

Problem 2

Define a complex integer as being of form x + iy, where x and y are nonnegative integers and i is a square root of -1 (the imaginary unit). Argue that the complex integers are countable.

Solution

We could employ the following bijection:
   0 + 0i  --> 0

   0 + 1i  --> 1
   1 + 0i  --> 2

   0 + 2i  --> 3
   1 + 1i  --> 4
   2 + 0i  --> 5

   0 + 3i  --> 6
   1 + 2i  --> 7 
   2 + 1i  --> 8
   3 + 0i  --> 9
   ...

March, 2nd