Automate fini déterministe (AFD)
Résolu/Fermé
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
-
29 mars 2008 à 20:41
anissa - 22 févr. 2012 à 11:01
anissa - 22 févr. 2012 à 11:01
A voir également:
- Automate fini déterministe (AFD)
- Télécharger logiciel automate programmable gratuit - Télécharger - Émulation & Virtualisation
- Netflix : fini le partage de compte - Guide
- Ticket carton fini - Guide
- Bit de vie automate - Forum Programmation
- Uptobox fini - Guide
30 réponses
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
30 mars 2008 à 20:42
30 mars 2008 à 20:42
"Pas marché"
C'est à dire?
M.
C'est à dire?
M.
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
30 mars 2008 à 19:10
30 mars 2008 à 19:10
Je ne sais pas les symboles possibles on prendra { a, b, c }.
Un automate qui reconnaît les mots commençant par a. Soit l'expression a( a v b v c )*.
L'automate t'es sûrement donné, moi j'ai pris un état A pour exclure le mot vide, B qui reconnaît les a et C qui reconnaît tout le reste du mot.
Si tu n'en est pas encore aux structures on va éviter car il faudra y mettre aussi les pointeurs.
Dans l'idée la structure ressemblait à ça:
On remarquera que pour faire un programme qui reconnaît les mot qui commencent par 'a' il y a franchement plus simple, ici j'ai appliqué le principe général qui permettrait de faire n'importe quel automate.
M.
Un automate qui reconnaît les mots commençant par a. Soit l'expression a( a v b v c )*.
L'automate t'es sûrement donné, moi j'ai pris un état A pour exclure le mot vide, B qui reconnaît les a et C qui reconnaît tout le reste du mot.
#include <stdio.h> #include <stdlib.h> #include <string.h> /* | a | b | c -------------- A | B | 0 | 0 B | B | C | C C | C | C | C A:initial C:final */ unsigned char A ( char *mot, unsigned int taille ); unsigned char B ( char *mot, unsigned int taille ); unsigned char C ( char *mot, unsigned int taille ); unsigned char A ( char *mot, unsigned int taille ) { if ( taille > 0 ) { if ( *mot == 'a' ) return B( mot+1, taille-1 ); else return 0; // Puits ou non reconnu. } else return 0; // A n'est pas un état final. } unsigned char B ( char *mot, unsigned int taille ) { if ( taille > 0 ) { if ( *mot == 'a' ) return B( mot+1, taille-1 ); else if ( ( *mot == 'b' ) || ( *mot == 'c' ) ) return C( mot+1, taille-1 ); else return 0; // symbole inconnu. } else return 0; // B n'est pas un état final. } unsigned char C ( char *mot, unsigned int taille ) { if ( taille > 0 ) { if ( ( *mot == 'a' ) || ( *mot == 'b' ) || ( *mot == 'c' ) ) return C( mot+1, taille-1 ); else return 0; // symbole non reconnu. } else return 1; // LE mot est lu entièrement et C est un état final. } int main() { char *unMot = "aabaca"; if ( A( unMot, (unsigned int) strlen( unMot ) ) == 1 ) printf( "Reconnu.\n" ); else printf( "Non reconnu.\n" ); }
Si tu n'en est pas encore aux structures on va éviter car il faudra y mettre aussi les pointeurs.
Dans l'idée la structure ressemblait à ça:
char g_acSymboles[] = { 'a', 'b', 'c' }; typedef struct Etat_t { struct Etat_t *apEtatsSuivants[ sizeof( g_acSymboles ) ]; unsigned int uProprietees; // (INITIAL, FINAL, PUITS) } Etat;
On remarquera que pour faire un programme qui reconnaît les mot qui commencent par 'a' il y a franchement plus simple, ici j'ai appliqué le principe général qui permettrait de faire n'importe quel automate.
M.
nilly
Messages postés
154
Date d'inscription
samedi 26 janvier 2008
Statut
Membre
Dernière intervention
25 octobre 2012
5
30 mars 2008 à 22:45
30 mars 2008 à 22:45
salut
tu te débrouille bien en C
mais ton programme marche pour un seul automate pas pour n'importe le quel .
tu te débrouille bien en C
mais ton programme marche pour un seul automate pas pour n'importe le quel .
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 00:44
30 mars 2008 à 00:44
j ai pas bien compriss
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 00:47
30 mars 2008 à 00:47
ou bien cmt faire une table de transition ???
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
30 mars 2008 à 12:51
30 mars 2008 à 12:51
C'est une table à deux dimensions: Etat de départ / Alphabet
Les états: { A, B, C, D, E } avec A initial et F final (et 0 l'état puis)
L'alphabet: (c'est comme ça qu'on dit?) { a, b }
Voilà, avec une table j'ai décrit un automate. On peut représenter l'automate avec une table de transition car il est déterministe. (Sinon il faudrait pouvoir mettre plusieurs états d'arrivée dans chaque case.
On sait donc maintenant qu'à partir de l'état A on arrive en B par a et en F par b. etc
Mon automate reconnait (ba*) v ( aa ( aa* v bba* ) )
On prend un mot aabbaa. Est-il reconnu par l'automate?
On part de l'état initial.
1erè lettre du mot = a
Avec a où va-t-on? -> en B.
2ème lettre = a
A partir de B où va-t-on avec a? -> en C.
3ème lettre = b.
A partir de C où va-t-on avec b. -> en D.
4ème lettre = a.
A partir de D où va-t-on avec a. -> en 0. état puis.
Le mot n'est pas reconnu par notre automate.
Autre solution plus simple mais plus figée. Elle est directement issue de la mise en BNF.
Chaque état est représenté par une fonction qui renvoie 1 en cas de succès et 0 en cas d'échec.
Seul l'état final renvoie 1 lorsque la taille du mot est 0. C'est que l'automate a pu consommer tout le mot.
A noter qu'on pourrait dans cette deuxième solution quand même avoir une table de transition et chaque fonction irait lire la ligne qui lui correspond et faire son analyse à partir d'un boucle plutôt que d'écrire à la main chaque cas. On remarquera ensuite que les fonctions des états se ressemblent et on pourra faire des structure contenant les transitions. On arrivera alors à une sorte de programmation descriptive et ce sera le pied!
M.
Les états: { A, B, C, D, E } avec A initial et F final (et 0 l'état puis)
L'alphabet: (c'est comme ça qu'on dit?) { a, b }
| a | b ---------- A | B | F B | C | 0 C | F | D D | 0 | F F | F | 0
Voilà, avec une table j'ai décrit un automate. On peut représenter l'automate avec une table de transition car il est déterministe. (Sinon il faudrait pouvoir mettre plusieurs états d'arrivée dans chaque case.
On sait donc maintenant qu'à partir de l'état A on arrive en B par a et en F par b. etc
Mon automate reconnait (ba*) v ( aa ( aa* v bba* ) )
On prend un mot aabbaa. Est-il reconnu par l'automate?
On part de l'état initial.
1erè lettre du mot = a
Avec a où va-t-on? -> en B.
2ème lettre = a
A partir de B où va-t-on avec a? -> en C.
3ème lettre = b.
A partir de C où va-t-on avec b. -> en D.
4ème lettre = a.
A partir de D où va-t-on avec a. -> en 0. état puis.
Le mot n'est pas reconnu par notre automate.
Autre solution plus simple mais plus figée. Elle est directement issue de la mise en BNF.
Chaque état est représenté par une fonction qui renvoie 1 en cas de succès et 0 en cas d'échec.
unsigned char A ( char *mot, unsigned int taille ) { if ( taille > 0 ) // A est non final { if ( *mot == 'a' ) return B( mot + 1, taille - 1 ); else if ( *mot == 'b' ) return F( mot + 1, taille - 1 ); else return 0; // La lettre est inconnue. } else { return 0; // Fin du mot et A n'est pas un état final. } } int main() { return A( "aabbaa", 6 ); }
Seul l'état final renvoie 1 lorsque la taille du mot est 0. C'est que l'automate a pu consommer tout le mot.
A noter qu'on pourrait dans cette deuxième solution quand même avoir une table de transition et chaque fonction irait lire la ligne qui lui correspond et faire son analyse à partir d'un boucle plutôt que d'écrire à la main chaque cas. On remarquera ensuite que les fonctions des états se ressemblent et on pourra faire des structure contenant les transitions. On arrivera alors à une sorte de programmation descriptive et ce sera le pied!
M.
slt, merci pour ta reponse mais tu peut me dir si on peut definir des structure pour les etat et aussi pour le transition.merci bcp pour votre intension.
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
30 mars 2008 à 13:59
30 mars 2008 à 13:59
Je pense qu'avec une structure ça peut suffire.
L'état qui éventuellement peut contenir son nom complet mais surtout une mini table de transition. Juste la ligne qui se rapporte à l'état représenté par la structure. Globalement je vois ça comme un tableau de N pointeurs vers des états où N est la taille de l'alphabet.
Ainsi une fonction qui doit analyser un mot regarde dans son état courant à quoi correspond la lettre en cours dans la mini table de transition et se rappelle elle même avec le nouvel état en avançant dans le mot. La structure de l'état doit aussi dire si un état est final ou non.
Le but des structures serait de définir une macro simple pour déclarer les états et de n'avoir que cela à modifier pour faire un programme avec un autre automate sans ré-écrire les fonctions pour chaque état.
(En passant il existe aussi des programmes qui génèrent des programmes reconnaissant des automates à partir d'une sorte de BNF. On avait fait une sorte de compilateur d'un mini langage C en bytecodes Java avec ça)
Le but des structure c'est de finir avec un qui ressemble à ça.
(Une étape supplémentaire encore peut être de remplacer le .h par un fichier texte qui servirait à décrire l'automate qui serait chargé en début de programme, mais c'est un poil plus chiant à faire.)
M.
L'état qui éventuellement peut contenir son nom complet mais surtout une mini table de transition. Juste la ligne qui se rapporte à l'état représenté par la structure. Globalement je vois ça comme un tableau de N pointeurs vers des états où N est la taille de l'alphabet.
Ainsi une fonction qui doit analyser un mot regarde dans son état courant à quoi correspond la lettre en cours dans la mini table de transition et se rappelle elle même avec le nouvel état en avançant dans le mot. La structure de l'état doit aussi dire si un état est final ou non.
Le but des structures serait de définir une macro simple pour déclarer les états et de n'avoir que cela à modifier pour faire un programme avec un autre automate sans ré-écrire les fonctions pour chaque état.
(En passant il existe aussi des programmes qui génèrent des programmes reconnaissant des automates à partir d'une sorte de BNF. On avait fait une sorte de compilateur d'un mini langage C en bytecodes Java avec ça)
Le but des structure c'est de finir avec un qui ressemble à ça.
DEBUT_ALPHABET LETTRE( 'a' ) LETTRE( 'b' ) FIN_ALPHABET DECLARE_ETAT( PUITS ); DECLARE_ETAT( A ); DECLARE_ETAT( B ); DECLARE_ETAT( C ); DECLARE_ETAT( D ); DECLARE_ETAT( F ); DEFINE_ETAT( PUITS, 0, { PUITS, PUITS } ); DEFINE_ETAT( A, INITIAL, { B, F } ); DEFINE_ETAT( B, 0, { C, PUITS } ); ... DEFINE_ETAT( B, FINAL, { F, PUITS } );
(Une étape supplémentaire encore peut être de remplacer le .h par un fichier texte qui servirait à décrire l'automate qui serait chargé en début de programme, mais c'est un poil plus chiant à faire.)
M.
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
30 mars 2008 à 20:48
30 mars 2008 à 20:48
La fenêtre se ferme tout de suite peut-être. Mets #include <conio.h> au début et getch(); en bas du main.
M.
M.
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
29 mars 2008 à 20:43
29 mars 2008 à 20:43
en language c svp
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
29 mars 2008 à 20:50
29 mars 2008 à 20:50
Bonsoir,
Avec un AFD c'est quand pas trop trop compliqué, il n'y a qu'à regarder si le mot "rentre dans les cases" sachant qu'il n'y a aucune ambiguïté.
Ce serait à moi de faire l'exercice je ferais une table de transition pour représenter l'automate. Ensuite toutes les petites fonctions qui vont bien. Sinon ça peut se faire en construisant des états et en les reliant pour reconstruire l'automate mais ça me parait plus laborieux et moins évolutifs.
Quel est le souci au juste ?
M.
Avec un AFD c'est quand pas trop trop compliqué, il n'y a qu'à regarder si le mot "rentre dans les cases" sachant qu'il n'y a aucune ambiguïté.
Ce serait à moi de faire l'exercice je ferais une table de transition pour représenter l'automate. Ensuite toutes les petites fonctions qui vont bien. Sinon ça peut se faire en construisant des états et en les reliant pour reconstruire l'automate mais ça me parait plus laborieux et moins évolutifs.
Quel est le souci au juste ?
M.
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 15:44
30 mars 2008 à 15:44
c un peu dificile a comprendre j ai pas tro sasie mai bon c mieu merci
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
30 mars 2008 à 17:25
30 mars 2008 à 17:25
Si l'automate n'a pas besoin d'être changé, la version où chaque état définit une fonction est la plus simple et la plus rapide.
A quel moment ça coince ? La première version en plusieurs fonction est ok ? C'est comment la passer en une fonction avec des structures ?
M.
A quel moment ça coince ? La première version en plusieurs fonction est ok ? C'est comment la passer en une fonction avec des structures ?
M.
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 17:29
30 mars 2008 à 17:29
l automte ici kan veu faire c est par example automate des mots qui commencent par 'a' j ai pu faire une fonction poyur sa c été facile mais un automate c est pa la mm chose ??
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 17:34
30 mars 2008 à 17:34
moi j ai jamai étudié les structure
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 18:04
30 mars 2008 à 18:04
ce programme precedant c en java moi je veu en c
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 19:44
30 mars 2008 à 19:44
don on peu faire un automate deterministe qui indique est ce que un mot W est accépté par M={E,A,T,i,F} quekl ke soi les mot ki commence par a ou par b ou un mot de longueur paire ou qui commence par a et termine par b ?sur un alphavbet {a,b}seulement
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
30 mars 2008 à 20:17
30 mars 2008 à 20:17
Techniquement oui c'est possible.
Pour les nombres pairs de lettres cela complique énormément la vie des structures. Elles sont biens pratiques pour les automates basiques car on en vient à ne plus définir que les données sans retoucher au code réellement. Ici il vaut mieux faire avec des fonctions qui ne représentent plus vraiment un état mais une *** (J'ai oublié le terme ^^) de la BNF. (un "prédicat" ?) Chaque ligne de la BNF définit une fonction.
M.
Pour les nombres pairs de lettres cela complique énormément la vie des structures. Elles sont biens pratiques pour les automates basiques car on en vient à ne plus définir que les données sans retoucher au code réellement. Ici il vaut mieux faire avec des fonctions qui ne représentent plus vraiment un état mais une *** (J'ai oublié le terme ^^) de la BNF. (un "prédicat" ?) Chaque ligne de la BNF définit une fonction.
M.
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 20:20
30 mars 2008 à 20:20
le programme precedant ke ta ecri sa pa marchéé
shevalier11323
Messages postés
13
Date d'inscription
samedi 29 mars 2008
Statut
Membre
Dernière intervention
30 mars 2008
2
30 mars 2008 à 20:44
30 mars 2008 à 20:44
je l ai appliké je voi k il a pas donner de resultat d execution