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 mais il dispose également d'une pile. Ainsi, un automate à pile prend en entrée un mot et réalise une série de transitions, chacune consistant à lire une lettre de du mot ou à réaliser des opérations sur la pile. Les transitions effectuées dépendent des lettres du mot et du sommet de la pile. Selon l'état de l'automate à la fin du calcul, le mot peut être accepté ou refusé.

La puissance de calcul des automates à piles correspond aux langages non-contextuels soit ceux qui peuvent être décrits par une grammaire hors-contexte.

Automate à pile non déterministe

Un automate à pile (non déterministe) est un 7-uplet $\mathcal{A}=(Q,\Sigma ,\Gamma ,\delta ,{\gamma }_0,q_0,T)\underline{}$, où

• $Q\underline{}$ est l'ensemble d'états,
• $\Sigma \underline{}$ est l'alphabet d'entrée,
• $\Gamma \underline{}$ est l'alphabet de pile,
• $\delta :Q\times (\Sigma \cup \{ϵ\})\times \Gamma \to \mathcal{P}(Q\times {\Gamma }^{\ast })$ est la fonction de transition (la notation $\mathcal{P}$ désignant l'ensemble des parties),
• ${\gamma }_0\in \Gamma$ est le symbole de fond de pile,
• $q_0\in Q$ est l'état initial,
• $T\subset Q$ est l'ensemble des états terminaux.

Une configuration de l'automate est un triplet $(q,w,\beta )\in Q\times {\Sigma }^{\ast }\times {\Gamma }^{\ast }$. Un calcul de l'automate sur un mot $w\in {\Sigma }^{\ast }$ est une série de transitions à partir de la configuration (q₀,w,γ₀). À partir d'une configuration (q,σw,γβ), où σ et γ sont des lettres de Σ et Γ, les transitions possibles sont :

• $(q,\sigma w,\gamma \beta )⊢(q^{\prime },w,\alpha \beta )$ lorsque $(q^{\prime },\alpha )\in \delta (q,\sigma ,\gamma )$,
• $(q,\sigma w,\gamma \beta )⊢(q^{\prime },\sigma w,\alpha \beta )$ lorsque $(q^{\prime },\alpha )\in \delta (q,ϵ,\gamma )$.

On dit qu'un mot est accepté par l'automate s'il existe une série de transitions qui conduit à une configuration acceptante, notion qui peut être définie de deux façons :

• Pour les automates à reconnaissance par pile vide, les configurations acceptantes sont les configurations de la forme (q,ε,ε) où $q\in Q$ est un état quelconque. Autrement dit, il est possible d'arriver à vider entièrement la pile au moment où on termine la lecture du mot.
• Pour les automates à reconnaissance par état final, les configurations acceptantes sont les configurations de la forme (q,ε,β) où $q\in T$ est un état final.

Dans le cas non déterministe, cette distinction n'a pas d'importance car les deux types d'automates sont équivalents.

Le langage $L(\mathcal{A})$ reconnu par l'automate $\mathcal{A}$ est l'ensemble des mots de Σ qui sont acceptés.

Automate à pile déterministe

Un automate à pile déterministe est défini de la même manière qu'un automate à pile non déterministe, à l'exception de la fonction de transition. Dans le cas déterministe, δ est une fonction partielle $Q\times (\Sigma \cup \{ϵ\})\times \Gamma \to Q\times {\Gamma }^{\ast }$. De plus, lorsque δ(q,ε,γ) est définie, alors δ(q,σ,γ) ne peut être définie pour aucun $\sigma \in \Sigma$. Ainsi, au plus une transition est possible à partir de n'importe quelle configuration.

On distingue de même deux types de reconnaissance, par état final ou par pile vide. Les automates déterministes avec reconnaissance par état final sont plus puissants que les automates avec reconnaissance par pile vide. Plus précisément, un langage L peut être reconnu par le second type d'automate s'il peut être reconnu par un automate du premier type et qu'aucun mot du L n'est préfixe d'un autre. Par exemple, le langage a**b(n > 0) est reconnu par les deux types d'automates déterministes, mais le langage a ne l'est que par automate déterministe par état final.

Reconnaissance du langage $\{a^k{b}^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 )=\varnothing$ 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.

On commence par lire le premier caractère : Si le mot est vide on a fini et le mot est accepté car q₀ 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 q₁. Si c'est un b, le mot est rejeté (7).

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

Dans l'état q₂, 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 q₃ (6). Si on lit un a, on désactive l'automate et le mot est rejeté (7).

Dans l'état q₃, si le mot est fini on l'accepte car $q_3\in T$, si non on le rejette (7).

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 (plus précisément, on peut le tester en temps O(n) pour un mot de longueur n, grâce à l'algorithme CYK).

La classe des langages rationnels (reconnus par automate fini) est strictement incluse dans la classe des langages algébriques déterministes (reconnus par automate à pile déterministe par état final), elle même strictement incluse dans la classe des langages algébriques (reconnus par automate à pile non déterministe). Par exemple, le langage a**b est algébrique déterministe mais non rationnel, et le langage des mots palindromes est algébrique mais pas algébrique déterministe. Certains langages ne sont pas reconnus par automate à pile, par exemple abc (on peut le montrer à l'aide du lemme d'Ogden).

La plupart des langages de programmation sont décrits par une grammaire non contextuelle. L'analyse syntaxique d'un programme, qui est une des premières opérations effectuée par un compilateur, peut donc être effectuée par un automate à pile.

Il existe des outils automatiques pour construire l'automate à pile à partir d'une description de la grammaire du langage (par exemple Lex et Yacc en C).

En langage C :

1. #include <stdlib.h>

2. #include <stdio.h>

3. #define POP -1

4. #define ACCEPT -2

5. #define ERROR -3

6. #define ALPHABET 3 /* Grandeur*/

7. /*

8. Push-down automation)

9. Symbol | ( | ) | \0

10. ---------+---------+--------+-----------

11. State 0 | PUSH 1 | ERROR | ACCEPT

12. State 1 | PUSH 1 | POP | ERROR

13. */

14. int states[2][ALPHABET*2] =

15. {

16. {

17. '(', 1 /* PUSH 1 */,

18. ')', ERROR,

19. '\0', ACCEPT

20. },

21. {

22. '(', 1 /* PUSH 1 */,

23. ')', POP,

24. '\0', ERROR

25. }

26. };

27. int main( int argc, char** argv )

28. {

29. int stack[100] = { 0 };

30. int i = 0;

31. int action = 0;

32. int* tos = stack;

33. char s [80+1];

34. char* p = s;

35. /* Chaine de donnée */

36. printf("Entrez l'expression: ");

37. gets( &s );

38. /*Pile poussée*/

39. *(tos++) = 0;

40. /* Sortie */

41. do

42. {

43. /* Boucle*/

44. action = ERROR;

45. for( i = 0; i < ALPHABET; i++ )

46. {

47. if( states[*(tos-1)][i*2] == *p )

48. {

49. action = states[*(tos-1)][i*2+1];

50. break;

51. }

52. }

53. /* Actions*/

54. if( action == ERROR )

55. {

56. printf("Erreur inattendue à la position %d", p-s);

57. break;

58. }

59. else if( action == ACCEPT )

60. printf("Sortie acceptée!");

61. else if( action == POP )

62. tos--;

63. else

64. *(tos++) = action;

65. /* Données supplémentaires... */

66. p++;

67. }

68. while( action != ACCEPT );

69. getchar();

70. return 0;

71. }

Un automate à deux piles ou plus a la même puissance de calcul qu'une machine de Turing. En effet, les automates à deux piles sont une généralisation des machines à deux compteurs, elles mêmes équivalentes aux machines de Turing. On peut aussi le démontrer de manière plus directe : un automate à deux piles peut simuler une machine de Turing, en faisant en sorte que la partie du ruban située à gauche de la tête de lecture soit enregistrée dans la première pile, et la partie du ruban située à droite de la tête de lecture soit enregistrée sur la seconde.