Design a state machine to recognize if a binary string contains any occurrence of the sequence...

Design a state machine to recognize if a binary string contains any occurrence of the sequence “10101”. Is it possible to design this state machine with less states? By using Finite State machine designer.

http://madebyevan.com/fsm/

Solutions

Expert Solution

Solution:

The finite state machine which detects the sequence 10101 is designed and plotted using Finite State Machine Designer tool and the image is attached here.

The design steps are follows.

1. It has to detect the sequence 10101 with overlapping is allowed. It changes its state for every clock pulse and input is taken.

2. Initially the FSM is in state S0 and when the input is one, it moves to state S1 otherwise it is in the same state.

3. From the state S1, when the input is zero, it moves to state S2 otherwise it is in the same state.

4. From the state S2, when the input is one, it moves to state S3 otherwise it is moved to state S0.

5. From the state S3, when the input is zero, it moves to state S4 otherwise it is moved to state S1.

6. From the state S4, when the input is one, it moves to state S3 and the output becomes one, otherwise it is moved to state S0.

5. From the state S2, when the input is one, it moves to state S3 otherwise it is moved to state S0.

Manojponduru answered 2 days ago

Next > < Previous

Related Solutions

Draw a state diagram of the string pattern recognizer, implement it according to the design sequence...

Draw a state diagram of the string pattern recognizer, implement it according to the design sequence of the FSM, and draw a schematic diagram.

1. Design a sequence detector, a Mealy finite state machine to detect the serial bit sequence...

1. Design a sequence detector, a Mealy finite state machine to detect the serial bit sequence 1101, where the most significant bit (MSB) comes first and the least significant bit comes last. A) Draw the state diagram B) Draw the state table C) The circuit is to be implemented using JK flip-flops and combinational logic circuit. Derive the Boolean expression necessary for this implementation. D) Sketch the circuit diagram for your design. This should show all the flipflops, logic gates...

Design a transducer to convert a binary string into octal. For example the bit string 001101110...

Design a transducer to convert a binary string into octal. For example the bit string 001101110 should produce 156. Please complete the code to account for the 7 cases of 3 digit binary strings. //Function binaryToOctal takes a char array digits of length 3 //Pre: digits contains 3 binary digits. //Post: function returns the octal number equivalent to the 3 binary digits int binaryToOctal( char digits[], int 3){ int number; if(digits[0]=='0') if (digits[1]=='1') if (digits[2]=='0') return 2;//found "010" else return...

for this set of assignment, Moore state machine Design a sequence detector to detect "001", where...

for this set of assignment, Moore state machine Design a sequence detector to detect "001", where 0 arrives first, then 0, then 1. You need to show the test sequences you used to confirm that your state diagram is operating correctly. When the complete "001" sequence has been detected, the output goes high. Otherwise, the output stays at zero. Shows your state diagram, state table, encoded state table (use minimized bit encoding), logic equations, and logic circuit. (30 points) 3....

A DNA string is a sequence of the bases a, c, g, and t in any...

A DNA string is a sequence of the bases a, c, g, and t in any order, whose length is usually a multiple of three. In reality, it is not necessarily a multiple of three, but we will simplify it as such for discussion. For example, aacgtttgtaaccagaactgt is a DNA string with a length of 21 bases. Recall that a sequence of three consecutive letters is called a codon. Assuming the first codon starts at position 1, the codons are...

Design a 8-to-3 binary encoder, with priority in binary sequence (i.e. input line 0 has higher...

Design a 8-to-3 binary encoder, with priority in binary sequence (i.e. input line 0 has higher priority than input line 1 etc). There should also be an "active" output which is 1 when any input line is active, and "0" when all input lines are 0. If all input lines are 0, the output lines other than the "active" output are "don't care".

An n-bit binary string is a sequence of length n over the alphabet {0,1}. How many...

An n-bit binary string is a sequence of length n over the alphabet {0,1}. How many n-bit binary strings are there? How many n-bit binary strings b1,…,bn are there such that b1b2≠00? In other words, how many n-bit binary strings don't begin with 00? How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and b2b3≠11? How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?

Design a pseudo-random state machine for this sequence: 1, 15, 8, 3, 12, 6, 5, 4....

Design a pseudo-random state machine for this sequence: 1, 15, 8, 3, 12, 6, 5, 4. Give a state diagram, excitation table, boolean expression, and a circuit diagram.

using any form of induction, that a binary string begins and ends with the same character...

using any form of induction, that a binary string begins and ends with the same character iff contains an even number of occurences of substrings from (01,10).

Java String search Design and implement a recursive version of a binary search. Instead of using a...

Java String search Design and implement a recursive version of a binary search. Instead of using a loop to repeatedly check for the target value, use calls to a recursive method to check one value at a time. If the value is not the target, refine the search space and call the method again. The name to search for is entered by the user, as is the indexes that define the range of viable candidates can be entered by the user (that are...

Subjects