# NFA: How does it function with empty-string moves?

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.

• 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? Mar 22, 2022 at 17:18
• @plshelp that is correct, $\epsilon$ transition
– Nick
Mar 22, 2022 at 18:47

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\}$$:

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

• Correct, clear, and concise! Mar 22, 2022 at 18:51
• 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. Mar 22, 2022 at 19:15
• 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
– Nick
Mar 22, 2022 at 19:36
• Wikipedia is not a good source for mathematics. Mar 22, 2022 at 19:47
• @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.
– rici
Mar 22, 2022 at 20:08

$$\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.

• "𝜖" ..."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?
– Nick
Mar 22, 2022 at 18:54
• '"$\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. Mar 22, 2022 at 19:03
• @JohnL. Okay, I reworded. Mar 22, 2022 at 19:32
• @Nick That's correct. Mar 22, 2022 at 19:33
• @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. Mar 22, 2022 at 19:58