Compiler Design

Finite Automata & DFA Construction / Solved Problem: Min DFA

Below is a complete, step-by-step solved problem demonstrating how to construct a minimized DFA from a regular expression.

Problem Statement: Construct a minimized DFA for the regular expression: a*(aa + bb)b*

Understanding the Language

The alphabet is {a, b}. Valid strings consist of zero or more as, followed by either double a or double b, followed by zero or more bs.
Examples of valid strings: aa, bb, aaa, bbb, aabbb.

Step 1: Construct the NFA

Using Thompson's construction, we build the NFA with states q0 to q6.

q0 (start) --a--> q0 (self loop for a*)
q0         --ε--> q1 (move to middle part)

Branch 1 (aa):
q1 --a--> q2 --a--> q3

Branch 2 (bb):
q1 --b--> q4 --b--> q5

Merge at accept:
q3 --ε--> q6 (accept)
q5 --ε--> q6 (accept)
q6        --b--> q6 (self loop for b*)

State	On 'a'	On 'b'	On ε (Epsilon)
q0 (Start)	{q0}	-	{q1}
q1	{q2}	{q4}	-
q2	{q3}	-	-
q3	-	-	{q6}
q4	-	{q5}	-
q5	-	-	{q6}
q6 (Accept)	-	{q6}	-

Step 2: NFA to DFA Subset Construction

Compute epsilon closures and mapping transitions to form the DFA states:

ε-closure({q0}) = {q0, q1}  -> DFA Start State A
ε-closure({q3}) = {q3, q6}  (contains accept state q6)
ε-closure({q5}) = {q5, q6}  (contains accept state q6)

Subset Derivation:
1. Start at A = {q0, q1}:
   - On 'a': transition reaches {q0, q2}. ε-closure({q0, q2}) = {q0, q1, q2} -> State B
   - On 'b': transition reaches {q4}. ε-closure({q4}) = {q4} -> State C

2. Process B = {q0, q1, q2}:
   - On 'a': reaches {q0, q2, q3}. ε-closure = {q0, q1, q2, q3, q6} -> State D (Accept)
   - On 'b': reaches {q4}. ε-closure = {q4} -> State C

3. Process C = {q4}:
   - On 'a': reaches {}. -> State E (Trap/Dead state)
   - On 'b': reaches {q5}. ε-closure = {q5, q6} -> State F (Accept)

4. Process D = {q0, q1, q2, q3, q6} (Accept):
   - On 'a': reaches {q0, q2, q3}. ε-closure = {q0, q1, q2, q3, q6} -> State D
   - On 'b': reaches {q4, q6}. ε-closure = {q4, q6} -> State G (Accept)

5. Process F = {q5, q6} (Accept):
   - On 'a': reaches {}. -> State E (Trap/Dead state)
   - On 'b': reaches {q6}. ε-closure = {q6} -> State H (Accept)

6. Process G = {q4, q6} (Accept):
   - On 'a': reaches {}. -> State E
   - On 'b': reaches {q5, q6}. ε-closure = {q5, q6} -> State F

7. Process H = {q6} (Accept):
   - On 'a': reaches {}. -> State E
   - On 'b': reaches {q6}. ε-closure = {q6} -> State H

Step 3: Minimize the DFA

Apply the Myhill-Nerode partitioning algorithm to find equivalent states:

Initial Groups:
Group 1 (Accept states): {D, F, G, H}
Group 2 (Non-accept states): {A, B, C, E}

Iteration 1:
- Distinguish Group 2:
  - A on 'a' -> B (non-accept), B on 'a' -> D (accept) ==> A and B are distinguishable.
  - C on 'b' -> F (accept), E on 'b' -> E (non-accept) ==> C and E are distinguishable.
  Group 2 splits into individual states: {A}, {B}, {C}, {E}

- Distinguish Group 1:
  - D on 'a' -> D (accept), F on 'a' -> E (non-accept) ==> D and F are distinguishable.
  - G on 'a' -> E (non-accept) ==> D and G are distinguishable.
  - H on 'a' -> E (non-accept) ==> D and H are distinguishable.
  So D is isolated.
  - Now check {F, G, H}:
    - F on 'a' -> E, G on 'a' -> E, H on 'a' -> E
    - F on 'b' -> H, G on 'b' -> F, H on 'b' -> H
    All transitions from F, G, H go to equivalent target states.
    Therefore, F, G, and H are equivalent and merge into a single state (FGH).

Final Partition Groups (Minimized States):
S0 = A (Start)
S1 = B
S2 = C
S3 = D (Accept)
S4 = FGH (Merged Accept)
S5 = E (Dead Trap)

Minimized DFA Table & Traces

Here is the final minimized DFA configuration:

Minimized State	On 'a'	On 'b'	Accepting?
S0 (Start)	S1	S2	No
S1	S3	S2	No
S2	S5	S4	No
S3	S3	S4	YES
S4	S5	S4	YES
S5 (Trap)	S5	S5	No

Trace 1: "aa"

S0 --a--> S1 --a--> S3 (Accept) ==> Accepted

Trace 2: "bb"

S0 --b--> S2 --b--> S4 (Accept) ==> Accepted

Trace 3: "aba"

S0 --a--> S1 --b--> S2 --a--> S5 (Trap) ==> Rejected

DFA Minimization Introduction to Syntax Analysis