diff options
| -rw-r--r-- | notes-inf105.tex | 177 |
1 files changed, 165 insertions, 12 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 57a9267..c8b4703 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -106,7 +106,7 @@ appelleront un \textbf{alphabet}, et qui correspond pour les informaticiens à un \textbf{jeu de caractères}. Il s'agit d'un ensemble \emph{fini}, sans structure particulière, dont les éléments s'appellent \textbf{lettres}, ou encore \textbf{caractères} dans une -terminologie plus informatique. +terminologie plus informatique, ou parfois aussi \textbf{symboles}. Les exemples mathématiques seront souvent donnés sur un alphabet tel que l'alphabet à deux lettres $\{a,b\}$ ou à trois lettres @@ -873,7 +873,7 @@ pour chaque $q\in F$ une flèche pointant de $q$ vers nulle part\footnote{Certains auteurs préfèrent d'autres conventions, par exemple celle consistant à entourer deux fois les états finaux.}. -Lorsque plusieurs arêtes étiquetées par des symboles $x,y$ différents +Lorsque plusieurs arêtes étiquetées par des lettres $x,y$ différentes relient les mêmes sommets $q,q'$ (i.e., lorsqu'on a à la fois $\delta(q,x) = q'$ et $\delta(q,y) = q'$), on pourra écrire « $x,y$ » ou « $x|y$ » sur l'arête en question (et ne la tracer qu'une seule @@ -924,7 +924,7 @@ Graphiquement, on peut présenter la procédure de la manière suivante : on part de l'état $q_0$ (sommet du graphe représentant l'automate) indiqué par la flèche entrante (pointant de nulle part), et pour chaque lettre du mot $w = x_1\cdots x_n$ considéré, on suit l'arête -portant ce symbole (et partant de l'état où on se trouve +portant cette lettre pour étiquette (et partant de l'état où on se trouve actuellement). Si à la fin l'état $q_n$ est acceptant (représenté par une flèche pointant vers nulle part), le mot $w$ est accepté, sinon il est rejeté. @@ -1080,7 +1080,7 @@ partant de $q$ et étiquetée par $x$. \thingy Le fonctionnement d'un DFAI est le même que celui d'un DFA, à la modification suivante près : si on donne à consommer à l'automate -un symbole pour lequel la transition n'est pas définie, i.e., s'il +une lettre pour laquelle la transition n'est pas définie, i.e., s'il rencontre un $x$ pendant qu'il se trouve dans un état $q$ pour lequel $\delta(q,x)$ n'est pas défini, alors l'automate cesse de fonctionner : l'automate n'a plus d'état, n'effectue plus de @@ -1250,7 +1250,7 @@ les automates finis déterministes comme étant complets, d'autres comme Q \times \Sigma \times Q$). \end{itemize} Autrement dit, on autorise maintenant un ensemble quelconque d'états -initiaux, et de même, au lieu qu'un état $q$ et un symbole $x$ +initiaux, et de même, au lieu qu'un état $q$ et une lettre $x$ déterminent un unique état $q' = \delta(q,x)$, on a maintenant affaire à un ensemble quelconque de triplets $(q,x,q')$. @@ -1280,15 +1280,15 @@ chaque $1\leq i\leq n$. Il existe plusieurs manières de reformuler ce comportement : on peut par exemple dire que l'automate est dans plusieurs états à la fois, qu'il commence dans tous les états initiaux à la fois, et qu'à chaque -fois qu'il consomme un symbole $x$, il effectue toutes les transitions -possibles à partir d'un état où et étiquetées par ce symbole, et qu'au -bout du compte l'automate accepte le mot lorsqu'il est dans \emph{au - moins un} état acceptant (même s'il est, par ailleurs, dans d'autres -états). C'est cette façon de voir les choses qui conduira à +fois qu'il consomme une lettre $x$, il effectue toutes les transitions +possibles à partir d'un état où et étiquetées par cette lettre, et +qu'au bout du compte l'automate accepte le mot lorsqu'il est dans +\emph{au moins un} état acceptant (même s'il est, par ailleurs, dans +d'autres états). C'est cette façon de voir les choses qui conduira à l'équivalence entre NFA et DFA (cf. \ref{determinization-of-nfa}). Une autre façon de présenter les choses est que l'automate « devine » -par quel état initial commencer, et à chaque symbole consommé, +par quel état initial commencer, et à chaque lettre consommée, « devine » quelle transition effectuer, de manière à accepter le mot si c'est possible. @@ -2440,7 +2440,7 @@ $L$ n'est pas rationnel est donc quelque chose comme ceci : Donnons maintenant un exemple d'utilisation du lemme : -\begin{prop} +\begin{prop}\label{example-of-pumping-lemma} Soit $\Sigma = \{a,b\}$. Le langage $L = \{a^n b^n : n\in\mathbb{N}\} = \{\varepsilon, ab, aabb, aaabbb,\ldots\}$ constitué des mots formés d'un certain nombre ($n$) de $a$ suivis du même nombre de $b$ n'est @@ -2834,6 +2834,159 @@ et les langages reconnus sont les mêmes. \end{proof} +\section{Grammaires hors contexte} + +\subsection{Définition, notations, exemples} + +\thingy\label{definition-context-free-grammar} Une \textbf{grammaire + hors contexte} (on dit parfois aussi « sans contexte » ; en anglais, +« context-free grammar » ou « CFG ») sur un alphabet $\Sigma$ est la +donnée +\begin{itemize} +\item d'un second alphabet $N$, disjoint de $\Sigma$, appelé ensemble + des \textbf{nonterminaux}, +\item d'un élément $S \in N$ appelé \textbf{axiome} ou \textbf{symbole + initial} de la grammaire, +\item d'un ensemble \emph{fini} $R \subseteq N \times (\Sigma\cup + N)^*$ de couples $(T,\alpha)$ où $T$ est un nonterminal et $\alpha$ + un mot sur l'alphabet $\Sigma\cup N$, les éléments $(T,\alpha)$ de + $R$ étant appelés les \textbf{règles} ou \textbf{productions} de la + grammaire. +\end{itemize} + +\thingy Une grammaire hors contexte fait donc intervenir deux +alphabets : l'alphabet $\Sigma$ sur lequel sera le langage (encore à +définir), et l'alphabet $N$ (disjoint de $\Sigma$) qui intervient dans +la définition de la grammaire. Pour fixer la terminologie, on +appellera \textbf{symbole} un élément de $\Sigma \cup N$, ces symboles +étant dits \textbf{terminaux} lorsqu'ils appartiennent à $\Sigma$ (ou +simplement « lettres »), et \textbf{nonterminaux} lorsqu'ils +appartiennent à $N$. Un mot sur $\Sigma\cup N$ (c'est-à-dire, une +suite finie de symboles) sera appelé \textbf{pseudo-mot}, tandis que +le terme « mot » sans précision supplémentaire sera utilisé pour +désigner un mot sur $\Sigma$ (autrement dit, un mot est un pseudo-mot +ne comportant que des symboles terminaux). + +Typographiquement, on aura tendance à utiliser des lettres minuscules +pour désigner les symboles terminaux, et majuscules pour désigner les +symboles nonterminaux ; et on aura tendance à utiliser des lettres +grecques minuscules pour désigner les pseudo-mots. + +\thingy Intuitivement, il faut comprendre la grammaire de la manière +suivante. Les règles $(T,\alpha)$, où on rappelle que $T$ est un +symbole nonterminal et $\alpha$ un pseudo-mot (et on notera $T +\rightarrow \alpha$, cf. ci-dessous) doivent se comprendre +intuitivement comme « le symbole $T$ peut être remplacé +par $\alpha$ ». On part de l'axiome $S$, et on peut effectuer +librement des substitutions $T \rightarrow \alpha$ (consistant à +remplacer un nonterminal $T$ par un pseudo-mot $\alpha$) autorisées +par les règles : le langage défini par la grammaire est l'ensemble de +tous les mots (ne comportant plus aucun nonterminal) qu'on peut +obtenir de la sorte. + +Rendons maintenant cette définition précise : + +\thingy Lorsque $G$ est une grammaire hors-contexte comme +en \ref{definition-context-free-grammar}, on note $T +\mathrel{\rightarrow_G} \alpha$, ou simplement $T \rightarrow \alpha$ +(lorsque $G$ est clair) pour signifier que $(T,\alpha)$ est une règle +de $G$. + +On définit une relation $\Rightarrow$ en posant $\gamma T \gamma' +\Rightarrow \gamma\alpha\gamma'$ pour toute règle $(T,\alpha)$ et tous +pseudo-mots $\gamma,\gamma'$ : autrement dit, formellement, on définit +$\lambda\Rightarrow\xi$ lorsqu'il existe $\gamma,\gamma' \in +(\Sigma\cup N)^*$ et $(T,\alpha) \in R$ (ensemble des règles de $G$) +tels que $\lambda = \gamma T \gamma'$ et $\xi = \gamma\alpha\gamma'$. +Concrètement, $\lambda\Rightarrow\xi$ signifie donc que $\xi$ est +obtenu en remplaçant un nonterminal $T$ du pseudo-mot $\lambda$ par la +partie droite d'une production $T \rightarrow \alpha$ de la +grammaire $G$ : on dit encore que $\lambda \Rightarrow \xi$ est une +\textbf{dérivation immédiate} de $G$. (On pourra dire que $T +\rightarrow \alpha$ est la règle \textbf{appliquée} dans cette +dérivation immédiate, et que $\gamma$ et $\gamma'$ sont respectivement +le \textbf{contexte gauche} et le \textbf{contexte droit} de +l'application de la règle.) Bien sûr, si nécessaire, on précisera la +grammaire appliquée en écrivant $\lambda \mathrel{\Rightarrow_G} \xi$ +au lieu de simplement $\lambda\Rightarrow\xi$. + +Une suite de pseudo-mots $(\lambda_0,\ldots,\lambda_n)$ telle que +\[ +\lambda_0 \Rightarrow \lambda_1 \Rightarrow \cdots \Rightarrow \lambda_n +\] +autrement dit $\lambda_{i-1} \Rightarrow \lambda_i$ pour chaque $1\leq +i\leq n$, est appelée \textbf{dérivation} de $\lambda_n$ à partir de +$\lambda_0$ dans la grammaire $G$, et on note $\lambda_0 +\mathrel{\Rightarrow^*} \lambda_n$ pour indiquer son existence +(c'est-à-dire, si on préfère, que la relation $\Rightarrow^*$ est la +clôture réflexive-transitive de $\Rightarrow$, i.e., la plus petite +relation binaire réflexive et transitive contenant $\Rightarrow$). +Remarquons que $n=0$ est permis, autrement dit $\lambda +\mathrel{\Rightarrow^*} \lambda$ pour tout pseudo-mot $\lambda$. Bien +sûr, si nécessaire, on précisera la grammaire appliquée en écrivant +$\lambda \mathrel{\Rightarrow^*_G} \xi$ au lieu de simplement $\lambda +\mathrel{\Rightarrow^*} \xi$. + +Concrètement, $\lambda \mathrel{\Rightarrow^*} \xi$ signifie donc +qu'on peut passer de $\lambda$ à $\xi$ en effectuant une suite +(finie !) de dérivations immédiates, c'est-à-dire en remplaçant à +chaque étape un nonterminal $T$ par la partie droite $\alpha$ d'une +règle $T \to \alpha$ de la grammaire $G$. + +Il va de soi qu'un pseudo-mot qui ne comporte que des terminaux, i.e., +qui est en fait un mot (sur $\Sigma$), ne peut pas être dérivé plus +loin. Ceci justifie au moins en partie la terminologie de +« terminal ». + +\thingy Le \textbf{langage engendré} $L(G)$ par une grammaire +hors-contexte $G$ est l'ensemble des mots $w$ (ne comportant plus de +nonterminaux !) qui peuvent s'obtenir par dérivation à partir de +l'axiome $S$ de $G$, autrement dit : +\[ +L(G) = \{w \in \Sigma^* : S \mathrel{\Rightarrow^*} w\} +\] + +Un langage qui peut s'écrire sous la forme $L(G)$ où $G$ est une +grammaire hors-contexte est appelé \textbf{langage hors-contexte} ou +\textbf{algébrique}. + +\thingy À titre d'exemple, considérons la grammaire sur l'alphabet +$\Sigma = \{a,b\}$ donnée par +\[ +\begin{aligned} +S &\rightarrow aSb\\ +S &\rightarrow \varepsilon\\ +\end{aligned} +\] +où implicitement $S$ est l'axiome et le seul nonterminal : autrement +dit, $G$ est donnée par $N = \{S\}$, d'axiome $S$, et de règles de +production $(S,aSb)$ et $(S,\varepsilon)$ (où $\varepsilon$, bien +entendu, désigne le mot vide). Un pseudo-mot pour cette grammaire est +un mot sur l'alphabet $\Sigma\cup N = \{a,b,S\}$, et une dérivation +immédiate consiste \emph{soit} à ajouter un $a$ et un $b$ à gauche et +à droite d'un $S$ dans un pseudo-mot, \emph{soit} à retirer un $S$. + +Dans ces conditions, il est clair qu'une dérivation partant de +l'axiome $S$ est constituée d'un certain nombre d'applications de la +première règle suivi d'au plus une application de la seconde (puisque +le nombre d'occurrences de $S$ va alors tomber de $1$ à $0$ et on ne +pourra plus dériver). Autrement dit, une telle dérivation prend la +forme +\[ +S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow \cdots \Rightarrow a^n +S b^n +\] +ou éventuellement +\[ +S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow \cdots \Rightarrow a^n +S b^n \Rightarrow a^n b^n +\] +Le langage $L(G)$ défini par la grammaire est donc $\{a^n b^n : +n\in\mathbb{N}\}$. (On a vu en \ref{example-of-pumping-lemma} que ce +langage n'est pas rationnel : il existe donc des langages algébriques +qui ne sont pas rationnels.) + + % % |