Short Answer

**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 by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1: Definition

Step 2: (a) Finding the finite-state machines

Step 3: (b) Detecting the finite-state units

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1: Definition

Step 2: (a) Finding the finite-state machines

Step 3: (b) Detecting the finite-state units

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths