There are several completely different algorithms for converting DFAs into regular expressions. See http://www.cs.cmu.edu/~cdm/pdf/KleeneAlg.pdf http://www.cs.c

There are several completely different algorithms for converting DFAs into regular expressions. See http://www.cs.cmu.edu/~cdm/pdf/KleeneAlg.pdf http://www.cs.cmu.edu/~cdm/pdf/KleeneAlg.pdf for three. One of my favorites involves eliminating states by replacing all pairs of transitions through them with regexes -- it winds up looking almost exactly like the Floyd-Warshall algorithm.