Comment puis-je trouver la fermeture d'un D FA

Question

J'essaie de mettre en œuvre la fermeture de D FA. J'ai réussi à mettre en œuvre Union, Intersection Complement, Soustraction et Concaténation de D FA sans utiliser N FA. Notre professeur ne nous a pas dit l'algorithme pour trouver la fermeture. J'ai essayé de le faire en concaténant un D FA à lui-même mais de toute évidence cela n'a pas fonctionné.

J'ai juste besoin des étapes de la façon dont je représente D FA en utilisant la matrice. En parallèle, pouvez-vous élaborer sur la fermeture de Klein, mais je suis sûr que je peux le faire une fois que je sais comment obtenir la fermeture.

Answer 1

Je ne suis pas sûr de ce que vous entendez par fermeture en général. Mais pour la fermeture de Kleene, vous pouvez procéder comme ceci: à partir de chaque état final, vous ajoutez une transition epsilon (sans rien lire) à l'état de départ. Donc, après avoir lu un mot de la langue, vous pouvez commencer avec un autre.

Bien entendu, l'automate résultant n'est plus déterministe. Mais il existe des procédures standard pour le déterminer à nouveau.

Pour une construction directe: regardez toutes les transitions qui entrent dans un état final, par exemple (q, a) -> f. A partir de l'état sortant, ajoutez une autre transition lisant le même symbole et passant à l'état initial: (q, a) -> s. L'automate a donc la possibilité de finir de lire le mot et de recommencer juste après.