diff options
| -rw-r--r-- | controle-20170207.tex | 137 |
1 files changed, 79 insertions, 58 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex index 7d6a2bc..1d42a3e 100644 --- a/controle-20170207.tex +++ b/controle-20170207.tex @@ -93,8 +93,8 @@ très visible dans les copies où commence chaque exercice. \medbreak -Le sujet étant long pour le temps imparti, il ne sera nécessaire de -traiter toutes les questions pour obtenir la totalité des points. +Le sujet étant long pour le temps imparti, il ne sera pas nécessaire +de traiter toutes les questions pour obtenir la totalité des points. \medbreak @@ -107,7 +107,7 @@ L'usage des calculatrices électroniques est interdit. Durée : 1h30 -L'énoncé comporte 4 pages. +L'énoncé comporte 4 pages (page de garde incluse) \pagebreak @@ -155,7 +155,7 @@ $\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$. rapidement les réponses aux questions suivantes et ainsi détecter d'éventuelles erreurs lors des transformations des automates.) -(2) Éliminer les transitions spontanées de l'automate, s'il y en a. +(2) Éliminer les transitions spontanées de l'automate. (On supprimera les états devenus inutiles.) (3) Déterminiser l'automate ainsi obtenu, si nécessaire. (On demande @@ -165,12 +165,12 @@ correcteur, on demande de faire en sorte que les transitions la gauche vers la droite, et celles étiquetées par $b$, verticales du haut vers le bas. -(4) Minimiser l'automate ainsi obtenu, si nécessaire. +(4) Minimiser l'automate ainsi obtenu, si nécessaire (justifier). (5) Donner un automate (de n'importe quelle sorte) qui reconnaît le langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$. -(6) Décrire brièvement, en français, le langage ce langage +(6) Décrire brièvement, en français, ce langage complémentaire $\overline{L}$. (7) (Question bonus, plus longue, à ne traiter qu'en dernier.) Donner @@ -330,9 +330,10 @@ finaux (et les doublement entourés sont non-finaux). \emph{Attention :} échanger états finaux et non-finaux ne marche pas pour reconnaître le complémentaire du langage reconnu par un automate -non-déterministe (car la négation de « il existe un chemin qui va vers -un état final » est « aucun chemin ne va vers un état final » et pas -« il existe un chemin qui va vers un état non-final »). +non-déterministe ou incomplet (car la négation de « il existe un +chemin qui va vers un état final » est « aucun chemin ne va vers un +état final » et pas « il existe un chemin qui va vers un état +non-final »). \smallbreak @@ -422,9 +423,11 @@ l'expression.) Soit $\Sigma$ un alphabet (fini, non vide) fixé. Les questions suivantes sont indépendantes (mais on remarquera leur parallélisme). +Ne pas hésiter à décrire les algorithmes de façon succincte et +informelle. (1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe -un algorithme $A_1$ qui, donnée une expression rationnelle $r$ +un algorithme $A_1$ qui, étant donnée une expression rationnelle $r$ sur $\Sigma$, décide si le langage $L_r$ dénoté par $r$ est différent du langage $\Sigma^*$ de tous les mots sur $\Sigma$. (Autrement dit, l'algorithme $A_1$ doit prendre en entrée une expression rationnelle @@ -432,8 +435,8 @@ $r$, terminer en temps fini, et répondre « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in L_r$ et « faux » si $L_r = \Sigma^*$. On ne demande pas que l'algorithme soit efficace.) -(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, donnée une -grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le +(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, étant donnée +une grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le langage $L_G$ engendré par $G$ est différent du langage $\Sigma^*$ de tous les mots. (« Semi-décider » signifie que l'algorithme $A_2$ doit prendre en entrée une grammaire hors contexte $G$, terminer en temps @@ -551,8 +554,8 @@ l'indécidabilité du problème de l'arrêt. \exercice -On considère la grammaire hors-contexte $G$ d'axiome $S$ (et de -nonterminaux $N = \{S, T\}$) sur l'alphabet $\Sigma = \{a,b,c\}$ +On considère la grammaire hors-contexte $G$ d'axiome $S$ et de +nonterminaux $N = \{S, T\}$ sur l'alphabet $\Sigma = \{a,b,c\}$ donnée par \[ \begin{aligned} @@ -561,7 +564,7 @@ T &\rightarrow aSbSc\\ \end{aligned} \] On notera $L(G) = L(G,S)$ le langage qu'elle engendre, et $L(G,T)$ le -langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère le +langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère, le langage engendré par la grammaire identique à $G$ mais ayant $T$ pour axiome). @@ -570,32 +573,45 @@ moins deux de chaque). (1) Expliquer brièvement pourquoi $L(G)$ est l'ensemble des mots de la forme $u_1\cdots u_k$ avec $u_i \in L(G,T)$, et pourquoi $L(G,T)$ est -l'ensemble des mots la forme $awbw'c$ avec $w,w'\in L(G)$. (Par +l'ensemble des mots de la forme $awbw'c$ avec $w,w'\in L(G)$. (Par conséquent, $L(G,T)$ est l'ensemble des mots de la forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ avec $u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(G,T)$.) -(2) Comment décrire $L(G)$ de en fonction de $L(G,T)$ au moyen des -opérations rationnelles\footnote{C'est-à-dire : union, concaténation, - étoile de Kleene.} ? Y a-t-il inclusion de l'un dans l'autre ? - -(3) Montrer que tout mot $w$ de $L(G)$ a le même nombre de $a$, de $b$ -et de $c$, c'est-à-dire $|w|_a = |w|_b = |w|_c$ où $|w|_x$ désigne le -nombre total d'occurrences de la lettre $x$ dans le mot $w$. - -(4) Montrer par récurrence sur $|u|$ que si $v$ est un préfixe d'un -mot $u\in L(G,T)$ de longueur $0<|v|<|u|$, alors on a $|v|_c < |v|_a$. -(On pourra écrire $u$ sous la forme $a u_1 \cdots u_k b u'_1\cdots -u'_{\ell} c$ obtenue en (1).) - -(5) En déduire que si $u \in L(G,T)$ et $z \in \Sigma^+$ (c'est-à-dire -$z\in\Sigma^*$ et $z\neq\varepsilon$) alors $uz \not\in L(G,T)$. -Expliquer par ailleurs pourquoi $bz \not\in L(G,T)$. +(2) Comment exprimer $L(G)$ à partir de $L(G,T)$ au moyen d'une ou +plusieurs opérations rationnelles\footnote{C'est-à-dire : union, + concaténation, étoile de Kleene.} ? Y a-t-il inclusion de l'un dans +l'autre ? + +(3) Montrer que tout mot $w$ appartenant à $L(G)$ ou à $L(G,T)$ a le +même nombre de $a$, de $b$ et de $c$, c'est-à-dire $|w|_a = |w|_b = +|w|_c$ où $|w|_x$ désigne le nombre total d'occurrences de la +lettre $x$ dans le mot $w$. + +(4) Montrer par récurrence sur la longueur $|u|$ d'un mot $u\in +L(G,T)$ que si $v$ est un préfixe de $u$ de longueur $0<|v|<|u|$, +alors on a $|v|_c < |v|_a$. Pour cela, on pourra écrire $u$ sous la +forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ obtenue en (1), +considérer un préfixe\footnote{\label{prefix-note}On signale à toutes + fins utiles le fait évident suivant : un préfixe non vide de $t_1 + \cdots t_n$ où $t_1,\ldots,t_n \in\Sigma^*$ s'écrit sous la forme + $t_1\cdots t_{i-1} y$ où $y\neq\varepsilon$ est un préfixe + de $t_i$.} d'une telle expression, et appliquer la question (3) et +l'hypothèse de récurrence. + +(5) Déduire des questions (3) et (4) que si $u \in L(G,T)$ et si $v$ +est un préfixe de $u$ autre que $u$ lui-même, alors $u \not\in +L(G,T)$. En déduire que $u\in L(G,T)$ et $z \in \Sigma^*$, alors $u$ +est l'\emph{unique} préfixe du mot $w := uz$ qui appartienne +à $L(G,T)$ (autrement dit, aucun préfixe de $w$ de longueur ${<}|u|$ +ni ${>}|u|$ n'appartient à $L(G,T)$). (6) En déduire que si un mot $w$ s'écrit $w = u_1\cdots u_k$ avec $u_1,\ldots,u_k \in L(G,T)$ alors cette factorisation est unique. -(Comment peut-on définir $u_1$ en fonction de $w$ ?) Montrer de même -la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$. +(Comment peut-on caractériser $u_1$ comme préfixe de $w$ ?) Montrer +de même la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots +u'_\ell$ (on pourra noter que $bz\not\in L(G,T)$ quel que +soit $z\in\Sigma^*$). (7) En déduire que la grammaire $G$ est inambiguë. @@ -610,8 +626,8 @@ la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$. d'un mot $w$ de $L(G)$, soit il est la dérivation triviale du mot vide, soit sa racine a deux fils étiquetés $T$ et $S$, l'un dont descend un arbre d'analyse d'un mot $u_1$ de $L(G,T)$ et l'autre - dont descend arbre d'analyse d'un autre mot $w'$ de $L(G)$, avec $w - = u_1 w'$ : en répétant cette remarque jusqu'à tomber sur le mot + dont descend un arbre d'analyse d'un autre mot $w'$ de $L(G)$, avec + $w = u_1 w'$ : en répétant cette remarque jusqu'à tomber sur le mot vide, on voit que $w = u_1 u_2 \cdots u_k$ pour des mots $u_i \in L(G,T)$ ; et réciproquement, tout mot de cette forme a un arbre d'analyse dans $G$ obtenu en mettant ensemble les arbres d'analyse @@ -651,39 +667,44 @@ facteurs $t$ qui interviennent dans cette écriture vérifient $|t|_c \leq |t|_a$ : c'est trivial pour $a$ et $b$, c'est le cas pour chaque $u_j$ par la question (3), et pour $y$ cela découle soit de l'hypothèse de récurrence (lorsque $|y|<|u_i|$ resp. $|y|<|u'_i|$) -soit par de question (3) (lorsque $y$ est en fait égal à $u_i$ +soit par la question (3) (lorsque $y$ est en fait égal à $u_i$ resp. $u'_i$). Comme par ailleurs $|a|_c = 0 < 1 = |a|_a$, une égalité est stricte et on en déduit $|v|_c < |v|_a$, ce qui conclut la récurrence. -En particulier, on observe pour la question suivante que $v\not\in -L(G,T)$ pour tout préfixe strict $v$ d'un mot de $L(G,T)$ (si $v = -\varepsilon$ c'est clair, et si $0<|v|<|u|$, on vient de montrer -$|v|_c < |v|_a$ alors qu'un mot de $L(G,T)$ vérifie $|u|_c = |u|_a$ -d'après (3)). - \smallbreak -(5) Comme $u$ est un préfixe strict de $uz$, si on avait $uz \in -L(G,T)$ alors la question (4) implique $u\not\in L(G,T)$, une -contradiction : c'est donc que $uz \not\in L(G,T)$. - -Le fait que $bz \not\in L(G,T)$ est trivial car tout mot de $L(G,T)$ -commence par $a$ d'après la question (1). +(5) Si $u \in L(G,T)$ et si $v$ est un préfixe de $u$ autre que $u$ +lui-même, alors soit $v = \varepsilon$, qui n'appartient pas à +$L(G,T)$ (par exemple par la question (1)), soit $0<|v|<|u|$, auquel +cas la question (4) donne $|v|_c<|v|_a$, ce qui interdit $v\in L(G,T)$ +d'après (3). Dans tous les cas, $v\not\in L(G,T)$. + +Si maintenant $u\in L(G,T)$ et $z\in\Sigma^*$, un préfixe de $w := uz$ +est soit un préfixe de $u$ soit de la forme $uz'$ avec $z'$ un préfixe +non vide de $z$ (cf. la note \ref{prefix-note}). Un préfixe de $w$ de +longueur ${<}|u|$ n'appartient pas à $L(G,T)$ d'après le paragraphe +précédent, et un mot de la forme $uz'$ ne peut pas y appartenir non +plus car c'est alors $u$ lui-même qui serait un préfixe strict de $uz' +\in L(G,T)$ appartenant à $L(G,T)$, ce qui contredit de nouveau le +paragraphe précédent. \smallbreak -(6) On peut définir $u_1$ comme l'unique préfixe de $w$ qui appartient -à $L(G,T)$ (tout préfixe strictement plus court ou strictement plus -long n'appartient pas à $L(G,T)$ d'après les questions (4) et (5)). -Une fois que $u_1$ est défini par $w$, en appliquant le même -raisonnement à $u_2\cdots u_k$ et ainsi de suite, on voit que $u_2$ et -les autres sont uniquement définis. +(6) D'après la question précédente, on peut définir $u_1$ comme +l'unique préfixe de $w$ qui appartient à $L(G,T)$ (tout préfixe +strictement plus court ou strictement plus long n'appartient pas à +$L(G,T)$). Une fois que $u_1$ est défini, en appliquant le même +raisonnement au suffixe correspondant $u_2\cdots u_k$, on voit que +$u_2$ est défini de façon unique. En procédant ainsi (par récurrence +sur $k$ si on veut), les $u_i$ sont définis de façon unique. Le même raisonnement vaut pour $u_1\cdots u_k b u'_1\cdots u'_\ell$ : -on a une factorisation en mots de $L(G,T)\cup\{b\}$ et on a vu qu'en -retirant ou en ajoutant des lettres à la fin d'un mot de ce langage on -obtient un mot qui n'est pas dans $L(G,T)\cup\{b\}$. +on a une factorisation en mots de $L(G,T)\cup\{b\}$ et à chaque fois +le premier facteur est défini comme le seul préfixe possible +appartenant à $L(G,T)\cup\{b\}$. (On utilise le fait que $bz\not\in +L(G,T)$, qui découle du (1), pour voir que $bu'_1\cdots bu'_\ell$ n'a +pas de préfixe dans $L(G,T)$.) \smallbreak |