eBabylone
.com

ébauche|mathématiques Un automate à pile est une machine abstraite utilisée en informatique théorique et, plus précisément, en théorie des automates. Un automate à pile est semblable à un automate fini non-déterministe mais il dispose également d'une pile qui peut être utilisée pour stocker des informations pertinentes. La puissance de calcul des automates à piles correspond aux langages non-contextuels soit ceux qui peuvent être décrits par une grammaire hors-contexte.

Utilisation

Les automates à pile utilisent une zone de mémoire organisée en pile, qui permet de sauver des informations.
Le choix d'une transition peut dépendre de la valeur au sommet de la pile (pop)
Une transition peut entraîner un ou plusieurs empilements (push).

Définitions formelles

Un automate à pile est un 7-uplet $(E,\backslash Sigma,\backslash Phi,F,\backslash omega,i,T)\backslash underline\{\}$, où
$E\backslash underline\{\}$ est l'ensemble d'états,
$\backslash Sigma\backslash underline\{\}$ est l'alphabet d'entrée,
$\backslash Phi\backslash underline\{\}$ est l'alphabet de pile,
$F\; :\; E\backslash times(\backslash Sigma\backslash cup\; \backslash \{\; \backslash epsilon\; \backslash \})\; \backslash times\; (\; \backslash Phi\; \backslash cup\; \backslash \{\; \backslash epsilon\; \backslash \}\; )\; \backslash rightarrow\; P(E\backslash times\backslash Phi^$
) est la relation de transition,
$\backslash omega\backslash underline\{\}$ est le symbole de pile vide,
$i\backslash in\; E$ est l'état initial,
$T\; \backslash subset\; E$ est l'ensemble des états terminaux.

Exemples

Reconnaissance du langage $\backslash \{a^kb^k\; |\; k\; \backslash ge\; 0\; \backslash \}$ On peut utiliser l'automate $M\; =\; (\backslash \{q\_0,\; q\_1,\; q\_2,\; q\_3\backslash \},\; \backslash ,\; \backslash \backslash \},\; \backslash delta,\; \backslash omega,\; q\_0,\; \backslash \{q\_0,\; q\_3\backslash \}\; ),$ où les transitions sont définies par : $\backslash delta(q\_0,\; a,\; \backslash epsilon)\; =\; \backslash \{(q\_1,\; \backslash underline)\backslash \}$ $\backslash delta(q\_1,\; a,\; \backslash epsilon)\; =\; \backslash \{(q\_1,\; A)\backslash \}\backslash underline\{\}$ $\backslash delta(q\_1,\; b,\; A)\; =\; \backslash \{(q\_2,\; \backslash epsilon)\backslash \}\backslash underline\{\}$ $\backslash delta(q\_1,\; b,\; \backslash underline)\; =\; \backslash \{(q\_3,\; \backslash epsilon)\backslash \}$ $\backslash delta(q\_2,\; b,\; A)\; =\; \backslash \{(q\_2,\; \backslash epsilon)\backslash \}\backslash underline\{\}$ $\backslash delta(q\_2,\; b,\; \backslash underline)\; =\; \backslash \{(q\_3,\; \backslash epsilon)\backslash \}$ $\backslash delta(q,\; \backslash theta,\; \backslash rho)\; =\; \backslash empty$ pour les autres valeurs de $(q,\; \backslash theta,\; \backslash rho)\backslash underline\{\}$ Par exemple, dans l'état $q\_1\backslash underline\{\}$, si on lit un $b\backslash underline\{\}$ et que l'on dépile un $A\backslash underline\{\}$, on passe dans l'état $q\_2\backslash underline\{\}$ sans rien empiler.

Implémentation d'un automate à pile

#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 innatendue à 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;
}

Image:Automateapile.png

Voir aussi

Hiérarchie de Chomsky Multi bandeau|Portail mathématiques|portail informatique Catégorie:Langage formel Catégorie:Calculabilité ar:????????? ??? ??????? ?? ?????? bs:Potisni automat cs:Zásobníkový automat de:Kellerautomat en:Pushdown automaton es:Autómata con pila fi:Pinoautomaatti he:?????? ?????? hr:Potisni automat it:Automa a pila ja:?????????????? mk:Pushdown ??????? pl:Automat ze stosem ru:??????? ? ?????????? ??????? sk:Zásobníkový automat zh:?????Automate à pile811945