diff options
| -rw-r--r-- | controle-20170207.tex | 128 |
1 files changed, 75 insertions, 53 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex index f9a138f..a3637f6 100644 --- a/controle-20170207.tex +++ b/controle-20170207.tex @@ -87,10 +87,15 @@ \noindent\textbf{Consignes.} -Les exercices sont indépendants sauf dans la mesure où le contraire -est précisé. Ils pourront être traités dans un ordre quelconque, mais -on demande de faire apparaître de façon très visible dans les copies -où commence chaque exercice. +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +\medbreak + +Le sujet étant délibérément trop long pour le temps imparti, il sera +possible d'obtenir la totalité des points en ne traitant qu'une partie +des exercices. \medbreak @@ -146,8 +151,8 @@ rationnelle qui le dénote. (On pourra préférer traiter la question (1b) Pour chacun des mots suivants, dire s'ils sont dans $L$ ou non : $\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$. (Note : il est conseillé de réutiliser ces mots pour vérifier -rapidement les réponses aux questions suivantes et ainsi détecter des -erreurs lors des transformations des automates.) +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. (On supprimera les états devenus inutiles.) @@ -161,8 +166,8 @@ haut vers le bas. (4) Minimiser l'automate ainsi obtenu, si nécessaire. -(5) Donner un automate du type qu'on voudra qui reconnaît le langage -$\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$. +(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 complémentaire $\overline{L}$. @@ -292,6 +297,11 @@ de cet automate de la façon suivante : \draw[->] (s22) to[loop below] node[auto]{$b$} (s22); \end{tikzpicture} \end{center} +Ici, l'état $0\bullet$ signifie que l'automate n'a pas rencontré +de $a$, l'état $1\bullet$ qu'il en a rencontré exactement un, et +l'état $2\bullet$ qu'il en a rencontré au moins deux ; les états +$\bullet0$, $\bullet1$ et $\bullet2$ ont la même signification pour la +lettre $b$. \smallbreak @@ -396,7 +406,9 @@ babb{*}a \penalty0\,|\,bbb{*}ab{*}a$ dénote le langage formé des mots comportant au moins deux $b$ et exactement deux $a$ et qui finissent par un $a$ : l'expression du cas (iv) correspond donc à écrire un mot ayant au moins deux $a$ et au moins deux $b$ comme le premier préfixe -qui vérifie cette propriété suivi d'un suffixe quelconque. +qui vérifie cette propriété suivi d'un suffixe quelconque. (On +pouvait utiliser directement ce raisonnement pour produire +l'expression.) \end{corrige} @@ -407,7 +419,7 @@ qui vérifie cette propriété suivi d'un suffixe quelconque. \exercice Soit $\Sigma$ un alphabet (fini, non vide) fixé. Les questions -suivantes sont indépendantes. +suivantes sont indépendantes (mais on remarquera leur parallélisme). (1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe un algorithme $A_1$ qui, donnée une expression rationnelle $r$ @@ -424,9 +436,10 @@ 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 fini en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que -$w\not\in L_G$, et ne pas terminer — ou éventuellement terminer en -répondant « faux » — si $L_G = \Sigma^*$.) Indication : on peut -tester tous les mots possibles. +$w\not\in L_G$, et ne pas terminer\footnote{On peut admettre qu'il + termine parfois en répondant « faux », mais ce ne sera pas utile.} +si $L_G = \Sigma^*$.) Indication : on peut tester tous les mots +possibles. (3) Expliquer pourquoi il existe un tel algorithme $A_3$ : on lui fournit en entrée un algorithme $T$ qui décide un langage $L_T @@ -436,12 +449,11 @@ fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou « vrai »), et l'algorithme $A_3$ doit semi-décider si $L_T$ est différent de $\Sigma^*$. (C'est-à-dire que $A_3$ doit terminer en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in -L_T$, et ne pas terminer — ou éventuellement terminer en répondant -« faux » — si $L_T = \Sigma^*$.) Indication : la même approche permet -de traiter les questions (2) et (3). +L_T$, et ne pas terminer si $L_T = \Sigma^*$.) Indication : la même +approche permet de traiter les questions (2) et (3). -(4) Expliquer pourquoi il n'existe pas d'algorithme $A_4$ qui, dans -les mêmes conditions que $A_3$, décide (au lieu de seulement +(4) Expliquer pourquoi il \emph{n'existe pas} d'algorithme $A_4$ qui, +dans les mêmes conditions que $A_3$, décide (au lieu de seulement semi-décider) si $L_T$ est différent de $\Sigma^*$. (C'est-à-dire que $A_4$ est censé terminer toujours, et répondre « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in L_T$, et « faux » si $L_T = @@ -507,10 +519,10 @@ programme $T$ ne considère que la longueur $|w|$ de $w$, et lance étapes : si l'exécution termine dans le temps imparti, alors $T$ rejette le mot $w$, sinon, il l'accepte (dans tous les cas, $T$ termine et répond « vrai » ou « faux », donc il est une entrée -légitime à $A_4$). Cette construction fait que $L_T$ rejette un mot -précisément lorsque $S$ termine sur $x$ : si au contraire $S$ ne -termine pas sur $x$, alors $L_T = \Sigma^*$. L'utilisation de $A_4$ -sur $T$ permet donc de savoir algorithmiquement si $S$ termine +légitime à $A_4$). Cette construction fait que $L_T$ rejette au moins +un mot précisément lorsque $S$ termine sur $x$ : si au contraire $S$ +ne termine pas sur $x$, alors $L_T = \Sigma^*$. L'utilisation de +$A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt. Variante de la même idée : on appelle « trace d'exécution » de $S$ sur @@ -537,8 +549,9 @@ l'indécidabilité du problème de l'arrêt. \exercice -On considère la grammaire hors-contexte $G$ d'axiome $S$ sur -l'alphabet $\Sigma = \{a,b,c\}$ donnée par +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} S &\rightarrow TS \;|\; \varepsilon\\ @@ -550,29 +563,30 @@ 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). +(0) Donner quelques exemples de mots de $L(G)$ et de $L(G,T)$. + (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)$. (En -particulier, $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 +l'ensemble des mots 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)$ simplement en fonction de $L(G,T)$ ? Y -a-t-il inclusion de l'un dans l'autre ? +(2) Comment décrire $L(G)$ de manière simple en fonction de $L(G,T)$ ? +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 strict -d'un mot $u\in L(G,T)$, alors $|v|_c < |v|_a$. (« Préfixe strict » -signifie que $v$ est un préfixe de $u$ et $v\neq u$. On pourra écrire -$u$ sous la forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ donnée -en (1).) +(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)$. -Montrer aussi que $bz \not\in L(G,T)$. +Expliquer par ailleurs pourquoi $bz \not\in 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. @@ -582,6 +596,11 @@ la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$. (7) En déduire que la grammaire $G$ est inambiguë. \begin{corrige} +(0) Les mots $abc$ et $aabcbc$ et $ababcc$ appartiennent à $L(G,T)$. + Les mots $\varepsilon$ et $abc$ et $abcabc$ appartiennent à $L(G)$. + +\smallbreak + (1) En bref : il s'agit simplement d'une reformulation des règles de la grammaire. En plus détaillé : si on considère un arbre d'analyse d'un mot $w$ de $L(G)$, soit il est la dérivation triviale du mot @@ -596,7 +615,7 @@ la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots u'_\ell$. d'un mot $u$ de $L(G,T)$ est plus simple : son arbre d'analyse donne directement une écriture sous la forme $awbw'c$ avec $w,w'$ les mots analysés par les arbres qui descendent des deux fils étiquetés $S$ - de la racine. + de la racine (étiquetée $T$). \smallbreak @@ -607,11 +626,12 @@ L(G,T)^*$ où « $*$ » est l'étoile de Kleene. (Si on veut, la règle $S \smallbreak -(3) La propriété $|\gamma|_a = |\gamma|_b = |\gamma|_c$ est vérifiée -pour $S$ et elle est préservée par toute dérivation immédiate pour $G$ -puisqu'elle est préservée en remplaçant $S$ par $TS$ ou par le mot -vide et en remplaçant $T$ par $aSbSc$. Elle est donc vérifiée pour -tout mot de $L(G)$ (et en particulier, pour tout mot de $L(G,T)$). +(3) La propriété $|\gamma|_a = |\gamma|_b = |\gamma|_c$ (ici $\gamma +\in (\Sigma\cup N)^*$) est vérifiée pour $\gamma = S$ et elle est +préservée par toute dérivation immédiate pour $G$ puisqu'elle est +préservée en remplaçant $S$ par $TS$ ou par le mot vide et en +remplaçant $T$ par $aSbSc$. Elle est donc vérifiée pour tout mot de +$L(G)$ (et en particulier, pour tout mot de $L(G,T)$). \smallbreak @@ -619,22 +639,24 @@ tout mot de $L(G)$ (et en particulier, pour tout mot de $L(G,T)$). propriété déjà connue pour tout préfixe $v$ d'un mot de longueur strictement plus courte que $u$. Si $v$ est un préfixe d'un mot $u \in L(G,T)$, qu'on peut écrire sous la forme $u = a u_1 \cdots u_k b -u'_1\cdots u'_{\ell} c$, on a soit $v = a u_1 \cdots u_{i-1} y$ où $y$ -est un préfixe de $u_i$, soit $v = a u_1\cdots u_k b u'_1\cdots -u'_{i-1} y$ où $y$ est un préfixe de $u'_i$. Dans tous les cas, tous -les 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$ est un préfixe strict de $u_i$ -resp. $u'_i$) soit par de question (3) (lorsque $y$ est en fait égal à -$u_i$ resp. $u'_i$). Comme par ailleurs $|a|_c = 0 < 1 = |a|_a$, une +u'_1\cdots u'_{\ell} c$, et si $0<|v|<|u|$, on a soit $v = a u_1 +\cdots u_{i-1} y$ où $y \neq \varepsilon$ est un préfixe de $u_i$, +soit $v = a u_1\cdots u_k b u'_1\cdots u'_{i-1} y$ où $y \neq +\varepsilon$ est un préfixe de $u'_i$. Dans tous les cas, tous les +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$ +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)$ (car 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)). +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 |