3
$\begingroup$

How does the NFA function on $\epsilon$ input if there is only a single $\epsilon$ string in the language?

I understand that $L^* = \bigcup_{i=0}^\infty L^i$ where $L^0 = \{()\} = \{\epsilon\}$ and $L$ is the language. The empty string $\epsilon$ is an input to a NFA with $\epsilon$ moves.

I suspect an infinite number of strings could be defined with $\epsilon$ anywhere in the order, then the NFA with $\epsilon$ moves would function. However I do not see this definition.

$\endgroup$
2
  • $\begingroup$ Are you talking about Non-deterministic finite state machines (NFA)? I think you mean $\epsilon$ transition (an edge in the state machine graph with the label $\epsilon$) instead of $\epsilon$ move? $\endgroup$
    – plshelp
    Commented Mar 22, 2022 at 17:18
  • $\begingroup$ @plshelp that is correct, $\epsilon$ transition $\endgroup$
    – Nick
    Commented Mar 22, 2022 at 18:47

2 Answers 2

5
$\begingroup$

There is only one empty string, which you denoted by $\epsilon$. If you concatenate two empty strings, then you just get the empty string back: $\epsilon\epsilon = \epsilon$. This is the same as $0+0=0$. There is only one zero, and no matter how many times you add zero to itself, you only get the one zero.

I suspect that the real problem is with the semantics of $\epsilon$-NFAs (which are NFAs with $\epsilon$-transitions; an NFA is a nondeterministic finite state automaton). Let me give a definition which is similar to what you might have in mind. Suppose that $\Sigma$ is an alphabet which does not contain the symbol $\epsilon$, and define $\Sigma_\epsilon = \Sigma \cup \{\epsilon\}$. Here $\epsilon$ does not stand for the empty string. Rather, it is a letter of the alphabet. An $\epsilon$-NFA over the alphabet $\Sigma$ is the same as an NFA over the alphabet $\Sigma_\epsilon$.

Suppose that $A$ is an $\epsilon$-NFA over the alphabet $\Sigma$. Denote by $L_\epsilon(A)$ the language that it accepts as an NFA over the alphabet $\Sigma_\epsilon$. We define the language $L(A)$ over $\Sigma$, which is the language that $A$ accepts as an $\epsilon$-NFA over the alphabet $\Sigma$, as the language obtained from $L_\epsilon(A)$ by removing all $\epsilon$'s from all words.

For example, consider the following $\epsilon$-NFA $A$ over the alphabet $\Sigma = \{a,b\}$:

Automaton created by https://madebyevan.com/fsm/

The languages of this automaton are: $$ L_\epsilon(A) = \epsilon^*(\epsilon a)^+ + \epsilon^*(\epsilon b)^+ \\ L(A) = a^+ + b^+ $$

$\endgroup$
5
  • $\begingroup$ Correct, clear, and concise! $\endgroup$
    – John L.
    Commented Mar 22, 2022 at 18:51
  • 1
    $\begingroup$ I think your problem is that you don't understand the definition of the language accepted by an $\epsilon$-NFA. I gave one definition in my answer. You may be familiar with another definition. However, your mental image of how an $\epsilon$-NFA works is lacking. Choose one of the definitions, and adapt your mental image to match it. $\endgroup$ Commented Mar 22, 2022 at 19:15
  • $\begingroup$ Wiki en.wikipedia.org/wiki/Nondeterministic_finite_automaton claims for an $\epsilon$-NFA, $\epsilon$ is an input symbol, but also claims $\epsilon$ transitions do not consume an input, which seems contradictory. Given this, I would suspect your $\Sigma_{\epsilon}$ alphabet is really the one for the $\epsilon$-NFA. A little confused here $\endgroup$
    – Nick
    Commented Mar 22, 2022 at 19:36
  • 1
    $\begingroup$ Wikipedia is not a good source for mathematics. $\endgroup$ Commented Mar 22, 2022 at 19:47
  • 2
    $\begingroup$ @nick, as Yuval says, Wikipedia's mathematical pages are often low quality. But in this case, I think you are misreading the page. The page says "This automaton replaces the transition function with the one that allows the empty string ε as a possible input." It does not say "possible input symbol"; the empty string ε is not a symbol any more than the input string aa. aa is a sequence containing two symbols; ε is a sequence of zero symbols. $\endgroup$
    – rici
    Commented Mar 22, 2022 at 20:08
4
$\begingroup$

$\epsilon$ is a typographical convention, not a part of the underlying mathematical object. It's written where writing nothing would leave a confusing or ambiguous empty space.

Transitions labeled $\epsilon$ are really unlabeled transitions, and can be taken ad lib, without consuming any characters from the string. They don't consume an $\epsilon$ from the string. The string doesn't contain any $\epsilon$s, even if it's empty.

$\endgroup$
6
  • $\begingroup$ "𝜖" ..."are really unlabeled transitions"..."without consuming any characters from the string". So an indefinite amount of $\epsilon$ transitions can occur between symbols from the input alphabet? $\endgroup$
    – Nick
    Commented Mar 22, 2022 at 18:54
  • $\begingroup$ '"$\epsilon$ is the computer-science version of "this space intentionally left blank"' This statement is misleading if not simply wrong. A whitespace character, which implies "this space intentionally left blank" literally, is not the empty string at all. $\endgroup$
    – John L.
    Commented Mar 22, 2022 at 19:03
  • $\begingroup$ @JohnL. Okay, I reworded. $\endgroup$
    – benrg
    Commented Mar 22, 2022 at 19:32
  • $\begingroup$ @Nick That's correct. $\endgroup$
    – benrg
    Commented Mar 22, 2022 at 19:33
  • 2
    $\begingroup$ @Nick NFAs use angelic nondeterminism: they take whatever legal transitions lead to an accepting state at the end of the string. Or, equivalently, they both take and don't take all legal transitions, remembering a set of reachable nodes at each string position. If there's a cycle of $\epsilon$ transitions, the set simply contains all nodes in the cycle. $\endgroup$
    – benrg
    Commented Mar 22, 2022 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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