DFA minimization is the process of transforming a given DFA into an equivalent DFA that has the smallest possible number of states. The resulting minimal DFA recognizes precisely the same language as the original, but in the most compact form.

• Efficiency: A minimal DFA uses less memory to store its states and transitions, and simulation typically involves fewer state transitions, leading to faster execution times. This is crucial for applications like lexical analyzers in compilers.
• Uniqueness: For every regular language, there exists a unique (up to isomorphism, meaning the only difference is how states are named) minimal DFA. This property is fundamental: it means if two regular languages are equivalent, their minimal DFAs will look identical (structurally). This uniqueness allows for a robust method to check language equivalence: simply minimize both DFAs and compare the resulting structures.
• Clarity and Simplicity: A minimal DFA provides the most concise representation of a regular language, making it easier to understand and analyze.

The core principle behind DFA minimization is the identification and merging of indistinguishable states.

Two states, p and q, within a DFA are considered indistinguishable (or equivalent) if, for any possible input string w∈Σ∗, the DFA behaves identically regarding acceptance when starting from p versus starting from q. More formally:

p≡q⟺(∀w∈Σ∗:δ^(p,w)∈F⟺δ^(q,w)∈F).

If two states are indistinguishable, they can be safely merged into a single state without altering the language recognized by the DFA. States that are not indistinguishable are called distinguishable.

The table-filling algorithm systematically finds all pairs of distinguishable states. Once all distinguishable pairs are identified, the remaining unmarked pairs are indistinguishable, forming equivalence classes that become the states of the minimal DFA.

1. Initialize the Table: Create a symmetric table (or a 2D array) where rows and columns represent all distinct pairs of states {qi ,qj } from the original DFA, excluding self-pairs {qi ,qi }. This table will store whether a pair of states is distinguishable. Initially, all cells in the table are unmarked.
2. Mark 0-Distinguishable Pairs (Base Case): Iterate through every pair of states {p,q} in the table. If one state is an accepting state (p∈F) and the other is a non-accepting state (q∈/F), then mark this pair in the table. Reasoning: These states are immediately distinguishable by the empty string ϵ. When starting from p, ϵ leads to an accepting state (since p itself is accepting). When starting from q, ϵ leads to a non-accepting state. Thus, p and q are distinguishable.
3. Iteratively Mark k-Distinguishable Pairs: Repeat the following procedure until an entire pass through the table results in no new pairs being marked: For every unmarked pair of states {p,q} in the table: For each input symbol a∈Σ: Calculate the next states that p and q would transition to on input a: Let p′=δ(p,a) and q′=δ(q,a). Check the table for the pair {p′,q′} (or {q′,p′} since the table is symmetric). If the pair {p′,q′} is already marked as distinguishable in the table, then mark the current pair {p,q} as distinguishable. Reasoning: If p′ and q′ are distinguishable by some string w′ (meaning w′ leads one to an accepting state and the other to a non-accepting state), then the string aw′ will distinguish p and q. Therefore, p and q must also be distinguishable. This iterative process effectively finds states that are distinguishable by strings of increasing length.
4. Identify Indistinguishable States (Equivalence Classes): After the algorithm terminates (when no new marks are added in a full pass), all pairs of states {p,q} that remain unmarked in the table are indistinguishable. These unmarked pairs define equivalence classes. Group all indistinguishable states together into sets. For example, if {q1 ,q2 } is unmarked and {q2 ,q3 } is unmarked, then q1 ,q2 ,q3 all belong to the same equivalence class. Each such equivalence class will form a single state in the minimal DFA.
5. Construct the Minimal DFA: Let the equivalence classes found in step 4 be [Q1 ],[Q2 ],…,[Qm ]. These will be the states of the minimal DFA, Mmin . States (Qmin ): The set of states in Mmin is the set of all equivalence classes: Qmin ={[Q1 ],[Q2 ],…,[Qm ]}. Alphabet (Σmin ): Same as the original DFA: Σmin =Σ. Initial State (q0min ): This is the equivalence class that contains the original DFA's initial state q0 . So, q0min =[q0 ]. Final States (Fmin ): An equivalence class [Qj ] is an accepting state in Mmin if and only if any (and consequently, all) states within that equivalence class are accepting states in the original DFA. So, Fmin ={[Qj ]∣Qj ∩F=∅}. Transition Function (δmin ): For an equivalence class [Qj ] and an input symbol a, the transition is defined as δmin ([Qj ],a)=[δ(q,a)] for any q∈[Qj ]. This is well-defined because if p and q are in the same equivalence class, then δ(p,a) and δ(q,a) must also be in the same equivalence class for any a. (If they weren't, then a followed by some string would distinguish p and q, contradicting their indistinguishability).

Let's minimize the following DFA M:
States Q={A,B,C,D,E,F}, Initial state A, Final states F={C,D}.
Transitions (δ):
| State | Input '0' | Input '1' |
| ----- | --------- | --------- |
| A | B | C |
| B | A | D |
| C | E | F |
| D | E | F |
| E | E | F |
| F | F | F |
1. Initialize Table: Create a table for all pairs: (A,B), (A,C), ..., (E,F).

1. Mark 0-Distinguishable Pairs:
   Final States: {C,D}
   Non-Final States: {A,B,E,F}
   Mark all pairs where one is from F and the other is from Q∖F:
   ○ (A,C) X, (A,D) X
   ○ (B,C) X, (B,D) X
   ○ (C,E) X, (C,F) X
   ○ (D,E) X, (D,F) X
2. Iteratively Mark k-Distinguishable Pairs:
   Pass 1:
   ○ (A,B): δ(A,0)=B,δ(B,0)=A. Pair (B,A) unmarked.
   δ(A,1)=C,δ(B,1)=D. Pair (C,D) is unmarked. Cannot mark (A,B) yet.
   ○ (A,E): δ(A,0)=B,δ(E,0)=E. Pair (B,E) is unmarked.
   δ(A,1)=C,δ(E,1)=F. Pair (C,F) is marked from Step 2. So, mark (A,E) X.
   ○ (A,F): δ(A,0)=B,δ(F,0)=F. Pair (B,F) is unmarked.
   δ(A,1)=C,δ(F,1)=F. Pair (C,F) is marked. So, mark (A,F) X.
   ○ (B,E): δ(B,0)=A,δ(E,0)=E. Pair (A,E) is marked. So, mark (B,E) X.
   ○ (B,F): δ(B,0)=A,δ(F,0)=F. Pair (A,F) is marked. So, mark (B,F) X.
   ○ (C,D): δ(C,0)=E,δ(D,0)=E.
   δ(C,1)=F,δ(D,1)=F. Cannot mark (C,D) yet.
   ○ (E,F): δ(E,0)=E,δ(F,0)=F. Pair (E,F) is unmarked.
   δ(E,1)=F,δ(F,1)=F. Cannot mark (E,F) yet.
3. Pass 2: (Only check unmarked pairs from Pass 1)
   ○ (A,B): δ(A,0)=B,δ(B,0)=A. Pair (B,A) is unmarked.
   δ(A,1)=C,δ(B,1)=D. Pair (C,D) is unmarked. Cannot mark (A,B) yet.
   ○ (C,D): δ(C,0)=E,δ(D,0)=E.
   δ(C,1)=F,δ(D,1)=F. Cannot mark (C,D) yet.
   ○ (E,F): δ(E,0)=E,δ(F,0)=F. Pair (E,F) is unmarked.
   δ(E,1)=F,δ(F,1)=F. Cannot mark (E,F) yet.
4. No new pairs were marked in Pass 2. The algorithm terminates.
5. Identify Indistinguishable States:
   The unmarked pairs are: (A,B), (C,D), (E,F).
   This implies the following equivalence classes:
   ○ [A,B]: Contains A and B. Both are non-final.
   ○ [C,D]: Contains C and D. Both are final.
   ○ [E,F]: Contains E and F. Both are non-final.
6. Construct the Minimal DFA:
   ○ States: {[A,B],[C,D],[E,F]}
   ○ Initial State: [A,B] (since A is the original initial state)
   ○ Final States: {[C,D]} (since C and D are final)
   ○ Transitions (δmin ):
   ■ δmin ([A,B],0): δ(A,0)=B∈[A,B], δ(B,0)=A∈[A,B]. So,
   δmin ([A,B],0)=[A,B].
   ■ δmin ([A,B],1): δ(A,1)=C∈[C,D], δ(B,1)=D∈[C,D]. So,
   δmin ([A,B],1)=[C,D].
   ■ δmin ([C,D],0): δ(C,0)=E∈[E,F], δ(D,0)=E∈[E,F]. So,
   δmin ([C,D],0)=[E,F].
   ■ δmin ([C,D],1): δ(C,1)=F∈[E,F], δ(D,1)=F∈[E,F]. So,
   δmin ([C,D],1)=[E,F].
   ■ δmin ([E,F],0): δ(E,0)=E∈[E,F], δ(F,0)=F∈[E,F]. So,
   δmin ([E,F],0)=[E,F].
   ■ δmin ([E,F],1): δ(E,1)=F∈[E,F], δ(F,1)=F∈[E,F]. So,
   δmin ([E,F],1)=[E,F].
   The original DFA had 6 states, and the minimized DFA has 3 states. This algorithm guarantees finding the unique minimal DFA.