Pensez à lire la Charte avant de poster !
Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
119 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Déterminiser Minimiser un automate

Envoyé par labaraka 
Déterminiser Minimiser un automate
il y a cinq années
Bonsoir,

Je voulais savoir comment déterminer (ou iser) un automate fini ? Quelle est la technique ?
Comment calculer des résiduels ?
Quelle différence entre un automate fini non déterministe et déterministe ?
Qu'est ce un état co-accessible ?

Je vais ajouter un schéma afin que les choses soient plus claires
Merci



Edité 2 fois. La dernière correction date de il y a cinq années et a été effectuée par labaraka.
Re: Déterminiser Minimiser un automate
il y a cinq années
avatar
Bonjour,

De mémoire (mais ça remonte un peu) :

Un état co-accessible est un état à partir duquel on peut aller jusqu'à l'état final.
Un automate est dit déterministe si partant d'un état il n'y a qu'un seule flèche portant une étiquette donnée. Un automate non-déterministe est, comme son nom l'indique, un automate qui n'est pas déterministe.

Pour déterminiser un automate, il me semble qu'on regroupe les états. Par exemple, si d'un état $q$ on a deux flèches $q\xrightarrow{a}r$ et $q\xrightarrow{a}s$, dans le nouvel automate on aura un état noté $\{r,s\}$ et une flèche $q\xrightarrow{a}\{r,s\}$. De cet état partiront toutes les flèches qui partaient de $r$ ou de $s$. Ça doit être plus ou moins mécanique : on part de l'état initial, on applique cette opération, et pour chacun des états atteints depuis l'état initial on recommence. Ça termine forcément puisque les états du nouvel automate sont des parties de l'ensemble des états de l'ancien : si l'ancien avait $n$ états, le nouveau en aura au plus $2^n$.

Pour être plus précis, il faudrait que je retrouve mes cours d'informatique... sad smiley
Re: Déterminiser Minimiser un automate
il y a cinq années
avatar
Voilà quelques exemples. Il y a (1) un automate déterministe, (2) un non-déterministe, et (3) le déterminisé du (2).
[attachment 12348 1-dterministe.pdf]
[attachment 12349 2-non-dterministe.pdf]
[attachment 12350 3-dterminis.pdf]

Pour la construction du déterminisé, j'ai dressé un tableau :
\begin{tabular}{c|cccccc}
& \{0\} & \{1\} & \{2\} & \{1,2\} & \{0,1\} & \{0,1,2\} \\\hline
0 & & & b & b & & b \\
1 & a & a & b & a,b & a & a,b \\
2 & a & b & & b & a,b & b
\end{tabular}
On commence par mettre uniquement les trois premières colonnes, on les remplit avec les étiquettes des transitions. Ensuite on prends la première colonne ("\{0\}") et on voit qu'il faut créer un état \{1,2\}, donc on le rajoute à droite. Pour la colonne "\{1\}" pas de problème. Pour la suivante on voit qu'il faut créer un état \{0,1\}. Pour la suivante on voit qu'il faut créer un état \{0,1,2\}. Et ainsi de suite.

Petite précision : les états finaux du déterminisé sont les états qui contiennent l'état final de l'automate de départ. Dans l'exemple, si 2 était l'état final, alors les états finaux du déterminisé seront \{2\}, \{1,2\} et \{0,1,2\}.
Re: Déterminiser Minimiser un automate
il y a cinq années
salut

Tout d'abord je te remercie de tes réponses , cependant je ne vois pas quand s arreter et je suis un peu perdu quand l'automate est plus dense ,
voir exemple en fichier joint ,pourrais tu m'aider a la déterminiser :

En fait je débute par les états initiaux qui sont donc 1et 3.Mais après ça me pose un problème

merci
[attachment 12363 automate.JPG]


Re: Déterminiser Minimiser un automate
il y a cinq années
avatar
Bonjour,

À la réflexion, voici une version plus pratique de la ‹‹ méthode du tableau ››. On commence avec l'état initial du déterminisé, qui est \{1,3\} parce que les états initiaux de l'automate de départ sont 1 et 3. On commence par la première colonne du tableau :

\begin{tabular}{c|c}
& \{1,3\} \\\hline
a & \{3,5\} \\
b & \{3,5\}
\end{tabular}

En effet, en partant de 1 ou de 3 et en lisant 'a', on peut arriver en 3 et en 5 (et c'est tout). Idem en lisant 'b'.
Du coup, on rajoute une colonne \{3,5\} :
\begin{tabular}{c|cc}
& \{1,3\} & \{3,5\} \\\hline
a & \{3,5\} & \{3\} \\
b & \{3,5\} & \{5,4\}
\end{tabular}
donc on va créer de nouvelles colonnes nommées \{3\} et \{5,4\}. Et on continue comme ça jusqu'à ce qu'on arrive à un moment où on n'aura plus besoin de créer d'états. Je te laisse continuer, même pour des automates ‹‹ plus denses ›› ce n'est pas compliqué, il suffit d'y aller minutieusement.
Re: Déterminiser Minimiser un automate
il y a cinq années
salut badwolf , merci pour ces détails utiles

j en arrive au résultat (voir fichier joint)

merci
[attachment 12373 automatedeterministe.JPG]


Re: Déterminiser Minimiser un automate
il y a cinq années
avatar
J'obtiens le même résultat.
Re: Déterminiser Minimiser un automate
il y a trois années
Bonjour,

Voici ma question, merci pour vos réponses :

[attachment 18294 Question_automate1.jpg]


Anonymous
Re: Déterminiser Minimiser un automate
il y a trois années
Ces deux automates reconnaissent exactement le même langage.

La seule différence est que le premier est dit "complet". En effet, tous les états possèdent une transition pour chacune des lettres de l'alphabet (ici : {a,b}).
L'état supplémentaire est une sorte d'état "poubelle" recevant tous les mots qui ne peuvent plus être acceptés. L'automate continue la lecture jusqu'à la fin du mot.
@ BadWolf :

Pour la dernière case en bas à droite du tableau (1er tableau), si j'ai bien compris la logique du tableau, ca devrait pas plutôt être a,b ? Et ma proposition me semble être validée par le pdf joint dans le message :)

En tout cas merci beaucoup BadWolf pour cette explication. Elle est franchement bien faite
Auteur:

Votre adresse électronique:


Sujet:


Mesure anti-SPAM :
Recopiez le code que vous voyez dans le champ ci-dessous. Cette mesure sert à bloquer les robots informatiques qui tentent de polluer ce site.
 **    **  **    **        **   ******   **     ** 
 ***   **  ***   **        **  **    **  **     ** 
 ****  **  ****  **        **  **        **     ** 
 ** ** **  ** ** **        **  **        **     ** 
 **  ****  **  ****  **    **  **         **   **  
 **   ***  **   ***  **    **  **    **    ** **   
 **    **  **    **   ******    ******      ***    
Message:
A lire avant de poster!
Liste des forums - Statistiques du forum

Total
Discussions: 99 893, Messages: 918 011, Utilisateurs: 10 484.
Notre dernier utilisateur inscrit nolhandupuy.


Ce forum
Discussions: 1 456, Messages: 10 290.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page
Autres...