Automates finis non déterministes | Exemple Sipser 1.16

Je travaille sur le livre Sipser (2e édition) et suis tombé sur cet exemple, que je ne comprends pas. Dans le livre, il indique que ce NFA accepte la chaîne vide,$\epsilon$.

Quelqu'un pourrait-il m'expliquer pourquoi c'est le cas?

Ma compréhension est que $\epsilon$ se déplacera vers $q_3$ qui n'est pas un état accepté.

Vous confondez $\epsilon$avec une lettre. Ce n'est pas une lettre! C'est juste la chaîne vide.

Prenons un modèle un peu plus général, "word-NFA". Un mot-NFA est comme un NFA, mais chaque transition est étiquetée avec un mot arbitraire. Nous disons que le mot-NFA accepte un mot$w$ s'il y a une marche d'un état initial à un état final de telle sorte que si nous concaténons les étiquettes de bord à travers la marche, nous obtenons $w$. En symboles, un mot-NFA accepte$w$ s'il y a une séquence de transitions

$$q_0 \stackrel{w_1}\to q_1 \stackrel{w_2}\to q_2 \stackrel{w_3}\to \cdots \stackrel{w_n}\to q_n$$ tel que:

1. $q_0$est un état initial. (Le modèle habituel ne permet qu'un seul état initial, mais nous pouvons assouplir cette exigence.)
2. $q_n$ est un état final (également appelé état acceptant).
3. Chaque transition $q_{i-1} \stackrel{w_i}\to q_i$ correspond à une transition du mot-NFA.
4. $w = w_1 \ldots w_n$.

Un NFA est un mot-NFA dans lequel toutes les transitions sont étiquetées par des lettres (c.-à-d., Des mots de longueur exactement 1), et un $\epsilon$-NFA est celui dans lequel toutes les transitions sont étiquetées par des lettres ou $\epsilon$(c.-à-d. des mots d'une longueur maximale de 1). Habituellement, nous exigeons également un état initial unique.

Un mot-NFA accepte $\epsilon$ s'il y a une séquence de transitions

$$q_0 \stackrel\epsilon\to q_1 \stackrel\epsilon\to \cdots \stackrel\epsilon\to q_n$$ tel que $q_0$ est un état initial, $q_n$est un état final et toutes les transitions sont valides. En particulier, si un état est à la fois initial et final, le mot-NFA accepte$\epsilon$ (cela correspond à $n = 0$).