comment convertir un DFA en une expression régulière?

Question

Je suis en train de lire le livre: introduction à la théorie du calcul et suis resté coincé sur cet exemple.

Convertir un DFA en une expression équivalente en le convertissant d'abord en un GNFA (automate fini non déterministe généralisé), puis convertir GNFA en une expression régulière.

est ici l'exemple: enter image description here

je devrais utiliser ce récursive pour arriver au quatrième état: enter image description here

Malheureusement, je ne peux pas comprendre ce qui se passe de b à c? Je comprends seulement que nous essayons de nous débarrasser de l'état 2, mais comment nous arrivons à c de b?

Merci beaucoup!

Answer 1

Cela peut être assez difficile au début mais je vous suggère de vérifier la définition 1.64 et voir la fonction CONVERT (G) pour plus de jeu. Mais comme une brève explication en utilisant la fonction pour chaque état voisin possible:

• premier de a à b, ajouter un état de départ et un nouvel état acceptent; Ensuite, vous devez calculer chaque nouveau chemin après la suppression de qrip, dans ce cas l'état 1; Donc, de début à q2, vous obtenez seulement l'étiquette a de epsilon et a;

• La même chose va du début à q3, résultant seulement en b;

• Maintenant, de q2 à q2 en passant par qrip, vous devez étiqueter a pour qrip et étiqueter a pour revenir, donc vous obtenez (aa U b);

• Idem va de q3 à q3 par qrip, ce qui entraîne bb, notez qu'il n'y a pas de boucle dans q3, donc pas d'union;

• Maintenant, de q2 à q3 via qrip, il suffit de concaténer a et b pour obtenir une étiquette ab; Enfin, dans l'autre sens, de q3 à q2 passant par qrip, concaténer b et a aboutissant à ba mais cette fois faisant l'union avec le chemin précédent entre q3 et q2;

• Maintenant choisissez un nouveau qrip et recommencez à faire le même algorithme.

Espérons que l'explication était suffisamment claire, mais comme indiqué précédemment, référez-vous à l'algorithme du livre pour une meilleure explication plus détaillée.