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

Implanatation d'automates Finis (non)déterministes par un système d'équations booléennes.

L'idée est de représenter les transitions d'un automate par des équations booléennes. On associe à chaque état une variable booléenne. Les évolutions possibles de l'automate sont obtenus en mettant à jour ces variables, grâce à des équations traduisant les transitions permises.

On a trois variables \((x_0,x_1,x_2)\).

$$\left\{\begin{array}{ccc} x_0 &:= &(x_0 \land car = a) \lor (x_1 \land car = b)\\ x_1 &:= &(x_0 \land car = b) \lor (x_2 \land car = b)\\ x_2 & := & x_0 \land car = a \end{array}\right. $$

La variable car représente le symbole lu. On met alors à jour les variables booléennes avec ces équations. A chaque étape, les valeurs des variables représentent tous les états accéssibles depuis le début.

1. Comment initialise-t-on les variables ?
2. Comment sait-on qu'un mot est reconnu ?

• Dans l'exemple, la valeur des variables initialement est \((1,0,0)\). Pourquoi ?
• Si on lit un a, on obtient \((1,0,1)\). Pourquoi ?
• Si on continue avec b, on obtient \((0,1,0\)). Le mot \(ab\) est-il accepté ?

Implantation

Soient les deux automates sur \(X=\{a,b\}\) qui reconnaissent respectivement \(L_1\) les mots avec un nombre pair de \(a\) et \(L_2\) les mots avec un nombre impair de \(b\).

On va implanter un automate qui reconnaît \(L_1\cup L_2\).

#include<stdio.h>
#define ENTER '\n' 
#define N 4
 
int estAccepte(int etat[N],int etatA[N]){
	int i;
	for (i=0;i<N;i++){
		if (etat[i]&&etatA[i]) return 1;
	}
	return 0;
}
int main(){
	int etat[2][N]={0}; // 2 vecteurs de variables pour la mise à jour
	int etatA[N] = {1,0,0,1}; // etats acceptants
	int car; // caractere lu
	int tour=0;  
 
	//  Initialisation
 
	etat[tour][0]=1;
	etat[tour][2]=1;
 
	while(1){
		car=getchar();
		if (car == ENTER) break;
		tour=!tour;
 
		//Equations
 
		etat[tour][0] = (etat[!tour][0] && car == 'b') 
			|| (etat[!tour][1] && car == 'a');
		etat[tour][1] = (etat[!tour][0] && car == 'a') 
			|| (etat[!tour][1] && car == 'b');
		etat[tour][2] = (etat[!tour][2] && car == 'a') 
			|| (etat[!tour][3] && car == 'b');
		etat[tour][3] = (etat[!tour][2] && car == 'b') 
			|| (etat[!tour][3] && car == 'a');
 
	}
 
	if (estAccepte(etat[tour],etatA))
		printf("OK\n");
	else
		printf("NOK\n");
}

Remarque : la variable tour permet de mettre à jour les variables booléennes avec leurs valeurs précédentes. On a donc besoin de 2 exemplaires de chaque variable, stockées dans \(etat[2][N]\).

Votre travail

Donnez un automate (non déterministe) qui reconnaît les nombres décimaux à virgule, et implantez-le comme ci-dessus.

• Le nombre peut commencer par \(+\) ou \(-\).
• Pas de séquence inutile de \(0\) au début ou à la fin du nombre.