Il limite superiore sul numero di configurazioni di automi finite non determinanti

Question

In "Ingegneria: un compilatore" 2nd ed. di Cooper e Torczon, in 2.4.1 "Automata finiti non deterministici" del capitolo 2,
sezione "Equivalenza di NFA e DFA"

Discute il limite superiore del numero di configurazioni di NFA.

Qui

• NFA sta per automi finiti non determinanti
• DFA è l'acronimo di Automata finita deterministica

NFA è A è un $ (s, Sigma, Delta, S_0, S_A) $, dove

• $ S $ è il set finito di stati nel riconoscimento, insieme a uno stato di errore $ s_e $.
• $ Sigma $ è l'alfabeto finito utilizzato dalla FA. In genere, $ Sigma $ è l'unione delle etichette dei bordi nel diagramma di transizione.
• $ Delta (s, c) $ è la funzione di transizione di FA. Mappa ogni stato $ s ∈ S $ e ogni carattere $ c in sigma $ in uno stato successivo. In State $ S_i $ con carattere di input $ c $, la FA prende la transizione $ s_i xrightarrow { text {c}} Delta (s_i, c) $.
• $ s_0 in s $ è lo stato iniziale designato.
• $ S_a $ è l'insieme di stati accettanti, $ s_a sottoseteq s $.

UN configurazione di un NFA è definito come segue

Ogni volta che l'NFA deve fare una scelta non deterministica, l'NFA si clice stesso per perseguire ogni possibile transizione. Pertanto, per un determinato carattere di input, l'NFA si trova in un insieme specifico di stati, presi in tutti i suoi cloni.

In questo modello, l'NFA persegue contemporaneamente tutti i percorsi. In qualsiasi momento, chiamiamo l'insieme specifico di stati in cui l'NFA è attivo ITS configurazione.

Quando l'NFA raggiunge una configurazione in cui ha esaurito l'input e uno o più cloni ha raggiunto uno stato accettante, l'NFA accetta la stringa.

Date le definizioni sopra, afferma i libri

Considera lo stato di un NFA quando ha raggiunto un punto nella stringa di input. [...] L'NFA ha una serie finita di cloni operativi.

Il numero di queste configurazioni può essere limitato;

Per ogni stato, la configurazione include uno o più cloni in quello stato o no. Pertanto, un NFA con stati $ n $ produce al massimo configurazioni $ lvert Sigma rvert^n $.

La mia domanda.

Si prega di spiegare il maggior numero possibile di dettagli, come è derivato $ lvert Sigma rvert^n $.

Ho bisogno di aiuto, perché mentre provo a seguire il ragionamento del libro, mi perdo subito dopo questa frase

Per ogni stato, la configurazione include uno o più cloni in quello stato o no.

Sembra che il limite superiore sul numero di configurazioni dovrebbe essere $ 2^n $, ma invece il libro dà $ lvert Sigma rvert^n $ portando $ Sigma $ apparentemente di punto.