diff options
| -rw-r--r-- | exercices3.tex | 85 |
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 |