# Difference between methods of converting from finite state machine to regular expression

I have a question about method that I saw on internet and method that my professor showed me. I have this finite state machine:

q1(a)=q1
q1(b)=q2
q2(a)=q2
q2(b)=q3
qf3(a)=qf3
qf3(b)=qf3


My professor using a method

r(p,q,k+1)=r(p,q,k)|r(p,k+1,k)r(k+1,k+1,k)*r(k+1,q,k)


and he start from (1,3,3). He get r(1,3,3)=a*ba*b|(a|b)*, I understand that method but if a finite state machine is more complicated then it takes to much time, so I saw on internet and I saw here a method where I start like this

q1=epsilon+q1a, q1=a*
q2=q1b+q2a, q2=a*ba*
q3=q2b+q3a+q3b, q3=a*ba*b(a+b)*,q3=a*ba*b(a|b)*


Both regular expression look similar but I do not know is that the same? Can you tell me where is difference if difference exist?

• There are several algorithms for checking regular expression equivalence. One of them is to convert the regular expressions to DFAs (via NFAs), compute the symmetric difference automaton, and check whether it accepts the empty language. – Yuval Filmus Feb 2 '19 at 9:46

There is a reference question on methods to convert a finite automaton into a regular expression. Personally I am very fond of the "State removal method" which is equivalent to the "Transitive closure method" you seem to be using. The reason is that the administration you do in the state removal seems to be less, and is more easily kept as labels to edges, rather than keeping track of many $$R[i,j,k]$$ sets.