Question

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

a) 0111

b) 11011011

c) 01010101010

Short answer

(a) Therefore, the output is 1100.

(b) Therefore, the output is 00110110.

(c) Therefore, the output is 11111111111

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 the state table

Referring to Example 2: The state table is shown below.

Given that, an input string is 0111.

Using the table generates the output.

Let us use the input string to find the output.

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

Hence, the output is 1100.

Generate the output using the state table

The given input string is 11011011.

Using the table generates the output.

Let us use the input string to find the output.

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

Therefore, the output is 00110110.

Given that, an input string 01010101010.

Using the table generates the output.

Let us use the input string to find the output.

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

So, the output is 11111111111.