DFA to regex conversion not fast enough

[gavrilikhin-d]

I needed to create a regex for binary numbers divisible by 15.

DFA for this task has:

• 15 states
• 30 transitions

DFA code

#states
s0
s1
s2
s3
s4
s5
s6
s7
s8
s9
s10
s11
s12
s13
s14
#initial
s0
#accepting
s0
#alphabet
0
1
#transitions
s0:0>s0
s0:1>s1
s1:0>s2
s1:1>s3
s2:0>s4
s2:1>s5
s3:0>s6
s3:1>s7
s4:0>s8
s4:1>s9
s5:0>s10
s5:1>s11
s6:0>s12
s6:1>s13
s7:0>s14
s7:1>s0
s8:0>s1
s8:1>s2
s9:0>s3
s9:1>s4
s10:0>s5
s10:1>s6
s11:0>s7
s11:1>s8
s12:0>s9
s12:1>s10
s13:0>s11
s13:1>s12
s14:0>s13
s14:1>s14

Starting from 16 transitions I could feel a major slown down in construction of graph and/or regex.

With 26 transition it takes minutes to construct.

Could you do something with it?