The upper bound on a Nondeterministic Finite Automata's configurations number

Question

In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon, in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2,
section "Equivalence of NFAs and DFAs"

discusses the upper bound of a NFA's configurations number.

Here

• NFA stands for Nondeterministic Finite Automata
• DFA stands for Deterministic Finite Automata

NFA is a is a five-tuple $(S, \Sigma, \delta, s_0 , S_A)$, where

• $S$ is the finite set of states in the recognizer, along with an error state $s_e$.
• $\Sigma$ is the finite alphabet used by the FA. Typically, $\Sigma$ is the union of the edge labels in the transition diagram.
• $\delta(s,c)$ is the FA's transition function. It maps each state $s ∈ S$ and each character $c \in \Sigma$ into some next state. In state $s_i$ with input character $c$, the FA takes the transition $s_i \xrightarrow{\text{c}}\delta(s_i ,c)$.
• $s_0 \in S$ is the designated start state.
• $S_A$ is the set of accepting states, $S_A \subseteq S$.

A configuration of a NFA is defined as follows

Each time the NFA must make a nondeterministic choice, the NFA clones itself to pursue each possible transition. Thus, for a given input character, the NFA is in a specific set of states, taken across all of its clones.

In this model, the NFA pursues all paths concurrently. At any point, we call the specific set of states in which the NFA is active its configuration.

When the NFA reaches a configuration in which it has exhausted the input and one or more of the clones has reached an accepting state, the NFA accepts the string.

Given the definitions above, the books states

Consider the state of an NFA when it has reached some point in the input string. [...] the NFA has some finite set of operating clones.

The number of these configurations can be bounded;

for each state, the configuration either includes one or more clones in that state or it does not. Thus, an NFA with $n$ states produces at most $\lvert\Sigma\rvert^n$ configurations.

My question.

Please explain in as much details as possible, how $\lvert\Sigma\rvert^n$ is derived.

I need help, because while trying to follow the book's reasoning, I get lost right after this sentence

for each state, the configuration either includes one or more clones in that state or it does not.

This sounds like the upper bound on the number of configurations should be $2^n$, but instead the book gives $\lvert\Sigma\rvert^n$ bringing in $\Sigma$ seemingly out of the blue.

Answer 1

Remember that:
We can view a nondeterministic computation as a directed acyclic graph of configurations indexed by time.

I have a guess that in your eyes:
$2^n$ for both, one directs itself and one directs others and at most every has the $\Sigma$ chance to go next state, maybe to itself, maybe the other state, so from $1$ to $n$ state, an NFA produces at most $\mid\Sigma\mid^n$ configurations.

Here are more details: http://www.cse.msu.edu/~torng/360Book/NFA/