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

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

    flip flops counters and finite state machines notes

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

    Chapter Journey

    1. Flip-Flop Behaviour & Sequential Circuit Analysis Exam instances: 3 | Importance: Medium | Foundation topic 2. Ripple and Synchronous Counters Exam instances: 2 | Importance: Medium-High 3. Counter State Transitions & Excitation Equations Exam instances: 1 | Importance: Medium 4. Mealy Machines and Sequence Processing Exam instances: 1 | Importance: Medium 5. FSM State Minimization Exam instances: 1 | Importance: Medium-Low Total Exam Instances: 8

    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 onCurrent inputs onlyCurrent inputs + Past state
    MemoryNoYes (flip-flops)
    Clock requiredNoYes (usually)
    ExampleAdder, MultiplexerCounter, Register, FSM

    The Core Idea

    A sequential circuit has two parts:

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

    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-Flop Types and Their Characteristic Equations

    Four Essential Flip-Flops

    1. SR Flip-Flop

    SRQ(next)Action
    00QHold
    010Reset
    101Set
    11UndefinedInvalid
    Characteristic Equation: (with constraint )

    2. D Flip-Flop (Data/Delay)

    DQ(next)
    00
    11
    Characteristic Equation:
    The simplest and most commonly used in modern designs.

    3. JK Flip-Flop

    JKQ(next)Action
    00QHold
    010Reset
    101Set
    11Toggle
    Characteristic Equation:
    No invalid state; JK = 11 causes toggle.

    4. T Flip-Flop (Toggle)

    TQ(next)
    0Q
    1
    Characteristic Equation:

    Key Insight

    The characteristic equation is your primary tool. It tells you what the flip-flop will become after the clock edge, given its current state and inputs. In standard problems, you will:

    1. Identify the flip-flop type from the symbol
    2. Write down its characteristic equation
    3. Substitute the actual circuit connections for the inputs
    4. Compute Q(next) for each clock cycle

    37 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 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 Notes for GATE CS

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

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

    Chapter Journey

    1. Flip-Flop Behaviour & Sequential Circuit Analysis Exam instances: 3 | Importance: Medium | Foundation topic 2. Ripple and Synchronous Counters Exam instances: 2 | Importance: Medium-High 3. Counter State Transitions & Excitation Equations Exam instances: 1 | Importance: Medium 4. Mealy Machines and Sequence Processing Exam instances: 1 | Importance: Medium 5. FSM State Minimization Exam instances: 1 | Importance: Medium-Low Total Exam Instances: 8

    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 onCurrent inputs onlyCurrent inputs + Past state
    MemoryNoYes (flip-flops)
    Clock requiredNoYes (usually)
    ExampleAdder, MultiplexerCounter, Register, FSM

    The Core Idea

    A sequential circuit has two parts:

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

    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-Flop Types and Their Characteristic Equations

    Four Essential Flip-Flops

    1. SR Flip-Flop

    SRQ(next)Action
    00QHold
    010Reset
    101Set
    11UndefinedInvalid
    Characteristic Equation: (with constraint )

    2. D Flip-Flop (Data/Delay)

    DQ(next)
    00
    11
    Characteristic Equation:
    The simplest and most commonly used in modern designs.

    3. JK Flip-Flop

    JKQ(next)Action
    00QHold
    010Reset
    101Set
    11Toggle
    Characteristic Equation:
    No invalid state; JK = 11 causes toggle.

    4. T Flip-Flop (Toggle)

    TQ(next)
    0Q
    1
    Characteristic Equation:

    Key Insight

    The characteristic equation is your primary tool. It tells you what the flip-flop will become after the clock edge, given its current state and inputs. In standard problems, you will:

    1. Identify the flip-flop type from the symbol
    2. Write down its characteristic equation
    3. Substitute the actual circuit connections for the inputs
    4. Compute Q(next) for each clock cycle

    Step-by-Step: Analyzing a Sequential Circuit

    The 5-Step Method

    Step 1: Label State Variables
    Identify all flip-flops in the circuit. Label outputs as . Note the flip-flop type (D, JK, T, SR).
    Step 2: Write Excitation Equations
    For each flip-flop input, write the Boolean expression from the circuit. Example: , , .
    Step 3: Derive Next-State Equations
    Substitute excitation equations into characteristic equations. For D FF: . For JK FF: . For T FF: .
    Step 4: Build State Table
    List all current states (for n flip-flops). Compute next state for each row. Include inputs if present.
    Current StateInput(s)Next StateOutput(s)
    0000......
    0001......
    0010......
    Step 5: Trace the Sequence
    Start from given initial state. Apply clock cycles one at a time. Record the sequence: . Stop when you return to initial state or find the pattern.
    Pro Tip: Draw a small table while tracing:
    ClockQ1Q2Q3Notes
    0 (init)011Given
    1???Compute
    2???Compute

    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 notes in this unit