Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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^+ $$
aa. aa is a sequence containing two symbols; ε is a sequence of zero symbols.
$\endgroup$
$\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.
