Automate à pile - Définition
La liste des auteurs de cet article est disponible ici.
Exemples
Reconnaissance du langage
On peut utiliser l'automate
où les transitions sont définies par :
(1)
(2)
(3)
(4)
(5)
(6)
(7)
Par exemple, dans l'état
On commence par lire le premier caractère : Si le mot est vide on a fini et le mot est accepté car q0 est un état final. Si c'est un a, on empile
Ensuite dans l'état q1, à chaque a on empile A (2). Si on a un b, deux possibilités : - Si on n'a empilé qu'un seul
Dans l'état q2, si on a un b, soit on dépile un A et on reste dans cet état (5), soit on dépile un
Dans l'état q3, si le mot est fini on l'accepte car
Implémentation d'un automate à pile
En langage C :
-
#include -
#include -
-
#define POP -1 -
#define ACCEPT -2 -
#define ERROR -3 -
-
#define ALPHABET 3 /* Grandeur*/ -
-
/* -
Push-down automation) -
-
Symbol | ( | ) | \0 -
---------+---------+--------+----------- -
State 0 | PUSH 1 | ERROR | ACCEPT -
State 1 | PUSH 1 | POP | ERROR -
*/ -
-
int states[2][ALPHABET*2] =
-
{ -
{ -
'(', 1 /* PUSH 1 */,
-
')', ERROR,
-
'\0', ACCEPT
-
},
-
{ -
'(', 1 /* PUSH 1 */,
-
')', POP,
-
'\0', ERROR
-
} -
};
-
-
-
int main( int argc, char** argv )
-
{ -
int stack[100] = { 0 };
-
int i = 0;
-
int action = 0;
-
int* tos = stack;
-
char s [80+1];
-
char* p = s;
-
-
/* Chaine de donnée */ -
printf("Entrez l'expression: ");
-
gets( &s );
-
-
/*Pile poussée*/ -
*(tos++) = 0;
-
-
/* Sortie */ -
do -
{ -
/* Boucle*/ -
action = ERROR;
-
for( i = 0; i < ALPHABET; i++ )
-
{ -
if( states[*(tos-1)][i*2] == *p )
-
{ -
action = states[*(tos-1)][i*2+1];
-
break;
-
} -
} -
-
/* Actions*/ -
if( action == ERROR )
-
{ -
printf("Erreur inattendue à la position %d", p-s);
-
break;
-
} -
else if( action == ACCEPT )
-
printf("Sortie acceptée!");
-
else if( action == POP )
-
tos--; -
else -
*(tos++) = action;
-
-
/* Données supplémentaires... */ -
p++; -
} -
while( action != ACCEPT );
-
-
getchar();
-
return 0;
-
}
