# State-elimination on FSA, after epsilon-removal construction

I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression.

But there are already some epsilon transitions in this FSA.

My question is:

Should I first follow the epsilon-removal construction, and then do state elimination?

Or can I use state-elimination directly on this FSA? ## 1 Answer

Should I first follow the epsilon-removal construction, and then do state elimination? Or can I use state-elimination directly on this FSA?

If you would like to do more work to kill time, or if you would like to check the effect of epsilon-removal construction, or if someone higher on the command chain forces you to (for reasons I have no informed guess about), you should do the epsilon-removal construction before state elimination.

Otherwise, it is perfectly fine to start state-elimination directly and immediately.

By the way, the regular express I got is $$\left(0+(0+02)(2+42)^*(4+\epsilon)\right)^*(0+02)(42+2)^*\,.$$

• When I try without epsilon-removal, I get the expression (0*(0+02)((4+ε)2)*(4+ε))*0*(0+02)((4+ε)2)*. Could you please explain how you got the (0+(0+02)) part? – Ansar Al Feb 9 '19 at 3:19
• I also want to add that when I do epsilon-removal, I get the expression (0+00*(0+2))(0+2+(0+4)0*(0+2))*. Is this correct? – Ansar Al Feb 9 '19 at 3:23
• Yes, both of your expresses are correct. My expression is correct, too. – John L. Feb 9 '19 at 3:25