Comment un NFA utilise-t-il les transitions epsilon?

Dans l'image ci-dessous, j'essaie de comprendre exactement ce que cette NFA accepte.

Ce qui me déroute, c'est le saut à .q $\epsilon$$q_0$

• Si un est entré, le système passe-t-il à la fois à et (l'état d'acceptation)?q 0 q $0$$q_0$ $q_1$

• Si un est entré, le système passe-t-il à la fois à et ?q 1 q $1$$q_1$$q_2$

• Le système passe-t-il uniquement à (état accepté), si aucune entrée n'est donnée (chaîne vide)?$q_1$

Chaque fois que vous êtes dans un état qui a une transition , cela signifie que vous êtes automatiquement dans les DEUX états, pour vous simplifier la situation:$\epsilon$

Si la chaîne est vos automates se terminent à la fois par etq 0 q $\epsilon$$q_0$$q_1$

Si votre chaîne est '0', ce sera à nouveau dans etq $q_0$$q_1$

Si votre chaîne est '1', ce ne sera que dans , car si vous regardez à partir du point de , vous avez une transition '1' vers , mais vous devez également regarder si vous êtes dans ( si vous étiez dans vous étiez toujours dans aussi) alors il n'y a pas de transition '1', donc ce chemin alternatif "meurt".q 0 q 2 q 1 q 0 q $q_2$$q_0$$q_2$$q_1$$q_0$$q_1$

En regardant ces cas, il est facile de voir que vos automates acceptent , , et allant de à , la seule façon d'atteindre est , donc, cela reprend vos automates à , ,0 ∗ q 0 q 1 q 2 0 ∗ 11 ∗ 1 ϵ 0 ∗ 0 ∗ 11 ∗$\epsilon$$0^*$$q_0$$q_1$$q_2$$0^*11^*1$$\epsilon$$0^*$$0^*11^*1$

J'espère que cela vous a aidé, si vous avez d'autres doutes, demandez simplement!

Dans l'état sans lire aucune entrée, le NFA reste à la fois dans et (dans un univers alternatif, si vous voulez), il passe également à l'état . Ceci est similaire à ce qui se passerait dans un NFA qui avait deux transitions vers des états différents sur une entrée d'un personnage. En particulier, votre NFA accepte la chaîne vide, car sur aucune entrée, il peut effectuer une transition vers l'état d'acceptation .q 0 q 1 q $q_0$$q_0$$q_1$$q_1$

Poursuivant votre exemple, de l'état voyant l'entrée , il consommerait ce symbole, resterait dans l'état (la boucle) et passerait également à l'état , acceptant ainsi l'entrée . Dans l'état lisant l'entrée , le NFA passe à l'état . Il peut également ne pas consommer le , passer à l'état dans un autre univers et s'y coincer (et ne pas accepter, car il n'a pas lu toutes les entrées), car il n'y a pas de transition de sur un .$q_0$$0$$q_0$$q_1$$0$$q_0$$1$$q_2$$1$$q_1$$q_1$$1$

Voyez si vous pouvez vous convaincre que le langage accepté par cette machine est dénoté par l'expression régulière , c'est-à-dire n'importe quelle chaîne composée de zéro ou plus s suivi de rien du tout ou de deux ou plus s.$0^*+0^*11^*1$$0$$1$

Soit dit en passant, il existe un algorithme qui prend un NFA avec -moves et produit un NFA équivalent sans -moves, ce que je pense que vous apprendrez sous peu.$\epsilon$$\epsilon$

J'ai essayé de créer DFA pour ce NFA

$\sum$ - ensemble alphabet

$Q$Ensemble d'états

$\sigma(Q\times (\sum \cup {\epsilon} )) \to P(Q)$ fonction d'état

$q_0 = q_0$

$F \subseteq Q, F = \{q_0\}$

Parce que chaque NFA a un DFA égal, nous pouvons construire DFA pour ce NFA donné.$M'$

alphabet - le même

$Q' = P(Q)$ - états

L'état actuel est$R \in P(Q)$

$E(R)$ - fermeture de epsilon retourne un ensemble d'états accessibles sur zéro ou plus - connexions pour chaque$\epsilon$$r \in R$

$\sigma'(R,a) = \bigcup_{r \in R} E(\sigma(r,a))$ -transitions

$q'_{0} = E(\{q_0\})$

$F' = P(Q) \div F$

Certains calculent sur ce FSM

$1.$ $\epsilon$ en entrée: l'état initial inclut pour que FSM accepte$q'_{0} = E(\{q0\}) = \{q_0, q_1\}$$q_1$$\epsilon$

$2.$ $0*$ en entrée: pour que FSM accepte$\sigma'(\{q_0, q_1\}, 0) = E(\sigma(q_0,0)) \cup E(\sigma(q_1,0)) = \{q_0, q_1\} \cup \{ \} = \{q_0, q_1\}$$0*$

au moins$\{\epsilon, 0* \} \subset L (M')$

Merci à David Richerby