(c) [5 points] Any DFA can be modified so that we have at most one trap state (by easily modifying the original DFA such that any transition leading to a trap state leads to a single particular trap state). Write the transition matrix of the automaton above (the one with the trap state). (d) [5 points] Draw all other DFAs for the planet if we know that initially there were exactly two individuals on the planet each from a different species (one possible automaton is provided in the problem description above. Draw the other two). (e) [5 points] Draw all DFAs for the planet if there were initially exactly three individuals on the planet. If some of the look exactly like each other except for the initial state, you can just simply draw it once without specifying which state is the initial state. Hint: There are only three unique automata (not considering different initial states).

StrangeNEWS just reported that suddenly a very VERY strange planet appeared out of nowhere! Three species, A,B and C are living on this planet. Any two different species can mate. If they do, two children will be born and they themselves will die. The planet will fail if there is only one kind of specie left (therefore, no more mating can take place). We denote mating between two individuals from B and C species by a. Similarly, we define b and c. We want to draw an automaton for any given initial number of species on the planet that tells us whether a sequence of mating is possible and/or causes the planet to fail. For example, let's say there is only one individual of species A and one of species B. Then, the only way that a mating can happens is if these two individual mate with each other (mating of type c ). We can draw a finite automaton for it as below: As you can see, final state in this automoton is when the planet failes (not more mating is possible or, in other words, there are only individuals from one species left on the planet). Moreover, we labelled each state by xyz where x,y and z are respectively the number of individuals of species A,B and C. If one of the numbers is larger than 9 , then we can use commas, like 3,2,10, to label a state. If we wanted to draw all transitions, the (complete) transition graph would have been as this