diff options
| -rw-r--r-- | exercices3.tex | 46 |
1 files changed, 39 insertions, 7 deletions
diff --git a/exercices3.tex b/exercices3.tex index 9774b3a..c2f41cb 100644 --- a/exercices3.tex +++ b/exercices3.tex @@ -27,6 +27,8 @@ \refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% \refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} +\newcommand\exercicenobreak{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}} \renewcommand{\qedsymbol}{\smiley} % \newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax} @@ -92,10 +94,10 @@ Git: \input{vcline.tex} % % -\bigbreak +\bigskip \centerline{\textbf{Langages rationnels et automates}} - -\exercice +\penalty8000 +\exercicenobreak Soit $\Sigma = \{a,b\}$. @@ -166,6 +168,8 @@ finalement obtenu. Cet automate n'est pas déterministe : un automate comportant des ε-transitions est forcément non-déterministe. +\smallbreak + (2) Tous les états autres que $0$ (car il est initial) et $2,6,8,11$ (car des transitions non spontanées y aboutissent) vont disparaître ; les ε-fermetures $C(q)$ de ces états sont les suivantes : @@ -214,6 +218,8 @@ que $q^\sharp \in C(q)$, on obtient le NFA suivant : Les états $0,2,8,11$ sont finaux car ce sont eux qui ont $13$ dans leur ε-fermeture. +\smallbreak + (3) L'automate ainsi obtenu est déjà déterministe incomplet ; pour le déterminiser-compléter, il n'y a qu'à ajouter un puits $\bot$ avec la seule transition qui manque, c'est-à-dire une transition étiquetée par @@ -221,6 +227,8 @@ $b$ depuis l'état $6$ (et des transitions de $\bot$ vers lui-même étiquetées $a$ et $b$). Nous ne représentons pas l'automate à $6$ états ainsi fabriqué. +\smallbreak + (4) On part de l'algorithme déterministe complet obtenu à la question (3), et on lui applique l'algorithme de minimisation. On sépare d'abord ses états en deux classes, les finaux $\{0,2,8,11\}$ et @@ -249,6 +257,8 @@ $\{6,\bot\}$. On vérifie ensuite qu'aucune transition ne sépare des \end{center} où l'état $F$ représente la classe $0\equiv 2\equiv 8\equiv 11$. +\smallbreak + (5) Il s'agit du langage constitué des mots n'ayant jamais deux $b$ consécutifs ni de $b$ final, c'est-à-dire des mots dans lesquels chaque $b$ est suivi @@ -359,10 +369,11 @@ a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*} % % -\bigbreak +\penalty-2000\vskip24ptplus600ptminus12pt \centerline{\textbf{Langages algébriques et grammaires hors contexte}} +\penalty8000 -\exercice +\exercicenobreak On considère la grammaire hors contexte $G$ suivante (d'axiome $S$) sur l'alphabet $\Sigma = \{a,b\}$ : @@ -425,6 +436,8 @@ et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U}, $a,S,S$, ces deux derniers ayant pour descendants des sous-arbres donnés par $\mathscr{U}$ et $\mathscr{V}$. +\smallbreak + (2) Montrons par récurrence sur $|w|$ que si $w \in L$ alors on a $wz \not\in L$ pour tout $z \in \Sigma^+$. La récurrence permet de supposer la conclusion déjà connue pour tout mot de longueur $<|w|$. @@ -449,6 +462,8 @@ longueur du même mot $uvz = u'v'$), et on a alors $v' = vz$, mais comme $v\in L$, l'hypothèse de récurrence entraîne $v'\not\in L$, encore une contradiction. +\smallbreak + (3) Montrons que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$ et $v=v'$. On a notamment $uv = u'v'$. Distinguons trois cas : (i) soit $|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$, @@ -461,6 +476,8 @@ L$, de nouveau une contradiction ; (iii) soit $|u'|=|u|$, donc $u'=u$ (puisqu'ils sont préfixes de même longueur du même mot $uv = u'v'$), et on a alors $v' = v$, la conclusion annoncéee. +\smallbreak + (4) Soit $w \in L$ : on veut montrer qu'il a un unique arbre d'analyse pour $G$. On procède par récurrence sur $|w|$, ce qui permet de supposer la conclusion connue pour tout mot de longueur $<|w|$. Comme @@ -476,6 +493,8 @@ $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. +\smallbreak + (5) Donné un mot $w\in\Sigma^*$, la fonction « rechercher préfixe dans $L$ » suivante renvoie la longueur du préfixe de $w$ appartenant à $L$, ou bien « échec » si ce préfixe n'existe pas : @@ -575,6 +594,8 @@ que $G$. \end{center} et son symétrique par rapport à l'axe vertical. +\smallbreak + (2) Montrons que $L$ est égal au langage $L_{(ba){*}b}$ dénoté par l'expression rationnelle $(ba){*}b$ comme la question (0) le laisse entrevoir. Pour cela, il suffit de voir que l'ensemble des @@ -593,6 +614,8 @@ produire n'importe quel nombre $n$ de répéritions du motif $aS$ en appliquant $n$ fois la règle $S\rightarrow SaS$ à partir de $S$, et on peut ensuite librement transformer certains $S$ en $b$. +\smallbreak + (3) La grammaire $G'$ donnée par $S \rightarrow baS\,|\,b$ engendre le même langage que $G$ d'après la question précédente ; et il est évident que cette grammaire est inambiguë : toutes les dérivations @@ -606,10 +629,11 @@ sont de la forme $S \Rightarrow baS \Rightarrow babaS \Rightarrow % % -\bigbreak +\penalty-2000\vskip24ptplus600ptminus12pt \centerline{\textbf{Calculabilité}} +\penalty8000 -\exercice +\exercicenobreak (1) Soit $\Sigma$ un alphabet (i.e., un ensemble fini). L'ensemble $L = \{u^k : u\in\Sigma^*, k\geq 2\}$ des mots qui sont une puissance @@ -639,6 +663,8 @@ de l'arrêt.) renvoyer faux. Le langage proposé est donc décidable (et \textit{a fortiori} semi-décidable). +\smallbreak + (2) Donné un $e \in \mathbb{N}$, la fonction $10^{1000+e}$ est évidemment calculable. On peut ensuite lancer l'exécution du $e$-ième programme, sur l'entrée $42$, pour au plus ce nombre @@ -648,6 +674,8 @@ de l'arrêt.) vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé est bien décidable (et \textit{a fortiori} semi-décidable). +\smallbreak + (3) L'ensemble $A$ proposé est « presque » le problème de l'arrêt. La différence est que le problème de l'arrêt est l'ensemble des couples $(e,n)$ tels que le $e$-ième programme termine sur l'entrée $n$ @@ -740,6 +768,8 @@ intervenir le mot vide, car si $w$ est factorisable en mots de $L$ en faisant intervenir le mot vide, quitte à retirer celui-ci, il est encore factorisable en mots non vides de $L$.) +\smallbreak + (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 @@ -831,6 +861,8 @@ $p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition de $T$. +\smallbreak + Reste à montrer que (3) implique (1) : supposons qu'on ait un algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$, termine en temps fini et répond oui si $p=f(n)$, et ne termine pas |