1
$\begingroup$

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?

FSA

Improve this question
$\endgroup$
0
$\begingroup$

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)^*\,.$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Ansar Al Feb 9 '19 at 3:19
  • $\begingroup$ 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? $\endgroup$ – Ansar Al Feb 9 '19 at 3:23
  • 1
    $\begingroup$ Yes, both of your expresses are correct. My expression is correct, too. $\endgroup$ – John L. Feb 9 '19 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.