Automates à Pile pour Langages Simples

1. La Stratégie et la Notation des Transitions

La stratégie de reconnaissance pour $L=\{a^n{b}^n\mid n\ge 0\}$ se décompose en trois phases logiques :

1. Phase d'empilement : Tant que nous lisons des a, nous les empilons sur la pile.
2. Phase de dépilement : Dès que nous rencontrons le premier b, nous changeons de phase. Pour chaque b lu, nous dépilons un a.
3. Phase d'acceptation : Si, après avoir lu toute la chaîne, nous nous retrouvons avec une pile vide, le mot est accepté.

Pour décrire les actions de l'automate, nous utilisons une notation standard pour les transitions :
symbole lu, sommet de la pile / chaîne à empiler

• Symbole lu : Un symbole de l'alphabet d'entrée $\Sigma$, ou $ϵ$ pour une transition spontanée.
• Sommet de la pile : Le symbole de l'alphabet de pile $\Gamma$ qui doit être au sommet pour que la transition s'active. Il est consommé (dépilé) par la transition.
• Chaîne à empiler : Une chaîne de symboles de ${\Gamma }^{\ast }$ qui est empilée sur la pile après la consommation du sommet. Le premier symbole de la chaîne devient le nouveau sommet.

Par exemple, a, Z₀ / aZ₀ signifie : "Si je lis a en entrée et que le sommet de la pile est Z₀, alors je consomme Z₀ de la pile et j'empile la chaîne aZ₀. Résultat net : a a été ajouté au-dessus de Z₀."

De même, b, a / ε signifie : "Si je lis b et que le sommet de la pile est a, je consomme a et j'empile la chaîne vide $ϵ$. Résultat net : a a été dépilé."

Pour visualiser cette notation, la vidéo suivante est très claire, bien qu'en anglais. La notation est universelle et l'explication graphique vous sera très utile.

2. Construction de l'Automate pour $L=\{a^n{b}^n\mid n\ge 0\}$

Armés de cette notation, nous pouvons maintenant construire notre automate. Il aura besoin de plusieurs états pour gérer les différentes phases. Un modèle courant utilise un état pour la lecture des a, un autre pour la lecture des b, et un état final.

L'automate suivant est une conception possible. Nous le détaillerons juste après.

La ressource vidéo de Leila Ben Ayed, que nous avons déjà consultée, détaille la logique de construction de manière très pédagogique. Nous allons maintenant nous concentrer sur la partie qui met en œuvre la logique des transitions.

Synthétisons la logique vue dans la vidéo et le diagramme :

1. Initialisation : On utilise un symbole spécial, souvent noté $Z_0$, pour marquer le fond de la pile. Cela permet de savoir quand la pile est "logiquement" vide.
2. État $q_0$ (Lecture des a) :
   • a, Z₀ / aZ₀ : En lisant le premier a, on l'empile sur $Z_0$.
   • a, a / aa : Pour chaque a suivant, on l'empile sur le a déjà au sommet.
3. Transition de $q_0$ à $q_1$ (Début de la lecture des b) :
   • b, a / ε : En lisant le premier b, on doit trouver un a sur la pile. On le dépile (en empilant $ϵ$) et on passe à l'état $q_1$. C'est un point de non-retour.
4. État $q_1$ (Lecture des b) :
   • b, a / ε : On continue de dépiler un a pour chaque b lu.
5. Acceptation :
   • Quand le mot est entièrement lu, si le sommet de la pile est $Z_0$, on peut le dépiler pour vider complètement la pile. ε, Z₀ / ε. L'automate s'arrête dans un état final avec une pile vide.

Le cas $n=0$ (le mot vide $ϵ$) est un cas particulier important. Une transition ε, Z₀ / ε depuis l'état initial vers un état final (ou en faisant de l'état initial un état final) permet de l'accepter.

3. Définition Formelle et Trace d'Exécution

Pour l'agrégation, une représentation graphique ne suffit pas. Il faut être capable de fournir une définition formelle complète de l'automate.

En nous basant sur le document, nous pouvons définir notre automate $M=(E,\Sigma ,\Gamma ,\delta ,q_0,F)$ :

• $E=\{q_0,q_1,q_f\}$ (états pour lire les a, lire les b, et un état final)
• $\Sigma =\{a,b\}$ (alphabet d'entrée)
• $\Gamma =\{a,Z_0\}$ (alphabet de pile)
• $q_0$ est l'état initial.
• $F=\{q_f\}$ (ensemble des états finaux)
• $\delta$ est la fonction de transition :
  • $\delta (q_0,a,Z_0)=\{(q_0,a{Z}_0)\}$
  • $\delta (q_0,a,a)=\{(q_0,aa)\}$
  • $\delta (q_0,b,a)=\{(q_1,ϵ)\}$
  • $\delta (q_1,b,a)=\{(q_1,ϵ)\}$
  • $\delta (q_1,ϵ,Z_0)=\{(q_f,ϵ)\}$
  • Pour gérer le mot vide : $\delta (q_0,ϵ,Z_0)=\{(q_f,ϵ)\}$ (En supposant que la pile contient initialement $Z_0$).

Trace d'exécution

Pour vérifier que notre automate fonctionne, nous simulons son exécution sur un mot, par exemple aabb. Pour cela, on utilise des configurations (ou descriptions instantanées), qui sont des triplets (état, mot restant, contenu de la pile).

Voici la trace pour aabb, en supposant que la pile contient initialement juste $Z_0$:

1. Initial : $(q_0,aabb,Z_0)$
2. Lit a, sommet Z₀. On applique $\delta (q_0,a,Z_0)$:
   $⊢(q_0,abb,a{Z}_0)$
3. Lit a, sommet a. On applique $\delta (q_0,a,a)$:
   $⊢(q_0,bb,aa{Z}_0)$
4. Lit b, sommet a. On applique $\delta (q_0,b,a)$:
   $⊢(q_1,b,a{Z}_0)$
5. Lit b, sommet a. On applique $\delta (q_1,b,a)$:
   $⊢(q_1,ϵ,Z_0)$
6. Fin du mot ($ϵ$), sommet Z₀. On applique $\delta (q_1,ϵ,Z_0)$:
   $⊢(q_f,ϵ,ϵ)$

Le mot est entièrement lu, l'automate est dans un état final $q_f$, et la pile est vide. Le mot aabb est donc accepté.

Conclusion

Aujourd'hui, nous avons franchi le pas de la théorie à la pratique en construisant un automate à pile fonctionnel.

Points clés à retenir :

• La construction d'un automate à pile suit une stratégie claire : identifier les différentes phases de lecture et les actions correspondantes sur la pile (empiler, dépiler, ne rien faire).
• La notation des transitions (symbole lu, sommet de la pile / chaîne à empiler) est le langage formel pour décrire le comportement de l'automate.
• Un automate à pile est formellement défini par un n-uplet qui capture ses états, ses alphabets et sa fonction de transition. Savoir l'écrire est indispensable.
• La trace d'exécution avec des configurations (état, mot restant, pile) est l'outil ultime pour simuler et valider le comportement de votre automate.

Dans notre prochaine leçon, nous pousserons les limites de la calculabilité. Nous introduirons la machine de Turing, un modèle encore plus puissant qui peut reconnaître des langages que même les automates à pile ne peuvent pas gérer, comme $\{a^n{b}^n{c}^n\mid n\ge 0\}$. Cela nous ouvrira les portes de la théorie de la complexité et de la décidabilité.