Question

Suppose that S, I and O are finite sets such that \(\left| S \right| = n, \left| I \right| = k\), and \(\left| O \right| = m\).

\(a)\)How many different finite-state machines (Mealy machines) \(M = \left( {S,I,O,f,g,{s_0}} \right)\) can be constructed, where the starting state \({s_0}\) can be arbitrarily chosen?

\({\bf{b)}}\)How many different Moore machines \(M = \left( {S,I,O,f,g,{s_0}} \right)\) can be constructed, where the starting state \({s_0}\) can be arbitrarily chosen?

Short answer

a) There are \(n \times {n^{nk}} \times {m^{nk}}\) finite-state machines can be constructed

b) There are \(n \times {n^{nk}} \times {m^n}\) finite-state machines can be constructed

Step-by-step solution

Definition 

A finite-state automaton\(M = \left( {S,I,f,{s_0},F} \right)\)consists of a finite set\(S\)of states, a finite input alphabet I, a transition function f that assigns a next state to every pair of state and input (so that\(f:S \times I \to S\)), an initial or start state\({s_0}\), and a subset F of\(S\)consisting of final (or accepting states).

(a) Finding the finite-state machines 

To specify a machine, you need to pick a start state (this can be done in n ways), and for each pair (state, input) (and there are \(nk\) such pairs), you need to choose a state and an output. By the product rule, therefore, the answer is \(n \times {n^{nk}} \times {m^{nk}}\). A much harder question is to determine how many "really" different machines there are, since two machines that really do the same thing and just have different names on the states should perhaps be considered the same. You will not pursue this question.)

Therefore, there are \(n \times {n^{nk}} \times {m^{nk}}\) finite-state machines can be constructed

(b) Detecting the finite-state units

This is just like part (a), except that you do not need to choose an output for each transition, only an output for each state.

Thus, the term \({m^{nk}}\) needs to be replaced by \({m^n}\), and the answer is \(n \times {n^{nk}} \times {m^n}\)

Therefore, there are \(n \times {n^{nk}} \times {m^n}\) finite-state machines can be constructed.