Chapter 13: Q18E (page 865)
Construct a finite-state machine that determines whether the input string read so far ends in at least five consecutive 1s.
Short Answer
Therefore, the finite-state machine model 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 read so far ends in at least five consecutive 1s.
The input is a bit string.
Construction:
Let us consider the states\({{\bf{s}}_{\bf{i}}}\), where\({\bf{i = 0,1,2,}}3{\bf{,}}4{\bf{,}}5\).
\({{\bf{s}}_0}\)is the start state. And will represent the fact that no bits were processed yet or that the last bit processed was a 0.
\({{\bf{s}}_1}\)represents that the last digit was a 1 but there were no digits before that or a 0.
\({{\bf{s}}_2}\)represents that the last digit was an 11 but there were no digits before that or a 0.
\({{\bf{s}}_3}\)represents that the last digit was a 111 but there were no digits before that or a 0.
\({{\bf{s}}_4}\)represents that the last digit was an 1111 but there were no digits before that or a 0.
\({{\bf{s}}_5}\)represents that the last digit was a 11111 but there were no digits before that or a 0.
The output is always 0 except when we move to state \({{\bf{s}}_5}\) or remain at \({{\bf{s}}_5}\).
The model of the finite-state machine is shown below:
Therefore, the result shows the required finite-state machine.
