Consider all the possible FAs over the alphabet {a b} that have exactly two states. An FA must have a designated start state, but there are four possible ways to place the + 's:

Each FA needs four edges (two from each state), each of which can lead to either of the states. There are 2⁴ = 16 ways to arrange the labeled edges for each of the four types of FAs. Therefore, in total there are 64 different FAs of two states. However, they do not represent 64 nonequivalent FAs because they are not all associated with different languages. All type 1 FAs do not accept any words at all , whereas all FAs of type 4 accept all strings of a's and b's.
(i) Draw the remaining FAs of type 2.
(ii) Draw the remaining FAs of type 3.
(iii) Recalculate the total number of two-state machines using the transition table definition.

Transcribed Image Text:

OOOOOOOO ОО type 1 type 2 type 3 type 4