Discussion :

[questionsinfo]

Bonjour,
J'avais posté dans "langages en général" mais il semblerait que ce ne soit pas la bonne rubrique vu le peu de réponses (c'est à dire zero!) que j'ai eu... Mais ma question est assez précise et très théorique... alors je tente ici!
voilà mon problème: j'ai un exercice que je n'arrive pas à faire, et c'est important (j'ai un partiel dans 2 jours...).
Voici l'énoncé:
construire l'automate fini déterministe minimal qui reconnait le langage suivant sur l'alphabet {a,b}
L={(ab)^m a^n|m,n>=0}
c'est à dire le langage associé à l'expression réguliere: (ab)*a*
j'ai d'abord construit l'automate fini non deterministe suivant:

et ensuite en applicant l'algo par sous-ensembles, qu'on nous as enseigné en cours, j'arrive à l'automate déterministe suivant:

Les flèches blanches symbolisent, les entrées et sorties et les états S,A,B,C correspondent à:
S={0,1,4,5,7}
A={2,5,6,7}
B={5,6,7}
C={1,3,4,5,7}
(avec 0,1,2,3,4,5,6,7 les états du précédent NFA)

Donc l'automate déterministe obtenu ne contient que des états finals, donc impossible d'appliquer l'algo de minimisation...
Et je ne sais pas si c'est un automate minimal ou pas... intuitivement, je dirais que oui, mais je ne vois pas non plus comment le démontrer...
donc si vous avez des suggestions, elles seront les bien venues!!
merci d'avance pour votre aide (espérée!! )

[questionsinfo]

Meme si je me rends bien compte que ça ne doit pas intéresser grand monde, j'ai trouvé (vraiment par hasard) la réponse.

Mon prof n'a pas parlé des fameux états "puits" qui sont à considérer comme non finals, puisque non acceptés par l'automate. Donc ils suffit de rajouter ce " puit", et d'y faire pointer tous les autres états quand une chaine de caractères ne correspond pas à l'expression régulière....
Et après de développer l'algo normalement.
Et donc la réponse est non, cet automate n'est pas minimal, C et S sont indistincts!! ouffa!! je me sens plus intelligente d'un coup!