Perso, j'ai jamais fait autre chose que des calculs simples à la main avec la méthode où on élimine les sommets : tu normalises l'automate (un seul état initial et final), puis tu étiquettes progressivement les transitions par les expressions rationnelles au lieu de simple lettres : au début juste on étiquette par des classes de caractères, puis après tu élimines les sommets un par un en ajoutant des expressions aux transitions qui restent : en gros pour toute paire de sommets p et q tu dois tenir en compte les transitions qui vont de p au sommet que t'as éliminé, puis ensuite vers q, et tu factorise tout ça en une seule expression exprimant une transition de p vers q. À la fin il te reste juste une transition entre l'état initial et final qui correspond à l'expression régulière. Sur des exemples simples l'expression est en général potable, mais j'imagine que ça risque de devenir horrible si la taille augmente.
Je me souviens aussi d'un autre algorithme qui utilise des équations et le lemme d'Arden mais je l'ai plus en mémoire, et je sais plus du tout ce que ça donne à la main, faudra que je révise ça un de ces jours.
[^] # Re: Plus dur
Posté par anaseto . En réponse à la dépêche Regexcrossword : un subtil mélange de sudoku et de mots croisés, à la sauce Regex. Évalué à 2.
Perso, j'ai jamais fait autre chose que des calculs simples à la main avec la méthode où on élimine les sommets : tu normalises l'automate (un seul état initial et final), puis tu étiquettes progressivement les transitions par les expressions rationnelles au lieu de simple lettres : au début juste on étiquette par des classes de caractères, puis après tu élimines les sommets un par un en ajoutant des expressions aux transitions qui restent : en gros pour toute paire de sommets p et q tu dois tenir en compte les transitions qui vont de p au sommet que t'as éliminé, puis ensuite vers q, et tu factorise tout ça en une seule expression exprimant une transition de p vers q. À la fin il te reste juste une transition entre l'état initial et final qui correspond à l'expression régulière. Sur des exemples simples l'expression est en général potable, mais j'imagine que ça risque de devenir horrible si la taille augmente.
Je me souviens aussi d'un autre algorithme qui utilise des équations et le lemme d'Arden mais je l'ai plus en mémoire, et je sais plus du tout ce que ça donne à la main, faudra que je révise ça un de ces jours.