Quiz 04 (March, 1st)
Statistics
There were 2 problems, each worth 10 points.
- Min: 0
- Median: 10
- Max: 20
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