Automate

[magodeoz]

Bonjour,
J'ai un problème avec cet automate.
Soit Σ={0,1} et L le langage qui contient tous les mots tels que toute paire de 0 (0,0) apparaisse avant toute paire 1 (1,1).
On me demande un mot minimal en longueur accepté et non accepté et de donner un automate déterministe d'états finis reconnaissant le langage.
Pour le mot de longueur minimale accepté j'ai dit :{0}
Pour le mot de longueur minimale non accepté j'ai dit : {1,1,0,0}, je ne pense pas qu'il y est plus court.
Je ne m'en sors pas pour construire l'automate....
J'avais tenté un automate ayant 2 états A et B avec A initial,B accepteur:

Avec 0: A->B
1: A->A
0:B->B
1:B->A

Mais ça ne fonctionne pas car par ex le mot {1} devrait être accepté...
Donc j'ai tenté:
Avec 0: A->B
1: A->B
0:B->B
1:B->A mais ça ne marche pas non plus car {1,0,1,1} n'est pas accepté.

Donc j'imagine qu'il faut plus de 2 états... Comme j'ai du mal à trouver l'automate non déterministe correspondant je ne parviens pas à transcrire....

D'avance je vous remercie,
Mägodeoz
-----

[kwariz]

Bonjour,

On ne rejette le mot que s'il contient une paire de 0 qui suit une paire de 1 ... dans tous les autres cas le mot est accepté ...

[magodeoz]

Merci de votre réponse,
Oui ça je sais, mais je peine pour la réalisation de l'automate.
Vous avez une idée...? Nombre d'états?J'ai essayé 2 états, sans succès... D'habitude, je réalise l'automate non déterministe pour retrouver le déterministe mais là non plus je ne m'en sors pas....

[kwariz]

En fait la démarche va être de construire un DFA qui accepte les mots qui ont une paire 0 qui suit une paire de 1 et d'en prendre le complément (à la louche 5 états).

[A voir en vidéo sur Futura]

[magodeoz]

Ah oui d'accord... Merci beaucoup, je vais voir si je m'en sors maintenant.

Mägodeoz

[kwariz]

Pas de problème
Poste ta solution pour les suivants, mais je pense que ça ne te posera pas plus de soucis que ça.

[magodeoz]

En fait, si, toujours un souci Le DFA qui accepte les mots qui ont une paire 0 qui suit une paire de 1 je ne m'en sors pas...

[kwariz]

Donc nous cherchons à construire un DFA qui va reconnaître les mots qui ont une paire de 1 suivi par une paire de 0. Il y a plusieurs méthodes pour faire, mais comme l'expression est simple on peut tenter une pproche directe :
On commence par l'état de départ S, si on tombe sur un 0 on reste sur S, si on tombe sur un 1 alors on passe vers un nouvel état A. Si en A on tombe sur un 0 cela signifie qu'on a pas trouvé une paire de 1 donc on retourne en S, en revanche si on tombe sur un 1 alors on vient de trouver une paire de 1 : on passe à un autre état B qui va marquer le début de la recherche d'une paire de 0. Donc en B si on boucle tant qu'on tombe sur des 1 et on passe sur un nouvel état C si on tombe sur un 0, C va «chercher» la paire de 0. Donc en C si on tombe sur un 1 c'est qu'on vient d'échouer à trouver une paire de 0 (mais on sait qu'on a déjà vu une paire de 1) donc on retourne en B mais si on tombe sur un 0 alors on vient de trouver une paire de 0 donc on peut passer a l'état final F qui acceptera le mot.
Une image vaut mille mots :

dfa.png

J'ai mis en vert la partie «recherche d'une paire de 1» et en jaune la partie «recherche d'une paire de 0». En bleu quand on a effectivement trouvé une paire de 1 et en rouge quand on a effectivement trouvé une paire de 0 qui suit une paire de 1.

Donc voilà le DFA qui accepte les mots qui ont au moins une paire de 1 et au moins une paire de 0 après la paire de 1, et qui refuse tous les autres c'est-à-dire seront refusés ceux qui n'ont pas de paire de 1, ou ceux qui n'ont pas de paire de 0 après une paire de 1.
Ce que tu cherches est exactement l'opposé, tu veux refuser ces mots et accepter les autres : il faut donc construire le complément de DFA 1 = tous les états acceptants deviennent non acceptants et vice et versa.

dfa2.png

Si tu as des questions, n'hésite pas.

[magodeoz]

J'ai tout compris....Vous aviez raison, c'était simple, me suis compliqué la vie...A chaque fois je démarrais mon automate avec à partir de l'état initial pour 0 et 1 je passais dans l'état suivant...Bref, je faisais n'importe quoi.J'essayais de faire un automate en cycle,en vain.Votre message est vraiment clair, je vois mieux le cheminement désormais et un grand merci pour les couleurs ça permet de bien comprendre les choses.
kwariz, pourriez-vous m'aider pour ceci:
J'ai un petit QCM sur les automates et j'ai quelques soucis, une petite aide me serait la bienvenue...
Vrai ou Faux,donner une justification de la réponse:
1) Tout langage d'états finis est fini.
-Faux, il est possible de reconnaître des langages infinis (nombre infini de mots). Exemple l'ensemble des mots contenant autant de a que de b.
2) Tout langage fini est d'états finis.
-Vrai je pense,mais j'ai du mal à justifier...
3) Tous les sous-ensembles d'un langage d'états finis sont d'états finis.
-Vrai mais idem que pour 2.
4) Tout langage d'états finis peut être reconnu par un automate déterministe avec un seul état terminal.
Faux,il peut y en avoir plusieurs.Exemple, Σ={a,b,c} un nombre impair de a et un nombre pair de b ou un c.Plus d'un état accepteur.Autre exemple, et bien celui que vous m'avez expliqué précédemment.
5) Tout langage d'états finis peut être reconnu par un seul automate non-déterministe avec un seul état terminal.
Je dirais Faux également.
6) Tout langage d'états finis peut être reconnu par un automate non-déterministe avec ɛ-transition avec un seul état terminal.
Aucune idée...
7) Si tous les états d'un automates déterministes sont terminaux alors il accepte tous les mots de son alphabet.
Vrai.ça me parait évident mais comment le justifier?...
8) Si L n'est pas d'états finis et L' est fini alors L∩L' est d'états finis.
ça c'est VRAI.

[magodeoz]

Petite question, avec quel logiciel avez-vous réussi à faire un schéma d'une telle qualité? J'allais posté mon automate faux qui avait les 3 derniers mêmes états que le votre, mais j'avoue le résultat n'est pas tout à fait le même avec paint

[kwariz]

...
kwariz, pourriez-vous m'aider pour ceci:

Déjà on peut se tutoyer

J'ai un petit QCM sur les automates et j'ai quelques soucis, une petite aide me serait la bienvenue...
Vrai ou Faux,donner une justification de la réponse:

1) Tout langage d'états finis est fini.
-Faux, il est possible de reconnaître des langages infinis (nombre infini de mots). Exemple l'ensemble des mots contenant autant de a que de b.

Effectivement faux, pour le contre-exemple on peut prendre le langage L={les mots ayant un nombre pair de 0}. ATTENTION, les langages reconnus par des dfa ne peuvent pas «compter et comparer» des caractères différents : il n'existe aucun dfa qui reconnaisse l'ensemble des mots contenant autant de a que de b.

2) Tout langage fini est d'états finis.
-Vrai je pense,mais j'ai du mal à justifier...

C'est effectivement vrai, le langage est fini L={w₀, w₁, ..., w_n}, donc tu peux construire le dfa qui va accepter w₁ ou w₂ ou ... ou w_n (le nfa est trivial)

3) Tous les sous-ensembles d'un langage d'états finis sont d'états finis.
-Vrai mais idem que pour 2.

Prenons L={a⁺b⁺}, L'={aⁿbⁿ, n>0} en est-il un sous-ensemble ? L' est-il un langage d'états finis ?

4) Tout langage d'états finis peut être reconnu par un automate déterministe avec un seul état terminal.
Faux,il peut y en avoir plusieurs.Exemple, Σ={a,b,c} un nombre impair de a et un nombre pair de b ou un c.Plus d'un état accepteur.Autre exemple, et bien celui que vous m'avez expliqué précédemment.
5) Tout langage d'états finis peut être reconnu par un seul automate non-déterministe avec un seul état terminal.
Je dirais Faux également.
6) Tout langage d'états finis peut être reconnu par un automate non-déterministe avec ɛ-transition avec un seul état terminal.
Aucune idée...

Imagine que tu as un nfa avec n états terminaux, peut-on rajouter une ɛ-transition de ces états terminaux vers un nouvel unique état terminal ? Est-ce encore un nfa ? si tu élimines les ɛ-transitions es-tu certain de ne garder qu'un état terminal ?

7) Si tous les états d'un automates déterministes sont terminaux alors il accepte tous les mots de son alphabet.
Vrai.ça me parait évident mais comment le justifier?...

L'automate est-il complet ? S'il ne l'est pas ça change quelquechose ?

8) Si L n'est pas d'états finis et L' est fini alors L∩L' est d'états finis.
ça c'est VRAI.

Que se passe-t-il si L' est l'ensemble vide ?

---

Bon, toutes ces réponses sont sujettes à caution car je me base sur mon cursus qui date des années 90 et qui n'est pas forcément frais, surtout concernant les pistes pour les 4,5,6 (en plus le vocabulaire a un peu changé) ...

[kwariz]

Petite question, avec quel logiciel avez-vous réussi à faire un schéma d'une telle qualité? J'allais posté mon automate faux qui avait les 3 derniers mêmes états que le votre, mais j'avoue le résultat n'est pas tout à fait le même avec paint

J'utilise graphviz. Pour générer le premier DFA le code est :

digraph DFA {
  rankdir=LR;
    label="DFA 1 : mots ayant une paire de 0 après une paire de 1";
    node [shape = circle];
    S;
    a [label="A"];
    b [label="B"];
    c [label="C"];
    
    node [shape = doublecircle];
    d [label="F"];
    
    S -> S [label = "0" color="darkgreen"];
    S -> a [label = "1" color="darkgreen"];
    a -> S [label = "0" color="darkgreen"]; 
    a -> b [label = "1" color="blue"];
    b -> b [label = "1" color="orange"];
    b -> c [label = "0" color="orange"];
    c -> b [label = "1" color="orange"];
    c -> d [label = "0" color="red"];
    d -> d [label = "*"];
  }

[magodeoz]

De nouveau, merci de ta réponse

J'utilise graphviz.

Vraiment top je trouve.

Déjà on peut se tutoyer

Merci Plus simple pour les conjugaisons.
1 et 2 ok, c'est bien ce que j'avais compris.
3)

Prenons L={a+b+}, L'={anbn, n>0} en est-il un sous-ensemble ? L' est-il un langage d'états finis ?

Oui. Non car il n'existe aucun dfa qui reconnaisse l'ensemble des mots contenant autant de a que de b.Donc FAUX.Mais L n'est pas d'états finis non?

7) L'automate est-il complet ? S'il ne l'est pas ça change quelque chose ?

Ah oui d'accord...Que c'est bien vu... Oui s'il n'est pas complet ça change quelque chose car si par exemple pour un langage {a,b} , on a dès l'état initial aucune boucle avec b (et a allant à l'état 2) ,tout mot commençant par b ne sera pas accepté. Donc FAUX.
8)Je ne savais pas que l'ensemble vide était considéré comme un langage fini....En effet, l'intersection L L' sera comme L, pas d'états finis. Donc FAUX.

4-5-6

Imagine que tu as un nfa avec n états terminaux, peut-on rajouter une ɛ-transition de ces états terminaux vers un nouvel unique état terminal ?

Oui. Et il est bien déterministe donc 4) VRAI?
5)VRAI également, si on peut la 4) on peut la 5).
6)epsilon-transition j'ai vraiment du mal....

[kwariz]

Vraiment top je trouve.

Oui, les débuts sont faciles, ensuite on essaye de faire des choses plus complexes et ça se corse ... il y a une courbe d'apprentissage assez coton. Mais au final rendu est bon. Il y a aussi des GUI pour créer les images, question de goût ensuite.

Merci Plus simple pour les conjugaisons.
1 et 2 ok, c'est bien ce que j'avais compris.

Prenons L={a+b+}, L'={anbn, n>0} en est-il un sous-ensemble ? L' est-il un langage d'états finis ?

3) Oui. Non car il n'existe aucun dfa qui reconnaisse l'ensemble des mots contenant autant de a que de b.Donc FAUX.Mais L n'est pas d'états finis non?

Si si ...

(toute expression régulière définit un langage à états finis ...)
Les mots de L sont ceux composés d'un certain nombre non nul de a suivi d'un certain nombre non nul de b, avec le nombre de a et de b non forcément identiques. Les mots de L' sont ceux qui ont le même nombre non nul de a et de b tels que tous les a précédent les b.

Ah oui d'accord...Que c'est bien vu... Oui s'il n'est pas complet ça change quelque chose car si par exemple pour un langage {a,b} , on a dès l'état initial aucune boucle avec b (et a allant à l'état 2) ,tout mot commençant par b ne sera pas accepté. Donc FAUX.

J'en profite pour préciser que la technique du complément utilisée pour ta première question ne fonctionne que parce que le dfa est complet. S'il ne l'avait pas été on aurait du d'abord le rendre complet.

8)Je ne savais pas que l'ensemble vide était considéré comme un langage fini....En effet, l'intersection L L' sera comme L, pas d'états finis. Donc FAUX.

C'est le langage vide L={}. Si cela pose un problème de compréhension tu peux reprendre L={aⁿbⁿ} et L'={ε}.

4-5-6
Oui. Et il est bien déterministe donc 4) VRAI?
5)VRAI également, si on peut la 4) on peut la 5).
6)epsilon-transition j'ai vraiment du mal....

Bah c'est là que mes souvenirs et mon vocabulaire font défaut ... je t'encourage à vérifier mes propos dans ton cours. L'idée pour n'obtenir qu'un seul état terminal et de rajouter des transitions entre les anciens états terminaux et l'unique nouveau. Si tu peux rajouter une transition "fin de mot" des anciens vers le nouveau alors le tour est joué. De souvenirs (et ils ne sont pas récents) une ε-transition peut se prendre n'importe quand sans consommer un symbole donc ça ne convient pas trop, sauf dans le cas non déterministe (et encore je n'en suis pas sûr). Je pense que tu dois avoir des pistes dans ton cours, et ça m'intéresserait de connaître la fin mot de l'histoire.

[magodeoz]

Très bien
Donc pour résumer:
1)FAUX, contre-exemple L={les mots ayant un nombre pair de 0}.
2)VRAI,vrai, le langage est fini L={w0, w1, ..., wn}, donc on peut construire le dfa qui va accepter w1 ou w2 ou ... ou wn
3)FAUX car il n'existe aucun dfa qui reconnaisse l'ensemble des mots contenant autant de a que de b.
4)FAUX, l'exercice précédent.
5)FAUX,on peut avoir plusieurs états accepteurs.
6)VRAI.
7)FAUX si l'automate n'est pas complet.
8)FAUX,en prenant L' l'ensemble vide, l'intersection L et L' ne sera pas d'états finis.

Petite question, on est d'accord que si j'ai des epsilon transition l'automate n'est pas déterministe n'est ce pas?

Pour les epsilon transitions oui on crée un nouvel état accepteur et les anciens accepteurs ne le sont plus et on a une epsilon-transition entre chacun et le nouvel état final.

[kwariz]

Très bien
Donc pour résumer:
1)FAUX, contre-exemple L={les mots ayant un nombre pair de 0}.
2)VRAI,vrai, le langage est fini L={w0, w1, ..., wn}, donc on peut construire le dfa qui va accepter w1 ou w2 ou ... ou wn
3)FAUX car il n'existe aucun dfa qui reconnaisse l'ensemble des mots contenant autant de a que de b.
4)FAUX, l'exercice précédent.
5)FAUX,on peut avoir plusieurs états accepteurs.
6)VRAI.
7)FAUX si l'automate n'est pas complet.
8)FAUX,en prenant L' l'ensemble vide, l'intersection L et L' ne sera pas d'états finis.

Je ne relis pas ... je te fais confiance

Petite question, on est d'accord que si j'ai des epsilon transition l'automate n'est pas déterministe n'est ce pas?

Oui s'il y a une epsilon transition alors l'automate n'est plus déterministe.

Pour les epsilon transitions oui on crée un nouvel état accepteur et les anciens accepteurs ne le sont plus et on a une epsilon-transition entre chacun et le nouvel état final.

Oui c'est ça.

[magodeoz]

Merci pour tout kwariz! Je te souhaite une bonne fin de week-end.