From 56f7f6f0e632baeffcc6116b4cd0a91b5e29c3ad Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 30 Jan 2017 15:56:11 +0100 Subject: Exercise on non-ambiguity and analysis of a simple context-free grammar. --- exercices3.tex | 161 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 161 insertions(+) (limited to 'exercices3.tex') diff --git a/exercices3.tex b/exercices3.tex index a58974b..a2fa873 100644 --- a/exercices3.tex +++ b/exercices3.tex @@ -355,6 +355,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} + + + % % % -- cgit v1.2.3