Flip-Flops, Counters and Finite State Machines PYQs for GATE CS

Solve 8+ Flip-Flops, Counters and Finite State Machines previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Digital Logic - Flip-Flops, Counters & FSMs

Chapter Journey

What you will master:

Trace sequential circuits through clock cycles
Design modulo-N counters using flip-flops
Derive excitation equations for D, T, JK flip-flops
Model sequence detectors as Mealy or Moore machines
Minimize states in finite state machines

Hero Card: What Makes a Circuit Sequential?

Combinational vs Sequential

Feature	Combinational	Sequential
Output depends on	Current inputs only	Current inputs + Past state
Memory	No	Yes (flip-flops)
Clock required	No	Yes (usually)
Example	Adder, Multiplexer	Counter, Register, FSM

The Core Idea

A sequential circuit has two parts:

Combinational logic (gates) that computes next state and outputs
Memory elements (flip-flops) that store the current state

Next State = f (Current State, Inputs)

Output = g (Current State, Inputs) (Mealy)

Output = g (Current State) (Moore)

The clock synchronizes when the state updates. On each active clock edge (rising or falling), flip-flops capture their input and update their output. Between clock edges, the state remains constant.

Why This Matters

Every sequential circuit problem asks you to do one thing: trace the state. Given initial values of flip-flops, determine what happens after 1 clock, 2 clocks, or N clocks. You will:

Read the circuit diagram
Write excitation equations (what goes into each flip-flop)
Build a state table
Follow the transitions

Flip-Flops, Counters and Finite State Machines: Solved Questions with Step-by-Step Explanations (8 Problems)

Question 1 · Digital Logic · 2026_Set1 MCQ

Consider a 2-bit saturating up/down counter that performs the saturating up count when the input

P

is 0, and the saturating down count when

P

is 1. The Next State table of the counter is as shown. The counter is built as a synchronous sequential circuit using D flip-flops.

Input	Current State		Next State
$P$	$Q_{1}$	$Q_{0}$	$Q_{1}^{+}$	$Q_{0}^{+}$
0	0	0	0	1
0	0	1	1	0
0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	0
1	1	0	0	1
1	1	1	1	0

Which one of the following options corresponds to the expressions for the inputs of the D flip-flops,

D_{1}

and

D_{0}

A.
$D_{1} = P Q_{1} + \overline{P} Q_{0} + Q_{1} Q_{0} D_{0} = P Q_{0} + \overline{P} Q_{1} + Q_{1} \overline{Q_{0}}$
B.
$D_{1} = \overline{P} Q_{1} + \overline{P} Q_{0} + Q_{1} Q_{0} D_{0} = \overline{P} \overline{Q_{0}} + \overline{P} Q_{1} + Q_{1} \overline{Q_{0}}$
C.
$D_{1} = \overline{P} \overline{Q_{1}} + \overline{P} Q_{0} + Q_{1} Q_{0} D_{0} = \overline{P} Q_{0} + \overline{P} Q_{1} + Q_{1} \overline{Q_{0}}$
D.
$D_{1} = P \overline{Q_{1}} + \overline{P} Q_{0} + Q_{1} Q_{0} D_{0} = P \overline{Q_{0}} + \overline{P} Q_{1} + Q_{1} \overline{Q_{0}}$

Correct Answer:

Step-by-Step Solution

Insight: For D flip-flops, the excitation input is exactly the next state ( $D = Q^{+}$ ). We just need to map the given Next State table to K-maps for $D_{1}$ and $D_{0}$ and minimize them.

Exam route: Build K-maps for $D_{1}$ and $D_{0}$ with variables $P, Q_{1}, Q_{0}$ . Fill in the 1s from the $Q_{1}^{+}$ and $Q_{0}^{+}$ columns. Group the 1s to get the SOP expressions. Match with the options.

Learning route:

Step 1: Understand the D flip-flop excitation. $D_{1} = Q_{1}^{+}$ and $D_{0} = Q_{0}^{+}$ .

Step 2: Construct the K-map for $D_{1}$ .

The minterms where $Q_{1}^{+} = 1$ are:

$P = 0, Q_{1} = 0, Q_{0} = 1$ (m1)

$P = 0, Q_{1} = 1, Q_{0} = 0$ (m2)

$P = 0, Q_{1} = 1, Q_{0} = 1$ (m3)

$P = 1, Q_{1} = 1, Q_{0} = 1$ (m7)

Grouping these on a 3-variable K-map:

m3 and m7 form a pair $\to Q_{1} Q_{0}$
m1 and m3 form a pair $\to \overline{P} Q_{0}$
m2 and m3 form a pair $\to \overline{P} Q_{1}$

Thus, $D_{1} = Q_{1} Q_{0} + \overline{P} Q_{0} + \overline{P} Q_{1}$ .

Step 3: Construct the K-map for $D_{0}$ .

The minterms where $Q_{0}^{+} = 1$ are:

$P = 0, Q_{1} = 0, Q_{0} = 0$ (m0)

$P = 0, Q_{1} = 1, Q_{0} = 0$ (m2)

$P = 0, Q_{1} = 1, Q_{0} = 1$ (m3)

$P = 1, Q_{1} = 1, Q_{0} = 0$ (m6)

Grouping these:

m2 and m6 form a pair $\to Q_{1} \overline{Q_{0}}$
m0 and m2 form a pair $\to \overline{P} \overline{Q_{0}}$
m2 and m3 form a pair $\to \overline{P} Q_{1}$

Thus, $D_{0} = Q_{1} \overline{Q_{0}} + \overline{P} \overline{Q_{0}} + \overline{P} Q_{1}$ .

Step 4: Match with options. Option B matches both derived expressions perfectly.

Verification: Plug in $P = 0, Q_{1} = 1, Q_{0} = 0$ into Option B. $D_{1} = (1) (0) + (1) (0) + (1) (1) = 1$ . $D_{0} = (1) (1) + (1) (1) + (1) (1) = 1$ . This matches the table's Next State of 11.

Question 2 · Digital Logic · 2025_Set2 NAT

In a 4-bit ripple counter, if the period of the waveform at the last flip-flop is 64 microseconds, then the frequency of the ripple counter in kHz is ________. (Answer in integer)

Correct Answer:

250.00

Step-by-Step Solution

Insight: A 4-bit ripple counter divides the input clock frequency by $2^{4} = 16$ . The period at the last flip-flop is 16 times the input clock period.

Exam route: Find the frequency of the last flip-flop from its period. Multiply by 16 to get the input clock frequency. Convert to kHz.

Learning route:

Step 1: The period of the waveform at the last flip-flop (4th stage) is given as $T_{l a s t} = 64 \mu s$ .

Step 2: The frequency at the last flip-flop is $f_{l a s t} = \frac{1}{T _{l a s t}} = \frac{1}{64 \times 1 0 ^{- 6}} Hz = 15625 Hz = 15.625 kHz$ .

Step 3: In an $n$ -bit ripple counter, each stage acts as a divide-by-2 circuit. Therefore, the input clock frequency is $2^{n}$ times the frequency at the $n$ -th stage.

Step 4: For a 4-bit counter, $f_{in} = 2^{4} \times f_{l a s t} = 16 \times 15.625 kHz = 250 kHz$ .

Verification: If $f_{in} = 250 kHz$ , the period is $4 \mu s$ . After 4 stages, the period is $4 \times 16 = 64 \mu s$ , which matches the given data.

Question 3 · Digital Logic · 2025_Set1 NAT

Consider a finite state machine (FSM) with one input

X

and one output

f

, represented by the given state transition table. The minimum number of states required to realize this FSM is ________. (Answer in integer)

Correct Answer:

5.00

Step-by-Step Solution

Insight: To find the minimum number of states, we look for equivalent states using row matching and partition refinement. States with identical next-states and outputs can be merged.

Exam route: Scan the table for identical rows. Merge them. Repeat until no more identical rows exist. Count the remaining unique states.

Learning route:

Step 1: Compare rows for exact matches in Next State and Output columns.

Row B: Next states (D, C), Outputs (0, 0).
Row E: Next states (D, C), Outputs (0, 0).

Rows B and E are identical. Merge E into B.

Row D: Next states (G, A), Outputs (1, 0).
Row H: Next states (G, A), Outputs (1, 0).

Rows D and H are identical. Merge H into D.

Step 2: Update the table with the merged states (replace E with B, and H with D).

Row A: F, B | 0, 0
Row B: D, C | 0, 0
Row C: F, E $\to$ F, B | 0, 0
Row D: G, A | 1, 0
Row F: F, B | 1, 1
Row G: G, H $\to$ G, D | 0, 1

Step 3: Scan the updated table for new identical rows.

Row A: F, B | 0, 0
Row C: F, B | 0, 0

Rows A and C are now identical. Merge C into A.

Step 4: Update the table again (replace C with A).

The remaining unique states are A, B, D, F, G.

Let's verify no more merges are possible:

A: F, B | 0, 0
B: D, A | 0, 0 (since C became A)
D: G, A | 1, 0
F: F, B | 1, 1
G: G, D | 0, 1

All 5 remaining states have distinct output signatures or distinct next-state transitions.

Step 5: The minimum number of states required is 5.

Question 4 · Digital Logic · 2025_Set1 NAT

Consider the given sequential circuit designed using D-Flip-flops. The circuit is initialized with some value (initial state). The number of distinct states the circuit will go through before returning back to the initial state is _________ . (Answer in integer)

Correct Answer:

7.00

Step-by-Step Solution

Insight: The circuit is a 4-bit Johnson counter (twisted ring counter), identifiable by the shift-register structure with inverted feedback from the last stage to the first. Exam route: A Johnson counter with

n

flip-flops has a modulus of

2 n

. Here

n = 4

, so the cycle length is 8. Starting from

0000

, the sequence of 8 distinct states is

0000 \to 1000 \to 1100 \to 1110 \to 1111 \to 0111 \to 0011 \to 0001 \to 0000

. The number of distinct states visited *before* returning to the initial state is 7 (or 8 if including the initial state, both were accepted in GATE 2025). Learning route: Step 1: Identify the circuit topology. The diagram shows four D flip-flops connected in a chain, where the output of each feeds the input of the next (

Q_{0} \to D_{1}

Q_{1} \to D_{2}

Q_{2} \to D_{3}

). Step 2: Observe the feedback path. The inverted output of the last flip-flop (

\overline{Q_{3}}

) is connected to the input of the first flip-flop (

D_{0}

). Step 3: Recognize this specific configuration as a Johnson Counter (or Twisted Ring Counter). Step 4: Recall the property of a Johnson counter: an

n

-bit Johnson counter cycles through exactly

2 n

distinct states. Step 5: Calculate the cycle length for

n = 4

2 \times 4 = 8

distinct states. Step 6: Trace the states manually to verify (assuming initial state

0000

): - Clock 1:

D_{0} = \overline{0} = 1 \to 1000

- Clock 2:

D_{0} = \overline{0} = 1 \to 1100

- Clock 3:

D_{0} = \overline{0} = 1 \to 1110

- Clock 4:

D_{0} = \overline{0} = 1 \to 1111

- Clock 5:

D_{0} = \overline{1} = 0 \to 0111

- Clock 6:

D_{0} = \overline{1} = 0 \to 0011

- Clock 7:

D_{0} = \overline{1} = 0 \to 0001

- Clock 8:

D_{0} = \overline{1} = 0 \to 0000

(Returns to initial state) Step 7: Interpret the question phrasing. "Before returning back to the initial state" typically means counting the intermediate states, which is 7. (Note: GATE 2025 official key accepted both 7 and 8). Verification: The trace confirms exactly 8 unique states in the cycle. Excluding the final return to the initial state, 7 distinct states are visited.

Question 5 · Digital Logic · 2023 MCQ

Consider a sequential digital circuit consisting of T flip-flops and D flip-flops as shown in the figure. CLKIN is the clock input to the circuit. At the beginning, Q1, Q2 and Q3 have values 0, 1 and 1, respectively.

Which one of the given values of (Q1, Q2, Q3) can NEVER be obtained with this digital circuit?

A.
(0, 0, 1)
B.
(1, 0, 0)
C.
(1, 0, 1)
D.
(1, 1, 1)

Correct Answer:

Step-by-Step Solution

Insight: This is a sequential circuit analysis problem requiring us to derive next-state equations for mixed flip-flop types and trace the state transition graph to find unreachable states.

Exam route: From the diagram, $T_{1} = \overline{Q_{3}}$ , $D_{2} = Q_{1}$ , $T_{3} = Q_{2}$ . Using $Q^{+} = T \oplus Q$ for T-FF and $Q^{+} = D$ for D-FF, we get $Q_{1}^{+} = \overline{Q_{3}} \oplus Q_{1}$ , $Q_{2}^{+} = Q_{1}$ , $Q_{3}^{+} = Q_{2} \oplus Q_{3}$ . Starting from $011$ , the sequence is $011 \to 000 \to 100 \to 010 \to 101 \to 111 \to 110 \to 011$ . The state $(0, 0, 1)$ is never visited.

Learning route:

Step 1: Identify the flip-flop types and their characteristic equations.

$Q_{1}$ is a T-FF: $Q_{1}^{+} = T_{1} \oplus Q_{1}$
$Q_{2}$ is a D-FF: $Q_{2}^{+} = D_{2}$
$Q_{3}$ is a T-FF: $Q_{3}^{+} = T_{3} \oplus Q_{3}$

Step 2: Extract excitation equations from the circuit diagram.

$T_{1} = \overline{Q_{3}}$
$D_{2} = Q_{1}$
$T_{3} = Q_{2}$

Step 3: Formulate the next-state equations.

$Q_{1}^{+} = \overline{Q_{3}} \oplus Q_{1}$
$Q_{2}^{+} = Q_{1}$
$Q_{3}^{+} = Q_{2} \oplus Q_{3}$

Step 4: Trace the state sequence starting from the initial state $Q_{1} Q_{2} Q_{3} = 011$ .

Current: $011$ . $Q_{1}^{+} = \overline{1} \oplus 0 = 0$ , $Q_{2}^{+} = 0$ , $Q_{3}^{+} = 1 \oplus 1 = 0$ . Next: $000$ .
Current: $000$ . $Q_{1}^{+} = \overline{0} \oplus 0 = 1$ , $Q_{2}^{+} = 0$ , $Q_{3}^{+} = 0 \oplus 0 = 0$ . Next: $100$ .
Current: $100$ . $Q_{1}^{+} = \overline{0} \oplus 1 = 0$ , $Q_{2}^{+} = 1$ , $Q_{3}^{+} = 0 \oplus 0 = 0$ . Next: $010$ .
Current: $010$ . $Q_{1}^{+} = \overline{0} \oplus 0 = 1$ , $Q_{2}^{+} = 0$ , $Q_{3}^{+} = 1 \oplus 0 = 1$ . Next: $101$ .
Current: $101$ . $Q_{1}^{+} = \overline{1} \oplus 1 = 1$ , $Q_{2}^{+} = 1$ , $Q_{3}^{+} = 0 \oplus 1 = 1$ . Next: $111$ .
Current: $111$ . $Q_{1}^{+} = \overline{1} \oplus 1 = 1$ , $Q_{2}^{+} = 1$ , $Q_{3}^{+} = 1 \oplus 1 = 0$ . Next: $110$ .
Current: $110$ . $Q_{1}^{+} = \overline{0} \oplus 1 = 0$ , $Q_{2}^{+} = 1$ , $Q_{3}^{+} = 1 \oplus 0 = 1$ . Next: $011$ (Initial state reached).

Step 5: List all visited states: $011, 000, 100, 010, 101, 111, 110$ .

Step 6: Compare with the options. The state $(0, 0, 1)$ is not in the list, meaning it can never be obtained.

Verification: The cycle length is 7, and it perfectly loops back to $011$ . State $001$ is outside this cycle.

Question 6 · Digital Logic · 2023 MCQ

The output of a 2-input multiplexer is connected back to one of its inputs as shown in the figure.

Match the functional equivalence of this circuit to one of the following options.

A.
D Flip-flop
B.
D Latch
C.
Half-adder
D.
Demultiplexer

Correct Answer:

Step-by-Step Solution

Insight: A 2x1 multiplexer with its output fed back to the '0' input and a select line 'S' acts as a level-sensitive memory element, specifically a D Latch.

Exam route: The MUX equation is $Y = \overline{S} \cdot I_{0} + S \cdot I_{1}$ . Substitute $I_{0} = Y_{o l d}$ (feedback) and $I_{1} = D$ (new data). This yields $Y_{n e w} = \overline{S} \cdot Y_{o l d} + S \cdot D$ , which is the exact characteristic equation of a D Latch where S acts as the Enable signal.

Learning route:

Step 1: Write the standard Boolean equation for a 2x1 multiplexer: $Y = \overline{S} \cdot I_{0} + S \cdot I_{1}$ .

Step 2: Identify the connections from the diagram. The output $Y$ is connected to input $I_{0}$ . Let the other input (at '1') be the data input $D$ .

Step 3: Substitute $I_{0} = Y_{o l d}$ into the MUX equation: $Y_{n e w} = \overline{S} \cdot Y_{o l d} + S \cdot D$ .

Step 4: Analyze the behavior based on the select line $S$ :

If $S = 0$ : $Y_{n e w} = 1 \cdot Y_{o l d} + 0 \cdot D = Y_{o l d}$ . The circuit holds its previous state (Memory/Transparent-low state).
If $S = 1$ : $Y_{n e w} = 0 \cdot Y_{o l d} + 1 \cdot D = D$ . The output follows the input data (Transparent-high state).

Step 5: Match this behavior to standard sequential elements. This "hold when 0, follow when 1" behavior is the defining characteristic of a positive-level-sensitive D Latch.

Verification: A D Flip-flop requires edge-triggering (typically built with two latches and an inverter), which is not present here. A half-adder and demultiplexer are combinational or different sequential structures entirely.

Question 7 · Digital Logic · 2021_Set2 MCQ

Suppose we want to design a synchronous circuit that processes a string of 0’s and 1’s. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1’s by a 0. Consider the following example.

Input sequence: 00100011000011100
Output sequence: 00000001000001100

A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.
The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables

s

t

b

and

y

respectively.
Assume the initial state of the Mealy machine is 0.

What are the Boolean expressions corresponding to

t

and

y

in terms of

s

and

b

A. $t = s + b$
$y = s b$
B. $t = b$
$y = s b$
C. $t = b$
$y = s \overline{b}$
D. $t = s + b$
$y = \overline{s b}$

Correct Answer:

Step-by-Step Solution

Insight: The problem describes a sequence processor that replaces the first '1' in a block of consecutive '1's with '0', while leaving subsequent '1's unchanged. This requires tracking whether we are currently inside a block of '1's.

Exam route: Define state s=0 as "not in a block of 1s" and s=1 as "inside a block of 1s". Trace transitions: from s=0, input b=1 gives output y=0 (replaced) and next state t=1. From s=1, input b=1 gives output y=1 (unchanged) and next state t=1. This matches t=b and y=s AND b.

Learning route:

Step 1: Understand the Mealy machine requirement. Output y depends on current state s and input b.

Step 2: Analyze state s=0. If b=0, we stay in s=0, output y=0. If b=1, this is the first '1', so output y=0, and we move to s=1. Thus, when s=0, t=b and y=0.

Step 3: Analyze state s=1. If b=0, the block of '1's ends, so we move to s=0, output y=0. If b=1, it's a subsequent '1', so output y=1, and we stay in s=1. Thus, when s=1, t=b and y=b.

Step 4: Combine the conditions. For t, in both s=0 and s=1, t=b. For y, y is 1 only when s=1 and b=1, which is the logical AND: y = s AND b.

Step 5: Verify with the example. Input 0010001100... -> Output 0000000100... matches perfectly.

Verification: Plugging s=0, b=1 into t=b, y=sb gives t=1, y=0. Plugging s=1, b=1 gives t=1, y=1. This perfectly matches the required behavior.

Question 8 · Digital Logic · 2021_Set1 MCQ

Consider a 3-bit counter, designed using T flip-flops, as shown below:

Assuming the initial state of the counter given by PQR as 000, what are the next three states?

A.
011, 101, 000
B.
001, 010, 111
C.
011, 101, 111
D.
001, 010, 000

Correct Answer:

Step-by-Step Solution

Insight: This is a synchronous counter where the T inputs are driven by combinational logic of the current state, requiring step-by-step state tracing using the T flip-flop characteristic equation.

Exam route: Extract excitation equations: $T_{P} = R$ , $T_{Q} = \overline{P}$ , $T_{R} = \overline{Q}$ . Use $Q^{+} = T \oplus Q$ . Starting from $P QR = 000$ , compute next states: $000 \to 011 \to 101 \to 000$ .

Learning route:

Step 1: Identify the flip-flop type and its characteristic equation. For T flip-flops, $Q_{n e x t} = T \oplus Q$ .

Step 2: Read the circuit diagram to find the excitation equations for each flip-flop input.

$T_{P}$ is connected to $R$ , so $T_{P} = R$ .
$T_{Q}$ is connected to $\overline{P}$ , so $T_{Q} = \overline{P}$ .
$T_{R}$ is connected to $\overline{Q}$ , so $T_{R} = \overline{Q}$ .

Step 3: Substitute the current state $P QR = 000$ into the excitation equations.

$T_{P} = 0$ , $T_{Q} = \overline{0} = 1$ , $T_{R} = \overline{0} = 1$ .

Step 4: Calculate the next state using $Q_{n e x t} = T \oplus Q$ .

$P^{+} = 0 \oplus 0 = 0$
$Q^{+} = 1 \oplus 0 = 1$
$R^{+} = 1 \oplus 0 = 1$

Next state is $011$ .

Step 5: Repeat for the next state $011$ .

$T_{P} = 1$ , $T_{Q} = \overline{0} = 1$ , $T_{R} = \overline{1} = 0$ .
$P^{+} = 1 \oplus 0 = 1$ , $Q^{+} = 1 \oplus 1 = 0$ , $R^{+} = 0 \oplus 1 = 1$ .

Next state is $101$ .

Step 6: Repeat for $101$ .

$T_{P} = 1$ , $T_{Q} = \overline{1} = 0$ , $T_{R} = \overline{0} = 1$ .
$P^{+} = 1 \oplus 1 = 0$ , $Q^{+} = 0 \oplus 0 = 0$ , $R^{+} = 1 \oplus 1 = 0$ .

Next state is $000$ .

Verification: The sequence $000 \to 011 \to 101 \to 000$ perfectly matches the first option.

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Flip-Flops, Counters and Finite State Machines PYQs for GATE CS

Chapter Roadmap: Digital Logic - Flip-Flops, Counters & FSMs

Chapter Journey

What you will master:

Hero Card: What Makes a Circuit Sequential?

Combinational vs Sequential

The Core Idea

Why This Matters

Flip-Flops, Counters and Finite State Machines: Solved Questions with Step-by-Step Explanations (8 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit