Milestones

Parameterization:

• r = number of symbols in a regular expression
• s = number of occurrences of alphabet symbols in a regular expression
• n = number of states in an NFA or DFA
• m = number of transitions in an NFA or DFA
• k = alphabet size

McNaughton and Yamada 1960

Thompson 1968

O(r) time O(r) space algorithm to turn regular expresions into Theta(r) space NFA's with n = Theta(r) and m = Theta(r), where r can be arbitrarily greater than s.

Hopcroft 1971

O(k n log n) time O(k n) space algorithm to turn DFA's into minimum-state DFA's.

Cardon and Crochemore 1982

O(n + m + m log n) time O(m) space algorithm to turn DFA's into minimum-state DFA's.

Brueggemann-Klein 1993 Chang and Paige 1992

O(m + r) time O(r) space algorithm to convert regular expressions into McNaughton and Yamada NFA's with n = s + 1 and m = Theta(s**2) in the worst case.

Keller and Paige 1996

O(m + n + m log n) time O(n) space algorithm to convert any DFA into a minimum-state DFA. Click here to read about the algorithm.

Chang and Paige 1997

O(r) time O(s) space algorithm to convert regular expressions into compressed O(s) space NFA's; NFA simulation and NFA-to-DFA conversion by the subset construction of Rabin and Scott are both improved by computing the next states U one transition away from an arbitrary set of states U in time O(|V| + |U|). Click here to read about the algorithm.