CFG et Automates à Pile (AP) : Introduction

1. Grammaires Hors-Contexte (CFG) : Le Modèle Génératif

Pour décrire un langage comme $L=\{a^n{b}^n\mid n\ge 0\}$, nous avons besoin d'un mécanisme qui peut "compter" et assurer une correspondance. Une grammaire le fait de manière élégante par un processus de réécriture récursive.

Une grammaire hors-contexte (en anglais, Context-Free Grammar ou CFG) est un ensemble de règles de production qui décrivent comment former les chaînes d'un langage. L'idée est de partir d'un symbole de départ (l'axiome) et de le remplacer successivement en utilisant les règles jusqu'à n'obtenir qu'une séquence de symboles "finaux" (les terminaux).

Définition formelle

Pour poser les bases rigoureuses attendues à l'agrégation, nous allons directement aborder la définition formelle.

Comme vous l'avez vu, une grammaire hors-contexte $G$ est un quadruplet $G=(V,\Sigma ,R,S)$ où :

• $V$ est un alphabet de symboles non-terminaux (ou variables).
• $\Sigma$ est un alphabet de symboles terminaux, disjoint de $V$.
• $R$ est un ensemble fini de règles de production de la forme $A\to \alpha$, où $A\in V$ et $\alpha \in (V\cup \Sigma {)}^{\ast }$.
• $S\in V$ est l'axiome (ou symbole de départ).

Le terme "hors-contexte" vient du fait que la variable $A$ à gauche d'une règle peut être remplacée par $\alpha$ indépendamment du contexte dans lequel elle apparaît.

Le Processus de Dérivation

Pour générer un mot, on part de l'axiome et on applique les règles. Chaque application d'une règle est une étape de dérivation.

Par exemple, pour le langage $L=\{a^n{b}^n\mid n\ge 0\}$, la grammaire est :

• $V=\{S\}$
• $\Sigma =\{a,b\}$
• $R=\{S\to aSb,S\to ϵ\}$
• Axiome : $S$

Pour dériver le mot $aabb$:
$S\Rightarrow aSb\Rightarrow a(aSb)b\Rightarrow aaSbb\Rightarrow aaϵbb=aabb$

La vidéo suivante illustre ce processus de dérivation.

Pour une référence écrite concise et formelle, vous pouvez consulter le document suivant, qui correspond au niveau de rigueur attendu.

2. Automates à Pile (AP) : Le Modèle de Reconnaissance

Maintenant que nous savons générer des langages comme $a^n{b}^n$, il nous faut une machine capable de les reconnaître. Nous avons vu qu'un automate fini ne suffit pas car sa mémoire est limitée à ses états. L'ajout d'une pile (structure LIFO : Last-In, First-Out) est précisément ce qui lui manquait.

Un automate à pile (en anglais, Pushdown Automaton ou PDA) est un automate fini doté d'une pile de capacité illimitée. À chaque transition, l'automate peut non seulement changer d'état, mais aussi manipuler le sommet de la pile (empiler ou dépiler des symboles).

Définition formelle

Formellement, un automate à pile $A$ est généralement défini par un 7-uplet $A=(Q,\Sigma ,\Gamma ,\delta ,q_0,Z_0,F)$ :

• $Q$ : un ensemble fini d'états.
• $\Sigma$ : l'alphabet d'entrée.
• $\Gamma$ : l'alphabet de la pile.
• $\delta$ : la fonction de transition. C'est le cœur de l'automate. Elle prend en argument l'état courant, le symbole d'entrée (ou $ϵ$) et le symbole au sommet de la pile, et retourne un ensemble de paires (nouvel état, chaîne à empiler).
  $\delta :Q\times (\Sigma \cup \{ϵ\})\times \Gamma \to \mathcal{P}(Q\times {\Gamma }^{\ast })$
• $q_0\in Q$ : l'état initial.
• $Z_0\in \Gamma$ : le symbole initial de la pile.
• $F\subseteq Q$ : l'ensemble des états accepteurs.

L'intuition pour reconnaître $L=\{a^n{b}^n\mid n\ge 0\}$ est simple :

1. Pour chaque a lu en entrée, on empile un symbole (disons X) sur la pile.
2. Quand on commence à lire des b, on dépile un X pour chaque b lu.
3. Si, à la fin de la lecture du mot, la pile est vide (et que l'on est dans un état accepteur), le mot est reconnu.

La vidéo suivante détaille magnifiquement cette construction.

Pour la définition formelle écrite, le document de l'ENS reste notre référence.

3. Le Lien Fondamental : CFG $⟺$ PDA

Tout comme le théorème de Kleene établit l'équivalence entre les automates finis et les expressions régulières, un théorème central de la théorie des langages établit l'équivalence entre les grammaires hors-contexte et les automates à pile.

Théorème d'équivalence : Un langage est généré par une grammaire hors-contexte si et seulement si il est reconnu par un automate à pile.

L'intuition de la preuve (de la grammaire vers l'automate) est que la pile de l'automate peut simuler une dérivation gauche de la grammaire. L'automate garde sur sa pile la partie de la chaîne (mélange de terminaux et non-terminaux) qui reste à dériver.

Conclusion

Cette leçon a posé les fondations d'un nouveau chapitre de la théorie des langages.

Points clés à retenir :

• Les grammaires hors-contexte (CFG) sont un formalisme génératif défini par un quadruplet $(V,\Sigma ,R,S)$. Elles utilisent des règles de réécriture pour construire des mots et sont capables de décrire des structures récursives ou imbriquées que les expressions régulières ne peuvent pas capturer.
• Les automates à pile (PDA) sont un formalisme de reconnaissance. Ils sont constitués d'un automate fini augmenté d'une pile. Cette pile leur confère une mémoire LIFO illimitée, essentielle pour reconnaître les langages hors-contexte.
• Le théorème d'équivalence stipule que la classe des langages générés par les CFG est exactement la même que la classe des langages reconnus par les PDA. C'est la pierre angulaire de ce domaine.

Dans notre prochaine leçon, nous mettrons ces définitions en pratique. Nous nous concentrerons sur la construction effective d'un automate à pile pour un langage hors-contexte simple, en détaillant la logique de conception des états et des transitions.