summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
diff options
context:
space:
mode:
Diffstat (limited to 'exercices3.tex')
-rw-r--r--exercices3.tex46
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