1
$\begingroup$

I've run into a problem concerning epsilon transitions and removing them. Specifically, it is to do with the picture seen in this post. My problem is that I am unsure of what to do with q1. I've already attempted to solve it but I don't know if it's correct. Should it just sit there still with no inputs going to it essentially making it a dead state? What should its loop be that was once an epsilon loop?

Thanks, all help appreciated!
enter image description here

$\endgroup$
1
$\begingroup$

In the original automaton, there is no way to be in $q_1$, read one symbol, and end up in $q_1$, so in the resulting automaton, there is no loop on $q_1$.

$\endgroup$
  • $\begingroup$ So the correct resulting automaton would simply be the second one above but without the loop? Or does q1 have any incoming transitions to it? $\endgroup$ – Fonorte Feb 22 '17 at 11:24
  • $\begingroup$ 1) There is no unique automaton for this. 2) There is no unique algorithm for removing $\epsilon$ transitions, different algorithms may produce different results. 3) I'm answering the question you asked. If you were given an algorithm and you just want us to tell you whether you are applying it correctly, asking that would be out of scope for this site. $\endgroup$ – reinierpost Feb 22 '17 at 11:50
0
$\begingroup$

There won't be a loop over $q_1$ but there will be a transition $q_1\in\delta(q_0,0)$, so it won't be dead state.

$\endgroup$

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.