3
$\begingroup$

It seems that their purpose is in making designing certain NFAs less onerous? Does this mean that no automata that are implemented have Epsilon-transitions, and that they are kind of a mathematical conceit we adopt for our own ease of design? I'm having a lot of trouble understanding what is "happening" when an Epsilon-transition occurs - is it a way of saying, "have the NFA now switch, automatically, to this next state"?

EDIT: I'm a CS student taking CS Theory for the very first time, so apologies if this question is very rudimentary. I'm a narrative person and I often understand abstract ideas through examples or by trying to understand the problems the ideas are engaging with. I ask very basic questions, but those questions help me hook into the ideas I'm studying.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ How do you imagine real-life NFA without epsilon-transitions? Of course, there is a concept of P systems, but I assume they have memory. $\endgroup$ – rus9384 Sep 14 '17 at 17:15
  • 1
    $\begingroup$ Epsilon transitions help a lot when proving regular languages properties like union, intersection, Kleene star, etc. Try proving those without epsilon transitions... $\endgroup$ – matheussilvapb Sep 14 '17 at 22:18
4
$\begingroup$

Yes, $\epsilon$-transitions can make designing NFAs less onerous, in cases where you just need any NFA recognizing a particular language.

But no, that is not their only purpose. NFA can be used to directly model real-world system behavior, and indeed, in those models, $\epsilon$-transitions represent silent state changes: ones that may happen, but that do not happen in response to receiving any input.

For instance, the coffee machines where I work can be modeled as state machines, with the user's actions as inputs. When operating, and operated, as intended, they are deterministic, responding to each input by making the state change requested by that input every time. This is what makes them usable as machines. But neither users nor the machine always play by the script, and that is when $\epsilon$-transitions happen.

For instance, when the user does nothing for too long, the system will spontaneously revert to its initial state. This will be an $\epsilon$-transition, unless we regard doing nothing for too long as an input to the machine, which seems strange.

Another example: without network connectivity, the machine refuses to serve coffee; losing and regaining network connectivity may happen at any time and no user input is involved, so it will be modeled as $\epsilon$-transitions as well.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is massively clarifying! The coffee example was perfect! $\endgroup$ – Chris T Sep 15 '17 at 3:33
4
$\begingroup$

An epsilon-NFA is a mathematical formalization. Mathematics doesn't have a purpose, per se.

Why do we use this formalization? Sometimes, because it is convenient. Yes, it sometimes makes designing certain NFAs less onerous, and that's useful. So, yes, your suggested rationale/motivation is reasonable. It also makes some algorithms (e.g., Thompson's construction) simpler and easier to understand. It's also intellectually interesting to know what power epsilon-transitions add. There are multiple reasons why one might study this concept; different people might have different reasons for studying it at any point in time. See also Why is non-determinism useful concept?.

What is "happening" when we execute an epsilon-transition? Well, a NFA is not a physically implementable machine; it is an abstract concept. So it is hard to map it to physical, real-world intuitions. See also Why NFA is called Non-deterministic?.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ You're mistaken. Nondeterministic machines can and do model the behavior of physically implementable machines. Of course, the models will be abstractions, leaving out details. $\endgroup$ – reinierpost Sep 14 '17 at 18:07
  • $\begingroup$ @reinierpost, OK, fair enough! I agree that NFAs can and do model the behavior of physically implementable machines. For purposes of the original question ("I have trouble understanding what happens on an epsilon-transition") I'm just trying to say that it's understandable that it's tricky to get intuition about that. Perhaps I could have written that better. $\endgroup$ – D.W.♦ Sep 14 '17 at 18:10
  • 3
    $\begingroup$ I think once you realize that automata describe behavior, not machines, nondeterminism becomes every bit as natural as determinism. $\endgroup$ – reinierpost Sep 14 '17 at 18:14

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.