diff options
| -rw-r--r-- | notes-inf105.tex | 74 |
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. + + + % % |