CPSC 323 - 9/22

Converting NFA to DFA

• Draw the NFA diagram

• Draw the transition table δ

• Add trap states for null states

Substate Construction

• Same input → Make new state

• Eg: If q_0 inputs 1 and goes into both q_0 and q_1, make the new state q_0q_1

Minimization of DFA

• making a DNA have the minimum number of states

• helps remove redundant states

  • more efficient (faster processing)

• merging equivalent states which share an input

  • given A inputted X and B inputted X, if |X| = N, “A and B are N equivalent” where N is a number of input

  • “State equivalence method”

Given:

0: (A,B) (B, B) (C,B) (D, B) (E,B)

1: (A, C) (B,D) (C, C) (D, E), (E, C)

0 Equivalent: {A, B, C, D} {E}

• A, B, C, D are non final states

1 Equivalent: {A, B, C} {D}{E}

• A, B, C share a zero equivalence [C and D] (1 step up)

2 Equivalent: {A, C} {B}{D}{E}

• A, C share a one equivalence [C] (1 step up)

3 Equivalent {A, C} {B}{D}{E}

• A, C share a two equivalence [C] (1 step up) [STOP: We are going to recurse at this point]