Question

Find the output for each these input strings when given as input to the finite-state machine in Example 3.

a) 0000

b) 101010

c) 11011100010

Short answer

(a) Therefore, the output is 1111.

(b) Therefore, the output is 001001.

(c) Therefore, the output is 00110000110.

Step-by-step solution

General form

Finite-State Machines with Outputs (Definition):

A finite-state machine\({\bf{M = }}\left( {{\bf{S,}}\,\,{\bf{I,}}\,\,{\bf{O,}}\,\,{\bf{f,}}\,\,{\bf{g,}}\,\,{{\bf{s}}_0}} \right)\)consists of a finite set S of states, a finite input alphabet I, a finite output alphabet O, a transition function f that assigns to each state and input pair a new state, an output function g that assigns to each state and input pair output and an initial state\({{\bf{s}}_0}\).

Concept of input string and output:

An input string takes the starting state through a sequence of states, as determined by the transition function. As we read the input string symbol by symbol (from left to right), each input symbol takes the machine from one state to another. Because each transition produces an output, an input string also produces an output string.

Generate the output using a state diagram

Referring to Example 3: The state diagram is shown below.

The given input string is 0000.

Using the diagram generates the output.

Let us use the input string to find the output.

The output obtained is 1111. The successive states and outputs are shown below the table.

So, the output is 1111.

Generate the output using a state diagram

The given input string is 101010.

Using the diagram generates the output.

Let us use the input string to find the output.

The output obtained is 001001. The successive states and outputs are shown below the table.

Hence, the output is 001001.

The given input string is 11011100010.

Using the diagram generates the output.

Let us use the input string to find the output.

The output obtained is 00110000110. The successive states and outputs are shown below the table.

Therefore, the output is 00110000110.