(pour signaler une erreur monnerat@u-pec.fr)

Implanatation d'automates Finis

On rappelle qu'un automate fini déterministe (AFD) \(A=(X,Q,q_0,F,\delta)\) est caractérisé par

• \(X\) : l'alphabet de symboles reconnus.
• \(Q\) : l'ensemble fini d'états.
• \(q_0\in Q\) l'état initial.
• \(F\subset Q\) l'ensemble des états terminaux ou acceptants .
• \(\delta : Q\times X \longrightarrow Q\) : la fonction de transition.

Tous les programmes sont à écrire en C.

Codage de l'AFD comme instructions du programme

C’est une démarche qu’on peut suivre lorsqu’on a un petit automate immuable.

• L'automate est "une boucle".
• Chaque état est représenté par une étiquette.
• Les transitions sont transcrites par des branchements conditionnels à l'aide de l'instruction goto.

#include<stdio.h>
#define ENTER '\n'
int main(){
	while(1){
		int c;
 
q0: // etat initial !
		c=getchar();
		switch(c){
			case 'a' : goto q1;
					   break; // break inutile !
 
			case 'b' : goto q3;
 
			case ENTER : printf("OK\n"); // si q0 est acceptant !
						 return 0; 
 
			default : goto poubelle; 
		}
q1:
 
q2:
 
q3:
 
 
poubelle :
 
	}
}

1. Donner un AFD et le programme qui reconnaît le langage \((ab)^{*}\).
2. Donner un AFD et le programme qui accepte les mots écrits sur \(X=\{a,b\}\) formées d'une succession d'un nombre pairs de \(a\) entrecoupées d'un nombre quelconque de \(b\).
3. Donner un AFD et le programme qui accepte les mots écrits sur \(X=\{a,b\}\) se terminant par \(ab\) .
4. Donner un AFD et le programme qui accepte les mots écrits sur \(X=\{0,1\}\) représentant des entiers (binaires) multiples de \(5\) .

Codage de l'AFD comme données du programme

L'automate est représenté dans le programme à l'aide de variables. La partie qui simule l'exécution de l'automate est toujours la même quelque soit l'automate.

#define ENTER '\n'
#define NQ 6 /* nb  etats (Q)*/
#define NX 3 /* nb lettres (X)*/
 
 
/* codage de la table  de 
   transition
   */
 
int DELTA[NX][NQ] = {
	{...},/* transition sur la première lettre */
	{...},/* transition sur la deuxième lettre */
	/* -1 en cas d'absence de transition */
 
 
	{...}
};
 
/* codage des etats
 * acceptants (0 ou 1)
 * */
 
int QF[NQ] = { ....}; 
 
/* fonction de transition
 *  calcule l'état suivant
 *  */ 
 
int transition(
		int ec, /* etat courant*/
		char c, /* caractere   */
		int T[NX][NQ]
		){
 
}
 
 
int main(){
	int c;
	int q= ; /* etat initial */
	while(1){
 
		c=getchar();
		if (c!=ENTER && q>=0){
			q=transition(q,c,DELTA);
		}else break;
 
	}
	if (...) printf("OK\n");
	else printf("NOK\n");
 
}

Recoder toutes les automates de la partie précédente.