automate fini déterministe (AFD) Résolu

Question

Bonjour,
svp j ai pas pu faire un programme pour d' AFD qui détermine est ce que un mot W appartient a un alphabet A donné vs pouvé m aider svp  merci d avance

Mahmah · Accepted Answer

"Pas marché"

C'est à dire?

M.

shevalier11323 · Answer

en language c svp

Mahmah · Answer

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.

shevalier11323 · Answer

j ai pas bien compriss

shevalier11323 · Answer

ou bien cmt faire une table de transition ???

Mahmah · Answer

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 }


  | 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.

forever · Answer

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 · Answer

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.

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.

shevalier11323 · Answer

c un peu dificile a comprendre j ai pas tro sasie mai bon c mieu merci

Mahmah · Answer

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.

shevalier11323 · Answer

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 · Answer

moi j ai jamai étudié les structure

shevalier11323 · Answer

ce programme precedant c en java moi je veu en c

Mahmah · Answer

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. #include #include #include /* | 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. " ); else printf( "Non reconnu. " ); } 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.

shevalier11323 · Answer

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 · Answer

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.

shevalier11323 · Answer

le programme precedant ke ta ecri sa pa marchéé

shevalier11323 · Answer

je l ai appliké je voi k il a pas donner de resultat d execution

Mahmah · Answer

La fenêtre se ferme tout de suite peut-être. Mets #include <conio.h> au début et getch(); en bas du main.

M.

shevalier11323 · Answer

sa marche wéé mai je doi changer le mot dans le programme cmt faire pour donner un mot ds la page d execution

Mahmah · Answer

int main()
{
	char unMot[2048];

	printf( "Entrez un mot:
" );
	scanf( "%s", unMot );
	printf( "
" );

	if ( A( unMot, (unsigned int) strlen( unMot ) ) == 1 )
		printf( "Reconnu.
" );
	else
		printf( "Non reconnu.
" );

	getch();
}

C'est juste du C ça...
M.

nilly · Answer

salut
tu te débrouille bien en C 
mais ton programme marche pour un seul automate pas pour n'importe le quel .

Mahmah · Answer

Je veux bien la solution universelle.

M.

shevalier11323 · Answer

ouai pour un seul automate

lami20j · Answer

Salut,

voici un exemple complet en C recherche de motif dans un texte

Mahmah · Answer

Bonjour,

Cela paraît être une bonne solution mais elle ne marche toujours pas pour tout automate.

Je continue à prétendre que pour un automate donné (comme cela avait l'air d'être le cas) il vaut mieux avoir un programme spécifique. Je pense bien que personne ne se serait cassé à faire des générateurs de code pour obtenir des programmes qui traitent des automates donnés si c'était si inadapté. J'en conviens pour faire des recherches dans un éditeur comme Word c'est pas top... mais l'automate n'est pas fixe dans ce dernier cas.

Sinon il n'y a pas à prendre une demi solution qui recherche un bloc dans un texte, autant sortir les expressions régulières et basta.

M.

lami20j · Answer

Salut,

autant sortir les expressions régulières et basta. 
effectivement ;-))

Mahmah · Answer

Je m'y colle pas.

Simplement par curiosité, c'est quoi l'algo conseillé ?
(A la fac on nous avait fait faire par back-tracking... C'est bien mignon mais on aurait vite fait d'éclater sa pile avec ce type de joujous ^^")

M.

waoumita · Answer

salut tt le monde j'ai un exo  en informatique theorique   mais je ne sais pa cmt trouver cet automate 
voila la question
donner un AFD qui reconnait les entiers positifs en base 2   multiples de   5 
merci pour l'aide

anissa · Answer

s'il vous plais qui peut me donner une idée comment programmer en java un automate qui teste s'il est deterministe ou nn ??

Automate fini déterministe (AFD) - Page 2

Discussions similaires

Newsletters