• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q17SE

Expert-verified
Found in: Page 901

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# 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?

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

See the step by step solution

## Step 1: 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).

## Step 2: (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

## Step 3: (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.