patternMinor
NFA: How does it function with empty-string moves?
Viewed 0 times
nfamoveswithfunctionemptydoeshowstring
Problem
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.
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.
Solution
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^+
$$
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^+
$$
Context
StackExchange Computer Science Q#150065, answer score: 5
Revisions (0)
No revisions yet.