Question:
Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown. At the beginning, \(Q_1=0\), \(Q_2=1\), \(Q_3=1\). Which one of the given values of \((Q_1,Q_2,Q_3)\) can NEVER be obtained with this circuit?
Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown. At the beginning, \(Q_1=0\), \(Q_2=1\), \(Q_3=1\). Which one of the given values of \((Q_1,Q_2,Q_3)\) can NEVER be obtained with this circuit?
Show Hint
Translate the diagram into next–state equations first. Then either use algebraic constraints or a short state walk from the initial condition to spot unreachable tuples quickly.
Updated On: Feb 3, 2026
- \((0,0,1)\)
- \((1,0,0)\)
- \((1,0,1)\)
- \((1,1,1)\)
Show Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
Step 1: Write next–state equations
For a T–FF: \(Q^+ = Q \oplus T\). For a D–FF: \(Q^+ = D\).
From the figure (using the labels in the question): \[ \begin{aligned} T_1 &= \overline{Q_3}, & Q_1^+ &= Q_1 \oplus \overline{Q_3}, \\ D_2 &= Q_1, & Q_2^+ &= Q_1, \\ T_3 &= Q_2, & Q_3^+ &= Q_3 \oplus Q_2. \end{aligned} \]
Step 2: Iterate from the given initial state \((Q_1,Q_2,Q_3)=(0,1,1)\)
On each rising edge (all FFs clocked together) apply the above equations: \[ \begin{array}{c|c} \text{Clock} & (Q_1,Q_2,Q_3) \\ \hline 0 & (0,1,1)\ \text{(given)} \\ 1 & (0,0,0) \\ 2 & (1,0,0) \\ 3 & (0,1,0) \\ 4 & (1,0,1) \\ 5 & (1,1,1) \\ 6 & (1,1,0) \\ 7 & (0,1,1)\ \text{(cycle repeats)} \end{array} \]
Step 3: Read off the reachable set
The reachable states are \(\{(0,1,1), (0,0,0), (1,0,0), (0,1,0), (1,0,1), (1,1,1), (1,1,0)\}\). The tuple \((0,0,1)\) never appears and the sequence repeats thereafter, so it is unreachable. \[ \boxed{\text{State }(0,0,1)\ \text{can never be obtained.}} \]
For a T–FF: \(Q^+ = Q \oplus T\). For a D–FF: \(Q^+ = D\).
From the figure (using the labels in the question): \[ \begin{aligned} T_1 &= \overline{Q_3}, & Q_1^+ &= Q_1 \oplus \overline{Q_3}, \\ D_2 &= Q_1, & Q_2^+ &= Q_1, \\ T_3 &= Q_2, & Q_3^+ &= Q_3 \oplus Q_2. \end{aligned} \]
Step 2: Iterate from the given initial state \((Q_1,Q_2,Q_3)=(0,1,1)\)
On each rising edge (all FFs clocked together) apply the above equations: \[ \begin{array}{c|c} \text{Clock} & (Q_1,Q_2,Q_3) \\ \hline 0 & (0,1,1)\ \text{(given)} \\ 1 & (0,0,0) \\ 2 & (1,0,0) \\ 3 & (0,1,0) \\ 4 & (1,0,1) \\ 5 & (1,1,1) \\ 6 & (1,1,0) \\ 7 & (0,1,1)\ \text{(cycle repeats)} \end{array} \]
Step 3: Read off the reachable set
The reachable states are \(\{(0,1,1), (0,0,0), (1,0,0), (0,1,0), (1,0,1), (1,1,1), (1,1,0)\}\). The tuple \((0,0,1)\) never appears and the sequence repeats thereafter, so it is unreachable. \[ \boxed{\text{State }(0,0,1)\ \text{can never be obtained.}} \]
Was this answer helpful?
0
0
Top GATE CS Computer Science and IT Engineering Questions
- Suppose a program is running on a non-pipelined single processor computer system. The computer is connected to an external device that can interrupt the processor asynchronously. The processor needs to execute the interrupt service routine (ISR) to serve this interrupt. The following steps (not necessarily in order) are taken by the processor when the interrupt arrives:
(i) The processor saves the content of the program counter.
(ii) The program counter is loaded with the start address of the ISR.
(iii) The processor finishes the present instruction.
Which ONE of the following is the CORRECT sequence of steps? - Which ONE of the following statements is FALSE regarding the symbol table?
- Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
- Consider a demand paging memory management system with 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte addressable, what is the maximum number of entries in the page table?
A schedule of three database transactions \(T_1\), \(T_2\), and \(T_3\) is shown. \(R_i(A)\) and \(W_i(A)\) denote read and write of data item A by transaction \(T_i\), \(i = 1, 2, 3\). The transaction \(T_1\) aborts at the end. Which other transaction(s) will be required to be rolled back?
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions