Is ε a part of alphabet or property of alphabet and NFA in FA

Question

I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following:

3rd point of the above image is the point of interest in the post

According to a few stackoverflow post: 1)https://math.stackexchange.com/questions/1689850/is-the-empty-string-always-in-a-finite-alphabet

2)https://stackoverflow.com/questions/52286628/how-can-i-tell-if-a-dfa-accepts-an-empty-string#:~:text=The%20empty%20string%20is%20never,string%20to%20accept%20the%20language.

It looks like ε is the property of the alphabet and NFA in the form of "zero sequence of alphabet symbols" and "ε transition". So it cannot be a part of the alphabet

But sipser does mention it as the union of alphabet and ε. So what does that imply?

1. Is ε a symbol like any other symbol present in the alphabet, then it isn't special anymore, which also means ε should be present in the input string such as "abεba" etc..

2. or, it's more like he wants to imply that NFA can have empty transition that is without reading any input, but to do that we use a special symbol ε. That's why he included ε in alphabet?

3. The meaning of ε is different in these two contexts? in the case of strings it means zero length and in the case of input it means no need to read input?

Can someone explain "can ε be a part of alphabet or not"

Answer 1

In the definition of $\Sigma_\epsilon$, $\epsilon$ is a letter (which must not belong to $\Sigma$).

Elsewhere, $\epsilon$ is the empty word.

To avoid confusion, you can use different symbols for the two different meanings, say use $\epsilon$ for the empty word and $\hat\epsilon$ for the letter of $\Sigma_\epsilon$.

Answer 2

There's a difference between how an NFA is represented and how it computes. Three common representations of an NFA are its state transition diagram, the tabular representation, and a description of each component of the 5-tuple by just writing down various sets and formulas. These are equivalent representations - if you have the state transition diagram, then you can construct the table, and vice-versa.

In terms of how an NFA computes, when an NFA reaches a new state, it splits into multiple copies, with one copy at this new state and other copies at states that can be reached from this new state by following one or more $\epsilon$-transitions. Because these new states are reached without consuming input, you can assume an empty string has been inserted at this place in the input. When defining the NFA, these $\epsilon$-transitions were placed in the diagram.

In the tabular representation of the NFA, you would have an extra column, with column heading $\epsilon$ say; the subset in row $q$ and column $\epsilon$ of the table is exactly the subset of states that can be reached from $q$ by following a single $\epsilon$-transition. In this tabular representation, whether you give the column a heading of $\epsilon$ or some other letter such as $\epsilon'$ is irrelevant, as long as it's clear that the entries in this column refer to the subsets of states that can be reached by an $\epsilon$-transition. The tabular form contains the same information as the state transition diagram.

In the tabular form, the subsets in the column labeled $\epsilon$ refer to subsets that can be reached by following a single arrow labeled $\epsilon$ (and are just an equivalent representation of the NFA's diagram), whereas in the computation, the machine can reach states that follow even 2 or more arrows labeled $\epsilon$ without consuming any input. To be precise, when the machine reaches a subset $R$ of states, the machine splits into copies and immediately reaches the subset $E(R)$ of states, where $E(R)$ is the set of states reachable from $R$ by following zero or more $\epsilon$-transitions.

An input string such as $abba$ would be accepted by the NFA if there is a sequence of transitions with labels $a, b, \epsilon, \epsilon, b, a$ that take the machine from the start state to an accepting state. Here, the string $abba$ is over the language $\{a,b\}$, and there are $\epsilon$-transitions in the diagram which you can interpret as being equivalent to an empty string.