7. 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 breeding can take place). When two individuals of breeds B and C mate, we denote it by a. Similarly, we define b and c. For any given initial number of species on the planet, we want to draw the automaton that tells us whether a sequence of mating is possible and/or causes the planet to fail. For example, let's say there is one individual of breed A and one of breed 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: 110 002 In the DFA above, we denoted each state by xyz where x,y and z are respectively the number of individuals of breeds A, B and C. If one of the numbers is larger than 9, then we can use commas, like 3, 2, 10 to represent a state. If we wanted to draw all transitions, the (complete) transition graph would have been as this: 110 002 b o DO a (U O Answer the following questions about this strange planet and the automata associated with it. (a) [2 points] What is the alphabet & in the DFA's associated with this strange planet? Also, describe what are the strings in the language specified by these automata. (b) (2 points] Describe the rule(s) that specifies whether a string belongs to the language. (c) [3 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. 7. 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 breeding can take place). When two individuals of breeds B and C mate, we denote it by a. Similarly, we define b and c. For any given initial number of species on the planet, we want to draw the automaton that tells us whether a sequence of mating is possible and/or causes the planet to fail. For example, let's say there is one individual of breed A and one of breed 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: 110 002 In the DFA above, we denoted each state by xyz where x,y and z are respectively the number of individuals of breeds A, B and C. If one of the numbers is larger than 9, then we can use commas, like 3, 2, 10 to represent a state. If we wanted to draw all transitions, the (complete) transition graph would have been as this: 110 002 b o DO a (U O Answer the following questions about this strange planet and the automata associated with it. (a) [2 points] What is the alphabet & in the DFA's associated with this strange planet? Also, describe what are the strings in the language specified by these automata. (b) (2 points] Describe the rule(s) that specifies whether a string belongs to the language. (c) [3 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
