Chapter 13: Q9E (page 864)
Construct a finite-state machine that delays an input string by two bits, giving 00 as the first two bits of output.
Short Answer
Therefore, the finite-state machine that delays input string by two bits, giving 00 as the first bits of output machine models is shown below:
Step by step solution
Over 22 million students worldwide already upgrade their learning with Vaia!
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.
Step 2: Construct a finite-state machine model
Given that the input string has two bits, giving 00 as the first two bits of output.
Construction:
Let us consider the states\({{\bf{s}}_{\bf{i}}}\), where\({\bf{i = 0,1,2,3,4}}\).
\({{\bf{s}}_0}\)is the starting state and will represent the fact that no bits were processed yet.
\({{\bf{s}}_1}\)represents the fact that the last two bits processed were 00 or that only one bit was processed.
\({{\bf{s}}_2}\)represents the fact that the last two bits processed were 01 or that only one bit was processed.
\({{\bf{s}}_3}\)represents the fact that the last two bits processed were 10.
\({{\bf{s}}_4}\)represents the fact that the last two bits processed were 11.
The first bit of the input always has to return 0, while the second bit also always has to return 0.
The third bit of the input needs to return the first bit of the input, the fourth bit of the input needs to return the second bit of the input, and so on.
Thus the resulting string is the input with two zeros placed in front and the last two digits removed.
The model of the finite-state machine is shown below.
Therefore, the result shows the required finite-state machine.
