summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-30 17:25:07 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-30 17:25:07 +0100
commita06f5fa43d0fc4b7e7663bc7fa370796209627cd (patch)
treec119c3af42448827b913e113bc3c298201d28bab /exercices3.tex
parentf31bfc5920019f52db8ead517b705c50ec08d7aa (diff)
downloadinf105-a06f5fa43d0fc4b7e7663bc7fa370796209627cd.tar.gz
inf105-a06f5fa43d0fc4b7e7663bc7fa370796209627cd.tar.bz2
inf105-a06f5fa43d0fc4b7e7663bc7fa370796209627cd.zip
Re-read exercises.
Diffstat (limited to 'exercices3.tex')
-rw-r--r--exercices3.tex85
1 files changed, 48 insertions, 37 deletions
diff --git a/exercices3.tex b/exercices3.tex
index c2f41cb..7ebae19 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -106,9 +106,9 @@ $a{*}(baa{*}){*}$. Cet automate est-il déterministe ?
(2) En éliminer les transitions spontanées.
-(3) Déterminiser l'automate obtenu.
+(3) Déterminiser l'automate obtenu (on demande un automate complet).
-(4) Minimiser l'automate obtenu.
+(4) Minimiser l'automate obtenu (on demande un automate complet).
(5) Vérifier le résultat en décrivant en français le langage dénoté
par l'expression rationnelle initiale et reconnu par l'automate
@@ -179,16 +179,17 @@ les ε-fermetures $C(q)$ de ces états sont les suivantes :
$q$&ε-fermeture $C(q)$\\
\hline
$0$&$\{0,1,3,4,5,13\}$\\
-$2$&$\{2,3,4,5,13\}$\\
+$2$&$\{1,2,3,4,5,13\}$\\
$6$&$\{6,7\}$\\
$8$&$\{5,8,9,10,12,13\}$\\
$11$&$\{5,10,11,12,13\}$\\
\end{tabular}
\end{center}
-En remplaçant chaque transition $q^\sharp \to q'$ étiquetée par $x$
-dans l'automate par une transition $q\to q'$ pour chaque état $q$ tel
-que $q^\sharp \in C(q)$, on obtient le NFA suivant :
+En remplaçant chaque transition $q^\sharp \to q'$ étiquetée
+d'un $x\in\Sigma$ dans l'automate par une transition $q\to q'$ pour
+chaque état $q$ tel que $q^\sharp \in C(q)$, on obtient le NFA
+suivant :
\begin{center}
%%% begin ex3p1b %%%
@@ -307,10 +308,10 @@ l'alphabet $\Sigma = \{a,b\}$ :
%%% end ex3p2 %%%
\end{center}
(On pourra considérer les ordres suivants d'élimination des états :
-d'abord $2,1,0$, ensuite $1,2,0$ et enfin $0,2,1$.)
+(A) $2,1,0$, ensuite (B) $1,2,0$ et enfin (C) $0,2,1$.)
\begin{corrige}
-Si on commence par éliminer l'état $2$ (en considérant l'automate
+(A) Si on commence par éliminer l'état $2$ (en considérant l'automate
comme un automate à transitions étiquetées par des expressions
rationnelles), l'état $1$ reçoit une transition vers lui-même
étiquetée $ab{*}a$. Si on élimine l'état $1$, l'état $0$ reçoit à la
@@ -325,7 +326,9 @@ obtient finalement l'expression rationnelle
(a|b(ab{*}a){*}b){*}
\]
-Si on commence par éliminer l'état $1$, il apparaît une transition
+\smallbreak
+
+(B) Si on commence par éliminer l'état $1$, il apparaît une transition
$0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut
appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas
de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter
@@ -345,7 +348,9 @@ une seule étiquetée par $a|b(a(b|aa){*}a){*}b$. On obtient finalement
(en particulier, cette expression est équivalente à celle obtenue
précédemment).
-Si on préfère commencer par éliminer l'état $0$, il faut au préalable
+\smallbreak
+
+(C) Si on préfère commencer par éliminer l'état $0$, il faut au préalable
ajouter un nouvel état initial $I$ (conduisant à $0$ par une
transition spontanée) et un nouvel état final $F$ (vers lequel $0$
conduit par une transition spontanée). L'élimination de l'état $0$
@@ -392,7 +397,7 @@ auv$.
\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 =
+mot qui n'appartient jamais à $L$. (Indication : si on a $auvz =
au'v'$ on pourra considérer les cas (i) $|u'|>|u|$, (ii) $|u'|<|u|$ et
(iii) $|u'|=|u|$.)
@@ -406,10 +411,11 @@ 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)).
+$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)) ou bien
+« échec » s'il n'existe pas ; expliquer comment s'en servir pour
+décider si $w\in L$ (i.e., écrire une fonction qui répond vrai ou faux
+selon que $w\in L$ ou $w\not\in L$).
\begin{corrige}
(0) Quelques exemples de mots dans $L$ sont $b$, $abb$, $aabbb$,
@@ -417,17 +423,17 @@ $w\in\Sigma^*$, renvoie la longueur du préfixe de $w$ appartenant
(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
+ selon l'une des deux règles de la grammaire, soit $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$.
+ 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},
@@ -490,8 +496,9 @@ 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.
+permet de conclure (comme $|u|<|w|$ et $|v|<|w|$) que les arbres
+d'analyse $\mathscr{U}$ et $\mathscr{V}$ de $u$ et $v$ sont uniquement
+déterminés, comme on le voulait.
\smallbreak
@@ -507,8 +514,8 @@ appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas :
\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
+\item si elle retourne $k$, soit $u$ le préfixe de $x$ de longueur
+ $k$, et $y$ le suffixe correspondant (c'est-à-dire $x = uy$, 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$ :
@@ -529,7 +536,7 @@ 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
+l'algorithme présenté ci-dessus est essentiellement un analyseur LL(1)
camouflé sous forme d'analyseur par descente récursive.)
\end{corrige}
@@ -658,7 +665,7 @@ de l'arrêt.)
allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$
facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour
$0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$
- commençant à la position $\ell i$) : s'ils sont tous égaux, renvoyer
+ commençant à la position $i \ell$) : s'ils sont tous égaux, renvoyer
vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne,
renvoyer faux. Le langage proposé est donc décidable (et \textit{a
fortiori} semi-décidable).
@@ -684,7 +691,11 @@ de l'arrêt.)
considéré. Or donnés deux entiers $(e,n)$, on peut fabriquer un
programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette
valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus
- un tel $e'$ se calcule algorithmiquement à partir de $e$ et $n$.
+ un tel $e'$ se calcule algorithmiquement\footnote{Techniquement, on
+ invoque ici le théorème s-m-n ; mais dans les faits, il s'agit
+ essentiellement d'ajouter une ligne « \texttt{let
+ n=}(représentation décimale de $n$) » au début d'un programme,
+ ce qui est certainement faisable.} à partir de $e$ et $n$.
L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle
autre entrée) se comporte donc comme l'exécution du programme $e$
sur l'entrée $n$, et notamment, termine si et seulement si elle
@@ -695,7 +706,7 @@ de l'arrêt.)
décidable, le problème de l'arrêt le serait, ce qui n'est pas le
cas. Donc $A$ n'est pas décidable. En revanche, $A$ est
semi-décidable : il suffit de lancer l'exécution du programme $e$
- sur l'entrée $42$ et renvoyer vrai si ele termine (si elle ne
+ sur l'entrée $42$ et renvoyer vrai si elle termine (si elle ne
termine pas, on ne termine pas).
\end{corrige}
@@ -718,8 +729,8 @@ factoriser en mots de longueur non nulle).
(B) Montrer que si deux langages $L_1$ et $L_2$ sont semi-décidables,
alors $L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont
-semi-décidables ; montrer que si un langage $L$ est décidable alors
-$L^*$ est semi-décidable.
+semi-décidables ; montrer que si un langage $L$ est semi-décidable
+alors $L^*$ est semi-décidable.
\begin{corrige}
(A) Supposons qu'on dispose d'algorithmes $T_1$ et $T_2$ qui décident
@@ -756,7 +767,7 @@ facteurs $k$ allant de $1$ à $n$, et, pour chaque $k$, effectuer $k$
boucles emboîtées pour déterminer les limites des facteurs
$u_1,\ldots,u_k \in \Sigma^+$ tels que $w = u_1\cdots u_k$ (il suffit
par exemple de faire boucler $i_1,\ldots,i_k$ chacun de $1$ à $n$, et
-lorsque $i_1+\cdots+i_k = n$, appaler $u_j$ le facteur de $w$ de
+lorsque $i_1+\cdots+i_k = n$, appeler $u_j$ le facteur de $w$ de
longueur $i_j$ commençant à la position $i_1+\cdots+i_{j-1}$). Pour
chaque factorisation comme on vient de le dire, on teste si tous les
$u_i$ appartiennent à $L$, et si c'est le cas on renvoie vrai (le mot
@@ -772,12 +783,12 @@ encore factorisable en mots non vides de $L$.)
(B) Les algorithmes sont très semblables à ceux de la partie (A) si ce
n'est qu'il faut tenir compte de la possibilité qu'ils puissent ne pas
-terminer. On doit donc les lancer « en parallèle » et pas « en
- série » : lorsqu'on dira qu'on lance deux algorithmes $T$ et $T'$
-« en parallèle », cela signifie qu'on exécute une étape du calcul de
-$T$, puis une étape de $T'$, puis de nouveau une de $T$, et ainsi de
-suite en alternant entre les deux, jusqu'à ce que l'un termine et
-renvoie vrai.
+terminer. À part pour l'intersection, on doit donc les lancer « en
+parallèle » et pas « en série » : lorsqu'on dira qu'on lance deux
+algorithmes $T$ et $T'$ « en parallèle », cela signifie qu'on exécute
+une étape du calcul de $T$, puis une étape de $T'$, puis de nouveau
+une de $T$, et ainsi de suite en alternant entre les deux, jusqu'à ce
+que l'un termine et renvoie vrai.
Si $L_1$ et $L_2$ sont semi-dédicables et si $T_1$ et $T_2$ sont des
algorithmes qui les « semi-décident » (i.e., $T_i$ termine en temps