J'ai lu que chaque Automate fini non déterministe (NFA) peut être transféré dans un automate fini déterministe (DFA). Cela peut-il être fait pour kleene star regex, disons un *? Ci-dessus est le NFA pour un *.Automate déterministe fini de Kleene Star
Oui. Un automate fini déterministe à étoile de Kleene a deux états. L'état de départ est final et a une transition vers lui-même pour a, et une transition vers l'autre état pour tous les autres symboles. L'autre état a une transition vers lui-même pour chaque symbole. Ainsi, il accepte la chaîne vide (puisque l'état de départ est final) et un nombre arbitraire de répétitions de a
Tout ce qui n'est pas a enverra le DFA dans l'autre état, qui n'est pas définitif, et à partir duquel il n'y a pas d'échappement. Cela devient un peu plus compliqué si vous appliquez l'étoile Kleene à une expression régulière plus compliquée qu'un simple symbole, mais cela peut toujours être fait: il suffit d'insérer le NFA pour l'expression régulière dans la partie rouge de l'image que vous avez montrée et appliquez l'algorithme standard Powerset construction pour convertir le NFA en DFA. Je recommande fortement d'étudier cet algorithme; Si vous comprenez pourquoi cela fonctionne, vous verrez pourquoi chaque NFA peut être converti en DFA.
Il s'agit simplement d'un état de démarrage unique qui est également l'état d'acceptation. Il a une boucle automatique qui accepte 'a'. 