# Finite State Machine and Miscellaneous

 Question 1
The state transition diagram for the circuit shown is
 A A B B C C D D
GATE EC 2019   Digital Circuits
Question 1 Explanation:
When $A=0, Q_{n+1}=1$
When $A=1, Q_{n+1}=\bar{Q}_{n}$
So, the correct state transition diagram is,

 Question 2
In the circuit shown below, a positive edge-triggered D Flip-Flop is used for sampling input data $D_{in}$ using clock CK. The XOR gate outputs 3.3 volts for logic HIGH and 0 volts for logic LOW levels. The data bit and clock periods are equal and the value of$\Delta T/T_{CK} = 0.15$, where the parameters $\Delta T$ and $T_{CK}$ are shown in the figure. Assume that the Flip-Flop and the XOR gate are ideal.
If the probability of input data bit $( D_{in})$ transition in each clock period is 0.3, the average value (in volts, accurate to two decimal places) of the voltage at node X , is _______.
 A 0.84 B 0.62 C 0.12 D 0.92
GATE EC 2018   Digital Circuits
Question 2 Explanation:

\begin{aligned} V_{X(\mathrm{avg})} &=\left[0.3 \times 3.3\left(1-\frac{\Delta T}{T_{C K}}\right)\right]+[0.7 \times 0] \mathrm{V} \\ &=0.3 \times 3.3 \times(1-0.15) \mathrm{V} \\ &=0.3 \times 3.3 \times 0.85 \mathrm{V}=0.8415 \mathrm{V} \end{aligned}
 Question 3
A traffic signal cycles from GREEN to YELLOW, YELLOW to RED and RED to GREEN. In each cycle, GREEN is turned on for 70 seconds, YELLOW is turned on for 5 seconds and the RED is turned on for 75 seconds. This traffic light has to be implemented using a finite state machine (FSM). The only input to this FSM is a clock of 5 second period. The minimum number of flip-flops required to implement this FSM is _______.
 A 4 B 5 C 6 D 7
GATE EC 2018   Digital Circuits
Question 3 Explanation:
\begin{aligned} \text{GREEN }&\rightarrow 70 \text{seconds}\\ \text { YELLOW } & \rightarrow 5 \text { seconds } \\ \text { RED } &\rightarrow 75 \text { seconds }\\ \text{Clock period }&\rightarrow 5 \text{seconds }\\ \end{aligned}
Total number of unique states required
$=\frac{70+5+75}{5}=30$
Minimum number of flip-flops required is,
$n=\left\lceil\log _{2}(30)\right\rceil=\lceil 4.91\rceil=5$
 Question 4
The state diagram of a finite state machine (FSM) designed to detect an overlapping sequence of three bits is shown in the figure. The FSM has an input 'In' and an output 'Out'. The initial state of the FSM is $S_{0}$.

If the input sequence is 10101101001101, starting with the left-most bit, then the number times 'Out' will be 1 is __________.
 A 2 B 3 C 4 D 5
GATE EC 2017-SET-2   Digital Circuits
Question 4 Explanation:
By observing the given state diagram, it is clear that the FSM can be used to detect the sequence '101'
It is given in the question that, the FSM detects overlapping sequences also. The given input sequence is,
$\underline{101}0\underline{110}1001\underline{101} \quad \Rightarrow$So, Output will be 1 for 4 times.
 Question 5
A finite state machine (FSM) is implemented using the D flip-flops A and B, and logic gates, as shown in the figure below. The four possible states of the FSM are $Q_{A}Q{B}$=00,01,10 and 11.

Assume that $X_{1N}$ is held at a constant logic level throughout the operation of the FSM. When the FSM is initialized to the state $Q_{A}Q_{B}$=00 and clocked, after a few clock cycles, it starts cycling through
 A all of the four possible states if $X_{IN}=1$ B three of the four possible states if $X_{IN}=0$ C only two of the four possible states if $X_{IN}=1$ D only two of the four possible states if $X_{IN}=0$
GATE EC 2017-SET-1   Digital Circuits
Question 5 Explanation:
In the given diagram,
$D_{A}=Q_{A} \oplus Q_{B} \text { and } D_{B}=\overline{Q_{A} X_{I N}}$
For $X_{I N}=0:$
$D_{A}=Q_{A} \oplus Q_{B} \text { and } D_{B}=1$

So, for $X_{I N}=0,$ Number of possible states =2
$For X_{I N}=1$
$D_{A}=Q_{A} \oplus Q_{B} \text { and } D_{B}=\bar{Q}_{A}$

So, for $X_{IN}=1$ of possible states = 3
 Question 6
The state transition diagram for a finite state machine with states A, B and C, and binary inputs X, Y and Z, is shown in the figure.

Which one of the following statements is correct?
 A Transitions from State A are ambiguously defined. B Transitions from State B are ambiguously defined C Transitions from State C are ambiguously defined. D All of the state transitions are defined unambiguously
GATE EC 2016-SET-2   Digital Circuits
Question 6 Explanation:
For State A

For State B

For State C

In state 'C' when X Y Z= 111 ; the ambiguity occurs. Because from state 'C'
\begin{aligned} \text{When, }\quad X&=1\\ Z&=1 \Rightarrow \text { Next state }=A \\ \text{When, }\quad Y&=1\\ Z&=1 \Rightarrow \text { Next state }=B \end{aligned}
 Question 7
Transistor geometries in a CMOS inverter have been adjusted to meet the requirement for worst case charge and discharge times for driving a load capacitor C. This design is to be converted to that of a NOR circuit in the same technology, so that its worst case charge and discharge times while driving the same capacitor are similar. The channel lengths of all transistors are to be kept unchanged. Which one of the following statements is correct?
 A Widths of PMOS transistors should be doubled, while widths of NMOS transistors should be halved. B Widths of PMOS transistors should be doubled, while widths of NMOS transistors should not be changed. C Widths of PMOS transistors should be halved, while widths of NMOS transistors should not be changed. D Widths of PMOS transistors should be unchanged, while widths of NMOS transistors should be halved.
GATE EC 2016-SET-2   Digital Circuits
 Question 8
The digital logic shown in the figure satisfies the given state diagram when $Q_{1}$ is connected to input A of the XOR gate.

Suppose the XOR gate is replaced by an XNOR gate. Which one of the following options preserves the state diagram ?
 A Input A is connected to $\bar{Q}_{2}$ B Input A is connected to ${Q}_{2}$ C Input A is connected to $\bar{Q}_{1}$ and S is complemented D Input A is connected to $\bar{Q}_{1}$
GATE EC 2014-SET-1   Digital Circuits
Question 8 Explanation:

Initially when X-OR gate is connected to the input of flip flop 2 i.e. input of $D_{2}$ , i.e.
$D_{2}=A \oplus S=Q_{1} \oplus S$
Now, X-OR is replaced by X-NOR, keeping state diagram to be unchanged it means the input to $D_{2}$ should not get changed.
When replaced by X-NOR gate
Now $D_{2}=A \odot S$
Also, we know that
$\overline{A \oplus B}= \overline{A} \oplus B=A \odot B$
We require output to be as $D_{2}=A \oplus S$
So, to keep this output, A should be connected to
$\bar{Q}_{1}$ as
$D_{2}=\overline{Q}_{1} \odot S=\overline{Q_{1} \odot S}=Q_{1} \oplus S$
 Question 9
The point P in the following figure is stuck at 1. The output f will be
 A $\overline{AB\bar{C}}$ B $\bar{A}$ C $AB\bar{C}$ D A
GATE EC 2006   Digital Circuits
Question 9 Explanation:

There are 9 questions to complete.