Automate À Pile

Automate à pile

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.

Sommaire

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,\Sigma,\Phi, F,\omega, i,T)\underline{}, où

  • E\underline{} est l'ensemble d'états,
  • \Sigma\underline{} est l'alphabet d'entrée,
  • \Phi\underline{} est l'alphabet de pile,
  • F : E\times(\Sigma\cup \{ \epsilon \}) \times ( \Phi \cup \{ \omega \} ) \rightarrow P(E\times\Phi^*) est la relation de transition,
  • \omega\underline{} est le symbole de pile vide,
  • i\in E est l'état initial,
  • T \subset E est l'ensemble des états terminaux.

Fonctionnement

L'automate commence à l'état i. La transition s'effectue en appliquant F(q,a,p) = (q1',P1),...,(qn',Pn)q est un des états courant, a est le caractère lu, p est un élément de la pile qui sera dépilé (peut être ω), qk' est un des nouveaux états dans lequel peut passer l'automate en empilant Pk. L'automate accepte le mot s'il a la possibilité, en lisant tout le mot, d'arriver dans un des états finaux.

Exemples

Reconnaissance du langage \{a^kb^k | k \ge 1 \}

On peut utiliser l'automate M = (\{q_0, q_1, q_2, q_3\}, \{a, b\}, \{A,\underline{A}\}, \delta, \omega, q_0, \{q_0, q_3\} ),

où les transitions sont définies par :

(1) \delta(q_0, a, \omega) = \{(q_1, \underline{A})\}

(2) \delta(q_1, a, \omega) = \{(q_1, A)\}\underline{}

(3) \delta(q_1, b, A) = \{(q_2, \omega)\}\underline{}

(4) \delta(q_1, b, \underline{A}) = \{(q_3, \omega)\}

(5) \delta(q_2, b, A) = \{(q_2, \omega)\}\underline{}

(6) \delta(q_2, b, \underline{A}) = \{(q_3, \omega)\}

(7) \delta(q, \theta, \rho) = \empty pour les autres valeurs de (q, \theta, \rho)\underline{}

Par exemple, dans l'état q_1\underline{}, si on lit un b\underline{} et que l'on dépile un A\underline{}, on passe dans l'état q_2\underline{} sans rien empiler.

Automateapile.png

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 \underline{A} (1) (il marque le fond de la pile), et on passe à l'état q1. Si c'est un b, le mot est rejeté (7).

Ensuite dans l'état q1, à chaque a on empile A (2). Si on a un b, deux possbilités : - Si on n'a empilé qu'un seul \underline{A} on passe à l'état q3 en dépilant le \underline{A} (4). - Si on a empilé un ou plus A, on passe à l'état q2 en dépilant un A (3).

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 \underline{A} (fond de la pile) et on passe dans l'état q3 (6). Si on lit un a, on désactive l'automate et le mot est rejeté (7).

Dans l'état q3, si le mot est fini on l'accepte car q_3\in T, si non on le rejete (7).

Propriétés

Chaque langage défini par une grammaire non contextuelle est reconnu par un automate à pile et réciproquement.

En conséquence, le problème de l'appartenance d'un mot à un langage non contextuelle est décidable : il existe un algorithme qui, étant donnés la description d'une grammaire non contextuelle et un mot, répond en temps fini à la question de l'appartenance de ce mot au langage défini par cette grammaire.

Implémentation d'un automate à pile

  1. #include <stdlib.h>
    
  2. #include <stdio.h>
    
  3.  
    
  4. #define POP	-1
    
  5. #define ACCEPT	-2
    
  6. #define ERROR	-3
    
  7.  
    
  8. #define ALPHABET 3	/* Grandeur*/
    
  9.  
    
  10. /*
    
  11. 	Push-down automation)
    
  12.  
    
  13. 	Symbol   | (       | )	    | \0
    
  14. 	---------+---------+--------+-----------
    
  15. 	State 0  | PUSH 1  | ERROR  | ACCEPT
    
  16. 	State 1  | PUSH 1  | POP    | ERROR
    
  17. */
    
  18.  
    
  19. int states[2][ALPHABET*2] =
    
  20. {
    
  21. 	{
    
  22. 		'(',	1 /* PUSH 1 */,
    
  23. 		')',	ERROR,
    
  24. 		'\0',	ACCEPT
    
  25. 	},
    
  26. 	{
    
  27. 		'(',	1 /* PUSH 1 */,
    
  28. 		')',	POP,
    
  29. 		'\0',	ERROR
    
  30. 	}
    
  31. };
    
  32.  
    
  33.  
    
  34. int main( int argc, char** argv )
    
  35. {
    
  36. 	int	stack[100]	= { 0 };
    
  37. 	int	i		= 0;
    
  38. 	int	action		= 0;
    
  39. 	int*	tos		= stack;
    
  40. 	char	s		[80+1];
    
  41. 	char*	p		= s;
    
  42.  
    
  43. 	/* Chaine de donnée */
    
  44. 	printf("Entrez l'expression: ");
    
  45. 	gets( &s );
    
  46.  
    
  47. 	/*Pile poussée*/
    
  48. 	*(tos++) = 0;
    
  49.  
    
  50. 	/* Sortie */
    
  51. 	do
    
  52. 	{
    
  53. 		/* Boucle*/
    
  54. 		action = ERROR;
    
  55. 		for( i = 0; i < ALPHABET; i++ )
    
  56. 		{			
    
  57. 			if( states[*(tos-1)][i*2] == *p )
    
  58. 			{
    
  59. 				action = states[*(tos-1)][i*2+1];
    
  60. 				break;
    
  61. 			}
    
  62. 		}
    
  63.  
    
  64. 		/* Actions*/
    
  65. 		if( action == ERROR )
    
  66. 		{
    
  67. 			printf("Erreur innatendue à la position %d", p-s);
    
  68. 			break;
    
  69. 		}
    
  70. 		else if( action == ACCEPT )
    
  71. 			printf("Sortie acceptée!");
    
  72. 		else if( action == POP )
    
  73. 			tos--;
    
  74. 		else
    
  75. 			*(tos++) = action;
    
  76.  
    
  77. 		/* Données supplémentaires... */
    
  78. 		p++;
    
  79. 	}
    
  80. 	while( action != ACCEPT );
    
  81.  
    
  82. 	getchar();
    
  83. 	return 0;
    
  84. }
    

Voir aussi

Références

  • (fr) Olivier Carton, Langages formels, calculabilité et complexité. Vuibert 2008, (ISBN 978-2-7117-2077-4).


  • Portail des mathématiques Portail des mathématiques
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Automate %C3%A0 pile ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Automate À Pile de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Automate a pile — Automate à pile 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… …   Wikipédia en Français

  • Automate à pile — 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 une généralisation des automates finis: il dispose en plus d une mémoire infinie organisée en… …   Wikipédia en Français

  • Automate cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe) de l application répétée de cette règle… …   Wikipédia en Français

  • Automate Fini — Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine …   Wikipédia en Français

  • Automate déterministe à états fini — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine …   Wikipédia en Français

  • Automate fini déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine …   Wikipédia en Français

  • Automate fini non déterministe — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine …   Wikipédia en Français

  • Automate fini non déterministe généralisé — Automate fini Pour les articles homonymes, voir Automate. Exemple d un diagramme d automate fini. Un automate fini (on dit parfois machine …   Wikipédia en Français

  • Automate fini — Pour les articles homonymes, voir Automate. Fig. 1 : Automate fini reconnaissant les écritures binaires des multiples de 3. Un automate fini (on dit parfois, par une traduction littér …   Wikipédia en Français

  • Automate sur les mots infinis — En informatique théorique, et spécialement en théorie des automates un automate sur les mots infinis ou ω automate est un automate fini, déterministe ou non, qui accepte des mots infins. Comme un tel automate ne s arrête pas, les conditions d… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”