Discussion :

[questionsinfo]

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:

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 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!! )

[réciproxy]

Dans ta première représentation de l'automate fini non déterministe il y a plein de flèches qui ne sont associés ni à 'a' ni à 'b'.
Je n'ai jamais vu de représentation comme cela.
Par exemple, à partir de ta représentation, quand l'automate passe de l'état '4' à l'état '5', il est impossible de savoir si c'est 'a' ou 'b' qu'il à lu.

Parcontre, dans ta deuxième représentation, on peut deviner si c'est 'a' ou 'b' qui est associé aux flèches d'entrée ou de sortie.

Sinon, sachant que ton automate doit reconnaitre l'expression régulière (ab)*a*, cela implique qu'il doit (entre autre) reconnaitre le mot vide.
Curieusement, ton 2ème automate reconnait le mot vide, mais pas le 1er, alors que le 2ème est sensé être issue du 1er

[gangsoleil]

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)

Hum, il y a quelque chose que je ne comprends pas. Dans le premier cas, tu ne peux sortir que par 7, en etant passe au moins une fois par 1 2 3 4 5 et 6. Or dans ton second automate, tu dis que S correspond a 0 1 4 5 7, et est terminal. Donc sauf erreur, ca veut dire que tu peux sortir (mettons que par 7), sans passer par 2 3 et 6, ce qui montrerait donc que ce ne sont pas les memes automates.

[gorgonite]

Dans ta première représentation de l'automate fini non déterministe il y a plein de flèches qui ne sont associés ni à 'a' ni à 'b'.
Je n'ai jamais vu de représentation comme cela.

Les Epsilon-transitions... tu peux ainsi passer de 0 à 4 et de 4 à 7 sans avoir lu quoique ce soit

Donc l'automate déterministe obtenu ne contient que des états finaux, donc impossible d'appliquer l'algo de minimisation...

Faudrait penser à gérer un automate complet... comme cela tu verrais apparaître un état puits gérant tes erreurs et n'étant pas final (cf les rouges ci-dessous)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Etats = {0;1;2;3}
Initials = {0}
Finals = {0;1;2}
Transitions = {(0,a,1);(1,b,0);(1,a,2);(2,a,2);(0,b,3);(2,b,3);(3,a,3);(3,b,3)}

[réciproxy]

Les Epsilon-transitions... tu peux ainsi passer de 0 à 4 et de 4 à 7 sans avoir lu quoique ce soit

Est-ce que entre 0 et 1, c'est aussi une Epsilon-transition ?

[gorgonite]

Est-ce que entre 0 et 1, c'est aussi une Epsilon-transition ?

a priori oui, toutes celles non étiquetées

[réciproxy]

Alors là... Je pense qu'un simple exemple suffira que je puisse comprendre ;

Quand on est à l'état '0', et que c'est la lettre 'a' est est lu ;
est-ce que l'automate va aller à l'état '1' ou à l'état '4' ?

Quand on est à l'état '0', et que c'est la lettre 'b' est est lu ;
est-ce que l'automate va aller à l'état '1' ou à l'état '4' ?

[questionsinfo]

Alors là... Je pense qu'un simple exemple suffira que je puisse comprendre ;

Quand on est à l'état '0', et que c'est la lettre 'a' est est lu ;
est-ce que l'automate va aller à l'état '1' ou à l'état '4' ?

Quand on est à l'état '0', et que c'est la lettre 'b' est est lu ;
est-ce que l'automate va aller à l'état '1' ou à l'état '4' ?

Désolée de ne pas m'être manifestée plus tôt, comme j'étais assez pressée, j'ai laissé de côté mais entre temps j'ai trouvé la réponse (qui correspond à ce que disait gorgonite, j'avais effectivement zappé le fameux état "puit").

En tout cas pour répondre à ta question reciproxy, le premier automate est non déterministe (c'est à dire qu'il peut faire ce qu'il veut, tant qu'il consomme l'input donné (incluant les e-transitions noté e(epsilon normalement mais je ne connais pas le raccourci-clavier (s'il existe!)), et qui donc se distingue de l'automate déterministe pour lequel à chaque état, pour chaque input, il n'y a qu'une transition possible.
Donc: quand on est à l'état 0 et que a est lu: il y plusieurs chemins:
0-(consomme e)->1-(consomme a)->2
ou
0-(consomme e)->4-(consomme e)->5-(consomme a)->6-(consomme e)->5
ou
0-(consomme e)->4-(consomme e)->5-(consomme a)->6-(consomme e)->7

par contre quand on est à l'état 0 et que b est au début de la chaine de caractère, le mot n'est pas reconnu (il n'y a aucun chemin qui mène de 0 à 3 sans passer par la transition 1-->2 qui consomme a)
ou plus simplement aucun mot du langage reconnu par l'automate ne peut commencer par b.

[réciproxy]

... le premier automate est non déterministe (c'est à dire qu'il peut faire ce qu'il veut, tant qu'il consomme l'input donné ...

J'ai compris que quand cet automate est à l'état '0', et que c'est la lettre 'a' est est lu, qu'il va choisir de manière aléatoire d'aller soit à l'état '1' ou soit à l'état '4'.
C'est bien cela ?

PS : pas de problème pour les temps de réponses

[Médinoc]

Pour un automate supposé déterministe, c'est peut-être ça.

Mais un vrai automate non-déterministe se trouvera dans les deux états à la fois (un AFN de N états correspond à un AFD d'au plus 2^N états)

[réciproxy]

Merci