Consider the deterministic finite-state automaton (DFA) below over the…

2025

Consider the deterministic finite-state automaton (DFA) below over the alphabet {a,b}. The state with a small incoming arrow is the initial state, while a double circle state denotes a final state

image.png

The number of states in the MINIMAL DFA for the language accepted by this DFA is:

  1. A.

    1

  2. B.

    2

  3. C.

    3

  4. D.

    4

Attempted by 88 students.

Show answer & explanation

Correct answer: B

The given DFA has three states: an initial state q0 and two final states q1 and q2. To minimize the DFA, we check for equivalent states. States q1 and q2 are both final. From q1, input 'a' goes to q1 (final) and 'b' goes to q2 (final). From q2, inputs 'a' and 'b' both go to q2 (final). Since transitions from both states always lead to a final state, they are equivalent and can be merged. The minimal DFA consists of the initial state q0 and one merged final state, resulting in a total of 2 states.

Explore the full course: Isro