Exercise on non-ambiguity and analysis of a simple context-free grammar.

1 files changed, 161 insertions, 0 deletions

diff --git a/exercices3.tex b/exercices3.tex
index a58974b..a2fa873 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -360,6 +360,167 @@ a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*}
 %
 
 \bigbreak
+\centerline{\textbf{Langages algébriques et grammaires hors contexte}}
+
+\exercice
+
+On considère la grammaire hors contexte $G$ suivante (d'axiome $S$)
+sur l'alphabet $\Sigma = \{a,b\}$ :
+\[
+S \rightarrow aSS \;|\; b
+\]
+Soit $L = L(G)$ le langage algébrique qu'elle engendre.
+
+(0) Donner quelques exemples de mots dans $L$.
+
+(1) Expliquer pourquoi un $w\in \Sigma^*$ appartient à $L$ si et
+seulement si : soit $w = b$, soit il existe $u,v\in L$ tels que $w =
+auv$.
+
+(2) En déduire par récurrence sur la longueur $|w|$ de $w$ que si $w
+\in L$ alors on a $wz \not\in L$ pour tout $z \in \Sigma^+$
+(c'est-à-dire $z \in \Sigma^*$ et $z \neq \varepsilon$).  Autrement
+dit : en ajoutant des lettres à la fin d'un mot de $L$ on obtient un
+mot qui n'appartient jamais à $L$.  (Indication : lorsque $auvz =
+au'v'$ on pourra considérer les cas (i) $|u'|>|u|$, (ii) $|u'|<|u|$ et
+(iii) $|u'|=|u|$.)
+
+(3) En déduire que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$
+et $v=v'$.  (Indication analogue.)
+
+(4) En déduire que $G$ est inambiguë, c'est-à-dire que chaque mot
+$w\in L$ a un unique arbre d'analyse pour $G$ (on pourra reprendre
+l'analyse de la question (1) et procéder de nouveau par récurrence
+sur $|w|$).
+
+(5) En s'inspirant des questions précédentes, décrire un algorithme
+simple (en une seule fonction récursive) qui, donné un mot
+$w\in\Sigma^*$, décide si $w\in L$ (c'est-à-dire répond vrai ou faux
+selon que $w\in L$ ou $w\not\in L$) ou plus généralement, donné
+$w\in\Sigma^*$, renvoie la longueur du préfixe de $w$ appartenant
+à $L$ s'il existe (il est alors unique d'après la question (2)).
+
+\begin{corrige}
+(0) Quelques exemples de mots dans $L$ sont $b$, $abb$, $aabbb$,
+  $ababb$ ou encore $aabbabb$.
+
+(1) Si $w \in L$, considérons un arbre d'analyse $\mathscr{W}$ de $w$
+  pour $G$ : sa racine, étiquetée $S$, doit avoir des fils étiquetés
+  selon l'une des deux règles de la grammaire, $S\rightarrow b$ ou
+  bien $S\rightarrow aSS$, autrement dit, soit elle a un unique fils
+  étiqueté $b$, soit elle a trois fils étiquetés respectivement
+  $a,S,S$.  Dans le premier cas, le mot $w$ est simplement $b$ ; dans
+  le second, les sous-arbres $\mathscr{U}, \mathscr{V}$ ayant pour
+  racine les deux fils étiquetés $S$ sont encore des arbres d'analyse
+  pour $G$, et si on appelle $u$ et $v$ les mots dont ils sont des
+  arbres d'analyse (c'est-à-dire, ceux obtenus en lisant les feuilles
+  de $\mathscr{U}$ et $\mathscr{V}$ respectivement par ordre de
+  profondeur), alors on a $w = auv$ et $u,v\in L$ puisqu'ils ont des
+  arbres d'analyse pour $G$.
+
+La réciproque est analogue : le mot $b$ appartient trivialement à $L$,
+et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U},
+\mathscr{V}$ pour $G$, et on peut fabriquer un arbre d'analyse pour $w
+:= auv$ qui a une racine étiquetée $S$ ayant trois fils étiquetés
+$a,S,S$, ces deux derniers ayant pour descendants des sous-arbres
+donnés par $\mathscr{U}$ et $\mathscr{V}$.
+
+(2) Montrons par récurrence sur $|w|$ que si $w \in L$ alors on a $wz
+\not\in L$ pour tout $z \in \Sigma^+$.  La récurrence permet de
+supposer la conclusion déjà connue pour tout mot de longueur $<|w|$.
+D'après la question (1), le mot $w$ est soit $b$ soit de la forme
+$auv$ avec $u,v\in L$ et trivialement $|u|<|w|$ et $|v|<|w|$.  Si
+$w=b$, il est évident qu'aucun mot de la forme $bz$ ne peut appartenir
+à $L$ (la question (1) montre que les seuls mots de $L$ sont le mot
+$b$ et des mots commençant par $a$).  Il reste le cas $w = auv$ : on
+veut montrer que $wz$, c'est-à-dire $auvz$, n'appartient pas à $L$.
+Mais s'il y a appartenait, toujours d'après la question (1), il serait
+de la forme $au'v'$ (le cas $b$ étant trivialement exclu), où $u',v'
+\in L$ ; notamment, $uvz = u'v'$.  Distinguons trois cas : (i) soit
+$|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$, c'est-à-dire
+que $u'$ peut s'écrire sous la forme $u' = ut$ pour un $t\in
+\Sigma^+$, et par l'hypothèse de récurrence, on a $u'\not\in L$, une
+contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe
+strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u =
+u't$ pour un $t\in\Sigma^+$, et par l'hypothèse de récurrence (puisque
+$|u'|<|u|<|w|$), on a $u\not\in L$, de nouveau une contradiction ;
+(iii) soit $|u'|=|u|$, donc $u'=u$ (puisqu'ils sont préfixes de même
+longueur du même mot $uvz = u'v'$), et on a alors $v' = vz$, mais
+comme $v\in L$, l'hypothèse de récurrence entraîne $v'\not\in L$,
+encore une contradiction.
+
+(3) Montrons que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$
+et $v=v'$.  On a notamment $uv = u'v'$.  Distinguons trois cas :
+(i) soit $|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$,
+c'est-à-dire que $u'$ peut s'écrire sous la forme $u' = ut$ pour un
+$t\in \Sigma^+$, et par la question (2), on a $u'\not\in L$, une
+contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe
+strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u =
+u't$ pour un $t\in\Sigma^+$, et par la question (2), on a $u\not\in
+L$, de nouveau une contradiction ; (iii) soit $|u'|=|u|$, donc $u'=u$
+(puisqu'ils sont préfixes de même longueur du même mot $uv = u'v'$),
+et on a alors $v' = v$, la conclusion annoncéee.
+
+(4) Soit $w \in L$ : on veut montrer qu'il a un unique arbre d'analyse
+pour $G$.  On procède par récurrence sur $|w|$, ce qui permet de
+supposer la conclusion connue pour tout mot de longueur $<|w|$.  Comme
+on l'a expliqué en (1), il y a deux possibilités pour un arbre
+d'analyse de $w$ : soit la racine a un unique fils étiqueté $b$ et le
+mot analysé est $w=b$, soit la racine a trois fils étiquetés $a,S,S$,
+et des deux derniers fils partent des arbres d'analyse
+$\mathscr{U},\mathscr{V}$ de mots $u,v\in L$ tels que $w=auv$.  Ces
+deux cas sont évidemment incompatibles : il reste donc simplement à
+expliquer que dans le dernier, $\mathscr{U}$ et $\mathscr{V}$ sont
+uniquement déterminés.  Or la question (3) assure que $u,v$ (tels que
+$w=auv$) sont uniquement déterminés, et l'hypothèse de récurrence
+permet de conclure que les arbres d'analyse $\mathscr{U}$ et
+$\mathscr{V}$ sont uniquement déterminés, comme on le voulait.
+
+(5) Donné un mot $w\in\Sigma^*$, la fonction « rechercher préfixe
+  dans $L$ » suivante renvoie la longueur du préfixe de $w$
+appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas :
+\begin{itemize}
+\item si $w=\varepsilon$, renvoyer échec,
+\item si la première lettre de $w$ est $b$, renvoyer $1$,
+\item sinon (la première lettre de $w$ est $a$), soit $x$ le suffixe
+  de $w$ correspondant (c'est-à-dire $w = ax$, ou si on préfère, $x$
+  enlève la première lettre de $w$),
+\item appeler la fonction elle-même (rechercher préfixe dans $L$)
+  sur $x$ :
+\item si elle échoue, renvoyer échec,
+\item si elle retourne $k$, soit $u$ le préfixe de $y$ de longueur
+  $k$, et $z$ le suffixe correspondant (c'est-à-dire $y = ux$, ou si
+  on préfère, $y$ enlève les $k$ premières lettres de $x$),
+\item appeler la fonction elle-même (rechercher préfixe dans $L$)
+  sur $y$ :
+\item si elle échoue, renvoyer échec,
+\item si elle retourne $\ell$, retourner $1+k+\ell$ (en effet, on a $w
+  = auvz$ où $u$ est de longueur $k$ et $v$ est de longueur $\ell$).
+\end{itemize}
+
+Pour savoir si un mot appartient à $w$, il s'agit simplement de
+vérifier que la valeur retournée (=la longueur du préfixe appartenant
+à $L$) n'est pas un échec et est égale à la longueur $|w|$.
+
+La terminaison de cet algorithme est claire par récurrence sur la
+longueur (chaque appel récursif est fait sur un mot de longueur
+strictement plus courte), et sa correction est garantie par les
+questions précédentes : les cas $b$ et $auv$ sont disjoints et dans le
+dernier cas, $u$ et $v$ sont uniquement déterminés (c'est ce
+qu'affirme la non-ambiguïté de la grammaire).
+
+(Il s'agit ici du cas le plus simple d'un analyseur LL, et
+l'algorithme présenté ci-dessus est essentiellement un analyseur LL
+camouflé sous forme d'analyseur par descente récursive.)
+\end{corrige}
+
+
+
+%
+%
+%
+
+\bigbreak
 \centerline{\textbf{Calculabilité}}
 
 \exercice