chapter
    Flip-Flops, Counters and Finite State Machines Short Notes for GATE CS

    Flip-Flops, Counters and Finite State Machines short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved pract

    flip flops counters and finite state machines short notes

    Topic Summary: Sequential Circuit Analysis Checklist

    Final Checklist

    Before Starting:

    Identified all flip-flops and types (D, JK, T, SR)
    Noted clock edge polarity (positive or negative)
    Recorded initial state correctly

    Analysis Steps:

    Written excitation equations for all flip-flop inputs
    Substituted into characteristic equations
    Derived next-state equations

    Tracing:

    Built state table (if helpful)
    Started from correct initial state
    Computed each transition carefully
    Stopped when pattern detected or state repeated

    Verification:

    Checked first transition manually
    Verified no calculation errors in XOR, AND, OR
    Confirmed cycle closure (if applicable)

    Characteristic Equations (Memorize)

    If You See...

    PatternAction
    MUX with feedbackWrite MUX equation, treat as FF input
    All T flip-flopsLook for counter pattern
    Mixed FF typesApply correct equation per FF
    "Number of distinct states"Trace until repeat, count unique
    Negative-edge clockSame method, just note edge type

    You are ready for sequential circuit analysis problems.

    Topic Summary: Counter Analysis Checklist

    Final Checklist

    1. Identify the Architecture

    Ripple: Clock daisy-chained ( or to next CLK).
    Synchronous: All CLK pins tied to the same global clock.

    2. Ripple Counter Direction (Negative-Edge FFs)

    UP: Next CLK connected to previous .
    DOWN: Next CLK connected to previous .

    (Reverse these rules for Positive-Edge FFs).

    3. Frequency & Delay

    Standard -bit Ripple:
    Truncated Ripple: (where is the number of FFs that actually toggle during reset).
    Synchronous:

    4. Synchronous Analysis Method

    Write excitation equation for each FF input (e.g., ).
    Substitute into characteristic equation (e.g., ).
    Build state table starting from the given initial state.
    Trace until the sequence repeats or the required number of clocks is reached.

    Final Revision Checklist

    Final Revision Checklist

    Before you finalize your answer, run this checklist. If yes, your excitation equations are solid.

    ✓
    Flip-Flop Type Verified

    Confirmed whether the problem specifies D, T, JK, or SR.

    ✓
    Translation Accurate

    correctly mapped to excitation inputs using the standard table (especially checking placements).

    ✓
    K-Map Axes Correct

    Variables on the outside are Current State (), not Next State ().

    ✓
    Don't Cares Utilized

    Unused states in the sequence are marked as and aggressively grouped for simplification.

    ✓
    Equation Form

    Final expressions are in minimal Sum of Products (SOP) or recognized XOR forms, matching the expected answer format.

    2 more cards in this chapter

    Try a question

    Answer it here to see how it works. Nothing is recorded until you sign in.

    Question 1
    Level 1: Warm-up

    An SR flip-flop has two inputs and . One specific input combination is invalid (undefined output). What is the number of valid input combinations for the SR flip-flop?

    Question 2
    Level 1: Warm-up

    For a JK flip-flop, the next state is given by the characteristic equation . The maximum number of input pairs that guarantee for any initial state is

    Question 3
    Level 1: Warm-up

    Consider a 3-bit ripple counter with flip-flop propagation delay of 20 ns and a strobe delay of 20 ns. Which of the following statements regarding its maximum operating frequency is true?

    Question 4
    Level 1: Warm-up

    A sequential circuit has 2 D flip-flops and 2 external inputs. The complete state table lists every combination of current state and input values. How many rows does this state table contain?

    Question 5
    Level 1: Warm-up

    A sequential circuit must be capable of representing at least 4 distinct states. What is the minimum number of flip-flops required?

    Question 6
    Level 1: Warm-up

    A sequential circuit has 3 state variables and 2 external inputs. The output function of a Mealy machine depends on variables, while a Moore machine depends on variables. The difference in the number of variables the output function depends on between a Mealy and a Moore implementation of this circuit is

    Question 7
    Level 1: Warm-up

    Consider a sequential circuit with three flip-flops: and are T flip-flops, and is a D flip-flop. The connections are , , and . The circuit is initialized to . Which of the following statements about the state sequence is true?

    Question 8
    Level 1: Warm-up

    In an 8-bit synchronous counter, the propagation delay of each flip-flop is 15 ns and the maximum delay of the combinational logic is 25 ns. The maximum total propagation delay for any state transition is

    Question 9
    Level 1: Warm-up

    Consider the following assertion and reason regarding a sequential circuit:

    Assertion (A): In a ripple counter built with negative-edge-triggered flip-flops, connecting the clock input of each stage to the output of the previous stage results in a DOWN counter.

    Reason (R): When the current state bit transitions from 0 to 1, its output transitions from 1 to 0, providing the required negative clock edge to trigger the next stage.

    Question 10
    Level 1: Warm-up

    For a D flip-flop, the excitation input is required to be equal to the next state . If the current state is and the desired next state is , what is the value of the excitation input ?

    Free preview ends here

    Login to view the complete short notes

    Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

    Why MastersUp

    Personalised first. High quality throughout.

    Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

    Built around you, not around a syllabus PDF

    Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

    Revision that hits your weak spots

    We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

    Questions calibrated to the real exam

    Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

    Notes written for recall, not for volume

    Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

    One place for everything

    Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

    Honest progress

    No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

    Unlock the whole course

    Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

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

    Flip-Flops, Counters and Finite State Machines short notes for GATE CS: 5 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

    Topic Summary: Sequential Circuit Analysis Checklist

    Final Checklist

    Before Starting:

    Identified all flip-flops and types (D, JK, T, SR)
    Noted clock edge polarity (positive or negative)
    Recorded initial state correctly

    Analysis Steps:

    Written excitation equations for all flip-flop inputs
    Substituted into characteristic equations
    Derived next-state equations

    Tracing:

    Built state table (if helpful)
    Started from correct initial state
    Computed each transition carefully
    Stopped when pattern detected or state repeated

    Verification:

    Checked first transition manually
    Verified no calculation errors in XOR, AND, OR
    Confirmed cycle closure (if applicable)

    Characteristic Equations (Memorize)

    If You See...

    PatternAction
    MUX with feedbackWrite MUX equation, treat as FF input
    All T flip-flopsLook for counter pattern
    Mixed FF typesApply correct equation per FF
    "Number of distinct states"Trace until repeat, count unique
    Negative-edge clockSame method, just note edge type

    You are ready for sequential circuit analysis problems.

    Topic Summary: Counter Analysis Checklist

    Final Checklist

    1. Identify the Architecture

    Ripple: Clock daisy-chained ( or to next CLK).
    Synchronous: All CLK pins tied to the same global clock.

    2. Ripple Counter Direction (Negative-Edge FFs)

    UP: Next CLK connected to previous .
    DOWN: Next CLK connected to previous .

    (Reverse these rules for Positive-Edge FFs).

    3. Frequency & Delay

    Standard -bit Ripple:
    Truncated Ripple: (where is the number of FFs that actually toggle during reset).
    Synchronous:

    4. Synchronous Analysis Method

    Write excitation equation for each FF input (e.g., ).
    Substitute into characteristic equation (e.g., ).
    Build state table starting from the given initial state.
    Trace until the sequence repeats or the required number of clocks is reached.

    Final Revision Checklist

    Final Revision Checklist

    Before you finalize your answer, run this checklist. If yes, your excitation equations are solid.

    ✓
    Flip-Flop Type Verified

    Confirmed whether the problem specifies D, T, JK, or SR.

    ✓
    Translation Accurate

    correctly mapped to excitation inputs using the standard table (especially checking placements).

    ✓
    K-Map Axes Correct

    Variables on the outside are Current State (), not Next State ().

    ✓
    Don't Cares Utilized

    Unused states in the sequence are marked as and aggressively grouped for simplification.

    ✓
    Equation Form

    Final expressions are in minimal Sum of Products (SOP) or recognized XOR forms, matching the expected answer format.

    Final Revision Checklist

    Final Revision Checklist

    Before finalizing your design, run this checklist. If yes, your Mealy machine is correctly designed.

    ✓
    Output Placement

    Outputs are labeled on transitions (arrows), not inside states.

    ✓
    Dependency Check

    Output is a function of both and .

    ✓
    Overlap Handling

    Transitions that fail a sequence check for partial matches before resetting to .

    ✓
    State Minimality

    Verified that no two states are redundant (Mealy machines often have fewer states than Moore equivalents).

    ✓
    Timing Awareness

    Acknowledged that outputs may change asynchronously with input changes, potentially causing glitches if not synchronized.

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

    Question 1 · Digital Logic MCQ

    An SR flip-flop has two inputs and . One specific input combination is invalid (undefined output). What is the number of valid input combinations for the SR flip-flop?

    1. A.

      2

    2. B.

      3

    3. C.

      4

    4. D.

      5

    Correct Answer:

    B

    Step-by-Step Solution

    Key idea: This is a direct recall of the SR flip-flop characteristic table.

    Step 1: An SR flip-flop has two binary inputs, and . The total number of input combinations is : namely .

    Step 2: From the characteristic table:

    • : Hold (valid)
    • : Reset (valid)
    • : Set (valid)
    • : Undefined / Invalid

    Step 3: Excluding the one invalid combination , the number of valid combinations is .

    Answer: B

    Question 2 · Digital Logic MCQ

    For a JK flip-flop, the next state is given by the characteristic equation . The maximum number of input pairs that guarantee for any initial state is

    1. A.

      0

    2. B.

      1

    3. C.

      2

    4. D.

      4

    Correct Answer:

    B

    Step-by-Step Solution

    Insight: This is an observation question about the JK flip-flop characteristic equation and the specific condition for toggling.

    Exam route: Set in the equation and solve for and that hold for both and .

    Learning route:

    Step 1: The characteristic equation is .

    Step 2: We require for any initial state .

    Step 3: If , then . The equation becomes .

    Step 4: If , then . The equation becomes .

    Step 5: The only input pair that satisfies both conditions simultaneously is .

    Step 6: Thus, there is exactly 1 such input pair.

    Answer: 1

    Question 3 · Digital Logic MCQ

    Consider a 3-bit ripple counter with flip-flop propagation delay of 20 ns and a strobe delay of 20 ns. Which of the following statements regarding its maximum operating frequency is true?

    1. A.

      The maximum frequency is 16.67 MHz because the strobe delay does not affect the critical path.

    2. B.

      The maximum frequency is 12.5 MHz because the total critical path delay is 80 ns.

    3. C.

      The maximum frequency is 10.0 MHz because the total critical path delay is 100 ns.

    4. D.

      The maximum frequency is 25.0 MHz because only one flip-flop delay matters.

    Correct Answer:

    B

    Step-by-Step Solution

    Insight: This is a bounding question testing the complete maximum frequency formula for a ripple counter, including the strobe delay.

    Exam route: Calculate total delay as , then take the reciprocal to find .

    Learning route:

    Step 1: Identify the parameters: , , .

    Step 2: Calculate the minimum clock period required for stable operation:

    Step 3: Calculate the maximum operating frequency:

    Answer: The maximum frequency is 12.5 MHz because the total critical path delay is 80 ns.

    Question 4 · Digital Logic MCQ

    A sequential circuit has 2 D flip-flops and 2 external inputs. The complete state table lists every combination of current state and input values. How many rows does this state table contain?

    1. A.

      4

    2. B.

      8

    3. C.

      16

    4. D.

      32

    Correct Answer:

    C

    Step-by-Step Solution

    Key idea: This is a direct application of the state table sizing rule from the sequential circuit fundamentals.

    Step 1: Determine the number of distinct current states. With flip-flops, the number of states is .

    Step 2: Determine the number of input combinations. With external inputs, the number of input combinations is .

    Step 3: The state table must cover every (current state, input) pair. The total number of rows is the product:

    Answer: C

    Question 5 · Digital Logic MCQ

    A sequential circuit must be capable of representing at least 4 distinct states. What is the minimum number of flip-flops required?

    1. A.

      2

    2. B.

      3

    3. C.

      4

    4. D.

      8

    Correct Answer:

    A

    Step-by-Step Solution

    Key idea: This is a direct application of the relationship between flip-flop count and state capacity.

    Step 1: With flip-flops, a sequential circuit can represent up to distinct states.

    Step 2: We need at least 4 states. Find the smallest such that .

    Step 3: Check values:

    • : (not enough)
    • : (sufficient)

    The minimum number of flip-flops is 2.

    Answer: A

    Question 6 · Digital Logic MCQ

    A sequential circuit has 3 state variables and 2 external inputs. The output function of a Mealy machine depends on variables, while a Moore machine depends on variables. The difference in the number of variables the output function depends on between a Mealy and a Moore implementation of this circuit is

    1. A.

      -2

    2. B.

      0

    3. C.

      2

    4. D.

      5

    Correct Answer:

    C

    Step-by-Step Solution

    Insight: This is a casework question comparing the variable dependency of Mealy and Moore machine output functions.

    Exam route: For Mealy, dependency is . For Moore, dependency is . Substitute and find the difference.

    Learning route:

    Step 1: Identify the number of state variables and external inputs .

    Step 2: For a Mealy machine, the output function depends on current state and inputs: variables.

    Step 3: For a Moore machine, the output function depends only on the current state: variables.

    Step 4: Calculate the difference: .

    Answer: 2

    Question 7 · Digital Logic MCQ

    Consider a sequential circuit with three flip-flops: and are T flip-flops, and is a D flip-flop. The connections are , , and . The circuit is initialized to . Which of the following statements about the state sequence is true?

    1. A.

      The circuit visits exactly 4 distinct states before repeating.

    2. B.

      The state 000 is an absorbing state, and the circuit never returns to 011.

    3. C.

      The circuit oscillates indefinitely between 011 and 111.

    4. D.

      The state 111 transitions directly back to 011 in one clock cycle.

    Correct Answer:

    B

    Step-by-Step Solution

    Insight: This is a state-tracing question. We must compute the next state for each flip-flop simultaneously using the given excitation equations.

    Exam route: Start at 011. Compute . Apply for T-FF and for D-FF. Repeat until a pattern or absorbing state is found.

    Learning route:

    Step 1: Initial state is .

    Step 2: Clock 1:

    . .

    . .

    . .

    New state: 111.

    Step 3: Clock 2 (from 111):

    . .

    . .

    . .

    New state: 000.

    Step 4: Clock 3 (from 000):

    . .

    . .

    . .

    New state: 000.

    The state 000 is absorbing. The distinct states visited are 011, 111, and 000. The circuit never returns to 011.

    Answer: The state 000 is an absorbing state, and the circuit never returns to 011.

    Question 8 · Digital Logic MCQ

    In an 8-bit synchronous counter, the propagation delay of each flip-flop is 15 ns and the maximum delay of the combinational logic is 25 ns. The maximum total propagation delay for any state transition is

    1. A.

      40 ns

    2. B.

      120 ns

    3. C.

      145 ns

    4. D.

      200 ns

    Correct Answer:

    A

    Step-by-Step Solution

    Insight: This is an observation question testing the fundamental speed advantage of synchronous counters.

    Exam route: Recall that in a synchronous counter, total delay is independent of the number of bits. It is simply .

    Learning route:

    Step 1: Identify the counter type: synchronous.

    Step 2: Recall the delay formula for synchronous counters: all flip-flops trigger simultaneously, so the delay does not accumulate across stages.

    Step 3: The total delay is bounded by the delay of one flip-flop plus the delay of the combinational logic determining the next state.

    Step 4: Calculate: .

    Answer: 40 ns

    Question 9 · Digital Logic MCQ

    Consider the following assertion and reason regarding a sequential circuit:

    Assertion (A): In a ripple counter built with negative-edge-triggered flip-flops, connecting the clock input of each stage to the output of the previous stage results in a DOWN counter.

    Reason (R): When the current state bit transitions from 0 to 1, its output transitions from 1 to 0, providing the required negative clock edge to trigger the next stage.

    1. A.

      Both A and R are true, and R is the correct explanation of A.

    2. B.

      Both A and R are true, but R is not the correct explanation of A.

    3. C.

      A is true but R is false.

    4. D.

      A is false but R is true.

    Correct Answer:

    A

    Step-by-Step Solution

    Insight: This is a construction question testing the precise wiring rules for ripple counter direction based on clock trigger edges.

    Exam route: Verify the down-count sequence behavior. In a down counter, the next bit toggles when the current bit goes . Check if provides a negative edge during this transition.

    Learning route:

    Step 1: Analyze the down-count sequence. For a bit to decrement the overall count, the next higher bit must toggle when the current bit transitions from 0 to 1.

    Step 2: Evaluate the signal at during this transition of . When goes from 0 to 1, goes from 1 to 0.

    Step 3: A transition is a negative edge.

    Step 4: Since the flip-flops are negative-edge-triggered, connecting the next stage's clock to will correctly trigger the next stage exactly when needed for a down-count.

    Step 5: Both A and R are true, and R perfectly explains the mechanism described in A.

    Answer: Both A and R are true, and R is the correct explanation of A.

    Question 10 · Digital Logic MCQ

    For a D flip-flop, the excitation input is required to be equal to the next state . If the current state is and the desired next state is , what is the value of the excitation input ?

    1. A.

      0

    2. B.

      1

    3. C.

      X (Don't Care)

    4. D.

      Undefined

    Correct Answer:

    A

    Step-by-Step Solution

    Key idea: The D flip-flop simply passes the input to the output on the clock edge. Thus, must exactly equal the desired next state .

    Step 1: Identify the desired next state, which is given as .

    Step 2: Apply the rule for a D flip-flop: .

    Step 3: Substitute the value: .

    Conclusion: The value of the excitation input is 0.

    More short notes in this unit