La limite supérieure sur un numéro de configuration de l'automate fini non déterministe

Question

Dans "Ingénierie: un compilateur" 2e éd. par Cooper et Torczon, dans 2.4.1 "Automates finis non déterministes" du chapitre 2,
section "Équivalence des NFAS et DFAS"

Discute de la limite supérieure du numéro de configuration d'un NFA.

Ici

• NFA signifie Automates finis non déterministes
• DFA signifie des automates finis déterministes

NFA est A est un tople $ (s, Sigma, Delta, S_0, S_A) $, où

• $ S $ est l'ensemble fini des états du reconnaissance, ainsi qu'un état d'erreur $ s_e $.
• $ Sigma $ est l'alphabet fini utilisé par la FA. En règle générale, $ Sigma $ est l'union des étiquettes Edge dans le diagramme de transition.
• $ delta (s, c) $ est la fonction de transition de la FA. Il mappe chaque état $ s ∈ S $ et chaque caractère $ c in sigma $ dans un état suivant. Dans l'état $ s_i $ avec le caractère d'entrée $ c $, la FA prend la transition $ s_i xrightarrow { text {c}} delta (s_i, c) $.
• $ s_0 in s $ est l'état de démarrage désigné.
• $ S_a $ est l'ensemble des états d'acceptation, $ s_a subseseq s $.

UN configuration d'une NFA est définie comme suit

Chaque fois que la NFA doit faire un choix non déterministe, la NFA clones elle-même pour poursuivre chaque transition possible. Ainsi, pour un caractère d'entrée donné, la NFA est dans un ensemble spécifique d'états, pris sur tous ses clones.

Dans ce modèle, la NFA poursuit toutes les chemins simultanément. À tout moment, nous appelons l'ensemble spécifique d'états dans lesquels la NFA est active configuration.

Lorsque le NFA atteint une configuration dans laquelle il a épuisé l'entrée et un ou plusieurs des clones ont atteint un état d'acceptation, la NFA accepte la chaîne.

Compte tenu des définitions ci-dessus, les livres indiquent

Considérez l'état d'une NFA lorsqu'il a atteint un certain point dans la chaîne d'entrée. [...] La NFA a un ensemble fini de clones d'exploitation.

Le nombre de ces configurations peut être délimité;

Pour chaque état, la configuration comprend un ou plusieurs clones dans cet état ou non. Ainsi, une NFA avec $ n $ états produit au plus $ lvert Sigma rvert ^ n $ configurations.

Ma question.

Veuillez expliquer autant de détails que possible, comment $ lvert Sigma rvert ^ n $ est dérivé.

J'ai besoin d'aide, car en essayant de suivre le raisonnement du livre, je me perds juste après cette phrase

Pour chaque état, la configuration comprend un ou plusieurs clones dans cet état ou non.

Cela ressemble à la limite supérieure du nombre de configurations devrait être de 2 $ ^ n $, mais au lieu de cela, le livre donne à $ lvert sigma rvert ^ n $ apportant $ sigma $ apparemment à l'improviste.