Need a better explanation of this lengthy DFA word problem ( CS : Formal Language & Automata course)

Question

I read this problem multiple times and still don't quite understand it. I just need some help understanding what's going on here.

So, I understand that there are three types of "species": A, B and C. Are these species alphabets Σ? Also, in the first DFA listed in the problem, the 110 state: what do those numbers represent exactly? I know they're

xyz where x, y and z are respectively the number of individual of breeds

But I don't understand what 110 means in the first state. Does it mean A and B have 2 children of its own or that A and B mated?

The questions from this problem are:

(a) 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) Describe the rule(s) that specifies whether a string belongs to the language.

(c) 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.

(d) Draw all other DFA’s for the planet if we know that initially there were ex- actly two individuals on the planet (one possible automaton is provided in the problem description above. Draw the other “two”)

(e) Draw all DFA’s for the planet if they were initially exactly three individuals on the planet. If some of them 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.

(f) We define three types of states as follows: i. must-fail states: Those states that certainly will lead to a failed planet. ii. might-fail states: Those states that can lead to a failed planet. iii. cannot-fail states: Those states that can never lead to a failed planet. List all must-fail, might-fail and cannot-fail states with three individuals.

(g) Draw the automaton with the initial state of 121. What type each of the state in this automaton are?

If I could get some help understanding this problem and help with the first 2 questions, I would greatly appreciate it! I'm trying to solve it but I just can't quite understand it. Thank you!

Answer 1

But I don't understand what 110 means in the first state. Does it mean A and B have 2 children of its own or that A and B mated?

It means the planet has 1 A, 1 B and 0 C. The resulting transition c, indicates that 1 A and 1 B mated and died, producing 2 C. Ergo, the planet then has 0 A, 0 B and 2 C, so the state is called 002.

(a) 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.

From the diagram, the alphabet is {a, b, c}. a represents a B and C mating, b represents a A and C mating, c represents a B and C mating.

(b) Describe the rule(s) that specifies whether a string belongs to the language.

This is quite complicated. The DFA is going to depend on the number of individuals of each species in the starting state. Basically, transitions are doing math to three variables A, B and C. Each transition subtracts 1 from two variables, and adds 2 to the third - this means that transitions are only possible when at least two of the variables are non-zero.

Consider state 111. There are three possible transitions to three possible states: a -> 300, b -> 030 and c -> 003. We consider these "failed" planets, because no more breeding can happen, so these are accepting states.

Consider state 220. Transition c gets us to state 112. a gets us to 301. b gets us back to 220. This is a loop! So infinite strings are possible.

Notice that the sum of the variables A, B and C are constant. Every state has to have the same sum. So the number of states, at most, will be every possible way to express that sum with three non-negative integer terms.

Continue to explore properties like the above to understand more about the transitions. I'll leave that for you as an exercise.