summaryrefslogtreecommitdiffstats
path: root/controle-20170207.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-02-02 00:11:04 +0100
committerDavid A. Madore <david+git@madore.org>2017-02-05 12:40:09 +0100
commit3bdb816d69bd10766944867297e2ca2fe769f182 (patch)
tree4bc232571e16b1d67241fec72f078fd5f37e8715 /controle-20170207.tex
parentaac882346c69c3576e7e2ebc230bf89fde67f0e6 (diff)
downloadinf105-3bdb816d69bd10766944867297e2ca2fe769f182.tar.gz
inf105-3bdb816d69bd10766944867297e2ca2fe769f182.tar.bz2
inf105-3bdb816d69bd10766944867297e2ca2fe769f182.zip
Take into account Antoine's remarks, rework the end of the third exercise.
Diffstat (limited to 'controle-20170207.tex')
-rw-r--r--controle-20170207.tex137
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