FSM-Finite State Machine-Questions-Answers

The Sequential FSM Finite State Machine DIGIQ based questions are very important for any digital interview. Sharing a few of the FSM questions with answers.

The question sequence or pattern detector will be a fixed question in many written tests such as NVIDIA, Western Digital, Analog Devices, etc.

FSM Finite State Machine Questions and Answers

1. Design a finite state machine FSM for a serial two’s complement block and also draw the logic diagram associated with it by using D-flipflop.

Answer:
The main logic behind this is, start from the least significant bit and retain the bits until and first 1-bit has occurred. Once a 1-bit is found, start complementing the bits if 1 makes it 0 and if 0 make it 1. Note retain the first 1-bit. (Don’t complement it, complement the bit which follows that first 1-bit).
State Assignment:
Let us assume State ‘a’ represents that 1 has not occurred yet. and assume State ‘b’ the situation after the first one has occurred. State flow diagram:

Designing the above FSM using D-flipflop: Truth table:

Present State (PS)	Input	Next State (NS)	Output (Q)
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	0

Logic diagram:

2. An FSM is given as in the below diagram. find out

1. What is the output sequence for the given input data sequence 001010110110110111?
2. What is the behavior of the above Finite state machine?
3. Decide the Flip-flop which can be used by avoiding external logic gates.

Answer:

1. The output for the given input sequence will be 001100100100100101.
2. By Analyzing the above logic, FSM logic behaves as an ODD-serial-parity-indicator. Since the output is one when the number of input arrived till are in odd numbers.

3. Let us draw the truth table for the above logic

Present State (PS) Qn	Input X	Next State (NS) Qn+1	Output (Z)
0	0	0	0
0	1	1	1
1	0	1	1
1	1	0	0

Here, Z = Qn XOR X, Hence a T-flip-flop can be used.

3. Draw the state flow or transition diagram for a JK flip-flop and also give the truth table associated with it.

Answer:
The truth table

J	K	Qn	Qn+1
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

The state flow or transition diagram for a JK flip-flop

4. Given a sequential logic circuit expression as
X(t+1) = p’X+pY
Y(t+1) = pX’+p’Y
where X and Y are the two flip-flop outputs and p is the main external input.
Draw the state transition table for the above-given logic function.
Also, draw the state transition diagram associated with it.
And What is the behavior of the circuit?

Answer:
1. The state transition table is (PS-Present state, NS-Next state),

PS		Input	NS
X	Y	p	X(t+1)	Y(t+1)
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	1
1	0	0	1	0
1	0	1	0	0
1	1	0	1	1
1	1	1	0	0

2. The state transition diagram is

3. The above circuit behaves as an ENABLE-based-gray-counter.

5. Given the conditions, such that
If A = 0, the circuit oscillates between either one of the two cases. Case 1: 00-01-00-01… and Case 2: 10-11-10-11… And
If A = 1, it switches inter between two cases. Draw the state transition diagram and implement the same using JK flip-flop and by using basic logic gates.

Answer:
1. The FSM for the above problem statement can be drawn as

2. Implementation using JK flip-flop
Excitation table for JK flipflop is

Qn	Qn+1	J	K
0	0	0	X
0	1	1	X
1	0	X	1
1	1	X	0

The state transition for the above problem statement is

PS		Input	NS		JK Flip-flop inputs
A	B	x	A(t+1)	B(t+1)	JA	KA	JB	KB
0	0	0	0	1	0	X	1	X
0	0	1	1	0	1	X	0	X
0	1	0	0	0	0	X	X	1
0	1	1	1	1	1	X	X	0
1	0	0	1	1	X	0	1	X
1	0	1	0	0	X	1	0	X
1	1	0	1	0	X	0	X	1
1	1	1	0	1	X	1	X	0

Simplify using Karnaugh Map for the expressions JA, KA, JB, and KB. JA=x; KA=x; JB=x’; KB=x’;

6. Explain briefly with the difference between the Mealy model and Moore model.

Answer:

Mealy Model (depends on both input and PS)	Moore Model (depends only on Present State)
In the Mealy model, the next state outputs are associated with the change in the input and also the current or present state.	In the Moore model, the next state outputs are associated with the change in the present state only and not with change in inputs.
These models give the input immediately upon receiving the inputs.	Here, the output will change only when there is a change in the present state. like only during clock transitions.
Here, the chances of Glitches in the output, since the delay difference between state and input.	This model avoids Glitches in the output since it only depends on change in the present state (PS).

7. Design an FSM for serial sequence detector with the pattern “1010” with overlapping and with non-overlapping.

Answer:
Let us assume FSM for the Mealy model.
Four states

a (no 1 detected state),
b (one 1 detected state),
c (10 detected state),
and d (101 detected state).
The state transition diagram for the overlapping case will be

The state transition diagram for the non-overlapping case will be

8. Design an FSM for serial sequence detector with the pattern “0110” with non-overlapping. use Mealy Machine.

Answer:
Four states
a (no 0 detected state),
b (one 0 detected state),
c (01 detected state),
and d (011 detected state). The state transition or flow diagram for the non-overlapping case will be

9. Design an FSM (Finite state machine) which will detect three consecutive 1’s with overlapping. And use the Mealy Machine.

Answer:
Let assume three states
a (no 1 detected state)
b (one 1 detected state)
c (two or more the two 1’s detected state) The state flow diagram for the overlapping case will be

10. Optimize or simplify the following given truth table. Given the input sequence 01010101001. Start from the state a and write the next state and output sequence for both original and optimized tables.

PS	NS		Output
PS	x=0	x=1	x=0	x=1
a	a	b	0	0
b	e	c	0	1
c	a	d	0	1
d	e	f	0	1
e	a	f	0	0
f	g	d	0	1
g	a	b	0	0

Answer:
The optimized transition table will be

PS	NS		Output
PS	x=0	x=1	x=0	x=1
a	a	b	0	0
b	e	c	0	1
c	a	b	0	1
e	a	c	0	0

For original table

i/p		0	1	0	1	0	1	0	1	0	0	1
NS	a	a	b	e	f	g	b	e	f	g	a	b
o/p		0	0	0	0	0	0	0	0	0	0	0

For an optimized table:

i/p		0	1	0	1	0	1	0	1	0	0	1
NS	a	a	b	e	c	a	b	e	c	a	a	b
o/p		0	0	0	0	0	0	0	0	0	0	0

11. Design a finite state machine (FSM) that will detect more than one number 1’s, in the previous three samples. for example
Input Sequence 0101011001
Output Sequence 0001011100
Answer:

The idea is we need to design a complex sequence generator which will detect the patterns 011, 101, 110, and 111. Let us assume four different states
a = no 1 detected state.
b = one 1 detected state or 01 or 1 detected state.
c = two or more than two 1’s detected state.
d = 001/010 detected state. The FSM diagram is

12. Design a finite state machine which detects the pattern 101 in the previous four samples. for example

Input Sequence	0101001101010
Output Sequence	0001100001111

Answer:
Here, it is required to design an overlapping complex sequence detector that will detect the patterns 0101, 1101, 1010, and 1011. Let us assume four different states
a = no 1 detected state.
b = at least one 1 detected state.
c = the pattern 010 detected state.
d = the pattern 1101/0101 detected state. The finite state machine is

13. Design an FSM-finite state machine which detects the alternate 0’s and 1’s in the previous three samples. for example

Input Sequence	0010101101000
Output Sequence	0001111001100

Answer:
Here, we need to design a complex sequence detector that will detect the patterns 010 and 101. Let us assume four states
a = continuous 0’s or no 1 detected state.
b = one 1 detected state.
c = pattern 10 detected state.
d = continuous 1’s detected state. The finite state machine can be drawn as

14. Design an FSM (Finite State Machine) which eliminates the short length pulses. for example

Input Sequence	01001101100
Output Sequence	00000111110

Answer:
Here, the meaning of eliminating the short length pulses is removing 0’s which are between the continuous 1’s and similarly removing 1’s which are between the continuous 0’s. Let us made a 1 after two continuous 0’s as 0, and similarly a 0 after two continuous 1’s as 1. Let us consider four states
a = continuous 0’s detected state.
b = one 1 in the two 0’s detected state.
c = continuous 1’s detected state.
d = one 0 in the two 1’s detected state. The finite state machine can be drawn as

15. Design a finite state machine for a serial binary input which is divisible by 5. for example

Input	Sequence	Value	Output
0	0	0	0
1	01	1	0
0	010	2	0
1	0101	5	1
0	01010	10	1

Answer:
Let us make five state a, b, c, d, and e and each represents remainder 0, remainder 1, remainder 2, remainder 3, and remainder 4 respectively.
The finite state machine can be drawn as

16. Design an FSM- finite state machine to check whether the two inputs A and B have the same value for the previous three samples. Use Mealy machine for the design.
Answer:
Let us define or assign three samples in such a way that
State a when A is not equal to B,
State b when A is equaled to B for previous one sample, and
State c when A is equaled to B for the previous two samples.
The FSM can be drawn as

17. Design a sequential FSM to check if the number of 1’s in the given inputs together is multiple of 4 or not. Use Moore Machine for the design.
Answer:
It is a similar example which we already did earlier. The idea is to find the remainder at each state and deciding the multiple of four. Let us assume four states,
State a for remainder 0
State b for remainder 1
State c for remainder 2
State d for remainder 3
and the state machine diagram will be

18. Design a sequential finite state machine which becomes one if input M had two same values in the previous two active clock edges or the input N had been 1 since the last condition was true. Design FSM for a Moore machine. for example,

A	00110010110
B	00000011010
Output	01010111010

Answer:
Let us assume four states such as
State a the initial state or reset state.
At state b, the value of M is 0 and value N is X (either 0 or 1)
At state c, the value of M is 1 and value N is X (either 0 or 1)
At state d, assume M has the same value for the last two samples and is 0.
At state e, assume M has the same value for the last two samples and is 1.
The sequential finite state machine can be drawn for the above state assignment as

19. Design an FSM to detect even number of or odd number of 0’s or 1’s in the given serial input. Use the Moore machine for the design.
Answer:
Let us consider four different states as
In-state a, even number of 0’s and even number of 1’s
In-state b, even number of 0’s and an odd number of 1’s
In-state c, odd number of 0’s and even number of 1’s
In state d, an odd number of 0’s an odd number of 1’s
outputs will be in the form of one-hot encodings, such as 1000, 0100, 0010, and 0001.
The FSM for the given problem statement will be