Déterminiser Minimiser un automate
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
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
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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... :-(
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
À 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.
j en arrive au résultat (voir fichier joint)
merci
Voici ma question, merci pour vos réponses :
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.
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
Pouvez-vous m'envoyer un lien de téléchargement ?