Add a new start and end state. Then remove one node at a time and replace the effected edges by combining the incoming edges with any self-loops, and then the outgoing edges. Repeat until just the Start and End nodes remain.
For example, if an edge is represeted as (src,regex,dest), and we are removing node x:
srcs, dests = []
loop_regex = "("
for (s,r,d) in edges
if s = d = x then
loop_regex +="|"+r
else if d = x then
add (s,r) to srcs
else if x = s then
add (r,d) to dests
if x = s or x = d then
remove (s,r,d) from edges
loop_regex +=")*"
for (s,rs) in srcs
for (rd,d) in dests
add (s,rd+loop_regex+rd,d) to edges