Start writing some general stuff about analysis of CFLs.

1 files changed, 74 insertions, 0 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 0f67711..55990c8 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3766,6 +3766,80 @@ en \ref{example-of-pumping-lemma-for-algebraic-languages} qu'il n'est
 pas algébrique ; c'est donc que $L$ n'est pas non plus algébrique.
 
 
+\subsection{Notions sur l'analyse des langages hors contexte}
+
+\thingy Il est naturel de se poser la question suivante : existe-t-il
+un algorithme qui, donnée une grammaire hors contexte $G$, permet de
+déterminer si un mot donné appartient au langage $L(G)$ engendré
+par $G$, et, si oui, d'en trouver un arbre d'analyse ?  La réponse à
+cette question est positive, mais plus délicate que dans le cadre des
+langages rationnels où la notion d'automate fini a permis de donner un
+point de vue clair (cf. \ref{rational-languages-are-recognizable}).
+
+\thingy Il existe bien un modèle de calcul qu'on peut imaginer comme
+l'analogue pour les langages algébriques (et grammaires hors contexte)
+de ce que les automates finis sont pour les langages rationnels (et
+expressions régulières) : il s'agit des \emph{automates à pile}.
+Informellement, un automate à pile non déterministe fonctionne comme
+un automate fini non déterministe à transitions spontanées, mais il a,
+en plus de son état courant, accès à une « pile », qui contient des
+éléments d'un autre alphabet (l'alphabet de pile), et pour choisir la
+transition à effectuer, il peut consulter, en plus du symbole proposé,
+les symboles au sommet de la pile (jusqu'à une profondeur bornée), et
+une fois cette transition effectuée, décider de rajouter, retirer ou
+remplacer des symboles au sommet de la pile.
+
+{\footnotesize
+
+De façon plus formelle, un automate à pile non déterministe est la
+donnée d'un ensemble fini $Q$ d'états, d'un ensemble $I \subseteq Q$
+d'états dits initiaux, d'un ensemble $F \subseteq Q$ d'états dits
+finaux, d'un ensemble fini $\Gamma$ appelé alphabet de pile, et d'une
+relation de transition $\delta \subseteq (Q \times
+(\Sigma\cup\{\varepsilon\}) \times \Gamma^*) \times (Q \times
+\Gamma^*)$.  Dire que $((q,t,\lambda), (q',\lambda')) \in \delta$
+signifie que l'automate peut transitionner de l'état $q$ avec
+$\lambda$ au sommet de la pile vers l'état $q'$ avec $\lambda'$ (à la
+place de $\lambda$) au sommet de la pile en consommant la lettre $t$
+(ou spontanément si $t=\varepsilon$), et l'automate \emph{accepte} un
+mot $w$ lorsqu'il existe une suite de transitions d'un état initial
+avec pile vide vers un état final avec pile vide qui consomme les
+lettres de $w$.
+
+De façon plus précise, l'automate accepte $w$ lorsqu'il existe
+$q_0,\ldots,q_n \in Q$ (les états traversés) et $t_1,\ldots,t_n \in
+(\Sigma\cup\{\varepsilon\})$ (les symboles consommés) et
+$\gamma_1,\ldots,\gamma_n \in \Gamma^*$ (les états intermédiaires de
+la pile) et $\lambda_1,\ldots,\lambda_n \in \Gamma^*$ (les mots
+dépilés) et $\lambda'_1,\ldots,\lambda'_n \in \Gamma^*$ (les mots
+empilés) tels que : $q_0 \in I$ et $q_n\in F$ et et $\lambda_1\gamma_1
+= \varepsilon$ et $\lambda'_n\gamma_n = \varepsilon$ et
+$((q_{i-1},t_i,\lambda_i),(q_i,\lambda'_i)) \in \delta$ pour
+chaque $1\leq i\leq n$ et $w = t_1\cdots t_n$ et enfin
+$\lambda_i\gamma_i = \lambda'_{i-1}\gamma_{i-1}$ pour chaque $1\leq
+i\leq n$.
+
+(Il existe différentes variations autour de cette notion, certaines
+sans importance : notamment, on peut relaxer l'exigence que l'automate
+termine le calcul avec la pile vide, cela ne change rien à la classe
+des langages acceptés.)
+
+\par}
+
+On peut montrer qu'il y a équivalence entre grammaires hors contexte
+et automates à pile non déterministes au sens où tout langage engendré
+par une grammaire hors contexte est le langage accepté par un automate
+à pile non déterministe et réciproquement.  Il n'est d'ailleurs pas
+très difficile de construire algorithmiquement un automate à pile non
+déterministe qui accepte le langage engendré par une grammaire hors
+contexte donnée.  Mais une différence essentielle avec les automates
+finis est que cette fois \emph{le non déterministe est essentiel} :
+les automates à pile déterministes (qu'il faut définir soigneusement)
+acceptent strictement moins de langages que les automates à pile
+non déterministes.
+
+
+
 
 %
 %