Minimisation des automates finis deterministes
Bonjour,
voilà mon problème: j'ai un exercice que je n'arrive pas à faire, peut-être pourrez-vous m'aider...
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:
http://dl.dropbox.com/u/11863989/img/nfa.png
et ensuite en applicant l'algo par sous-ensembles, qu'on nous as enseigné en cours, j'arrive à l'automate déterministe suivant:
http://dl.dropbox.com/u/11863989/img/dfa.png
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 finaux, 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!! :) )