diff options
| -rw-r--r-- | controle-20190205.tex | 57 |
1 files changed, 31 insertions, 26 deletions
diff --git a/controle-20190205.tex b/controle-20190205.tex index c975ab4..6007848 100644 --- a/controle-20190205.tex +++ b/controle-20190205.tex @@ -156,7 +156,8 @@ manière seront plus lourdement sanctionnées.) (1) Traiter l'une \emph{ou} l'autre des questions suivantes : (i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ; (ii) construire l'automate de Thompson de $r$, puis éliminer les -transitions spontanées de ce dernier : on appellera $\mathscr{A}_1$ +transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on +retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$ l'automate ainsi obtenu. (Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant @@ -551,15 +552,14 @@ que $w$, d'après l'hypothèse de récurrence ils vérifient (A) et (B), si bien que $w$ vérifie aussi (A) et (B) d'après la question (4). \end{corrige} -(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B). +(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B). \quad (6.1) Montrer qu'on peut écrire $w = av$ pour un certain $v \in -\Sigma^*$. (6.2) Si $w'$ est le plus long préfixe de $v$ +\Sigma^*$.\quad (6.2) Si $w'$ est le plus long préfixe de $v$ vérifiant (B)\footnote{Autrement dit, le plus long préfixe $w'$ de $v$ tel que pour tout préfixe $u'$ de $w'$ (y compris $w'$ lui-même) on ait $|u'|_b\leq |u'|_a$.}, montrer qu'on a $w = aw'bw''$ pour un -certain $w'' \in \Sigma^*$. (6.3) Montrer que $w'$ vérifie (B). -(6.4) Montrer que $w'$ vérifie (A). (6.5) Montrer que $w''$ vérifie -(A) et (B). +certain $w'' \in \Sigma^*$.\quad (6.3) Montrer que $w'$ vérifie (A). +\quad (6.4) Montrer que $w''$ vérifie (A) et (B). \begin{corrige} (6.1) Comme $w$ est un mot non vide, on peut parler de sa première @@ -579,23 +579,21 @@ vérifie $|va|_b = |v|_b \leq |v|_a < |va|_a$) : on peut donc écrire $v = w'bw''$ pour un certain $w''\in\Sigma^*$, c'est-à-dire $w = aw'bw''$. -(6.3) Le mot $w'$ vérifie (B) : en effet, si $u'$ est préfixe de $w'$ alors -$au'$ en est un de $w$, et on a $|u'|_b = |au'|_b \leq |au'|_a = -1+|u'|_a$. (6.4) Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est -pas le cas, comme $|w'|_b \leq |w'|_a$ (par (B), qu'on vient de -montrer), on a $|w'|_b < |w'|_a$, mais alors $|w'b|_b = |w'|_b + 1 -\leq |w'|_a = |w'b|_a$ donc $w'b$ vérifie encore (B), ce qui contredit -le fait que $w'$ était \emph{le plus long} préfixe de $v$ -vérifiant (B). (6.5) Le mot $w''$ vérifie (A) : en effet, on a $|w|_b = -|w|_a$ (puisque $w$ vérifie (A)), c'est-à-dire $|w'|_b + |w''|_b + 1 = -|w'|_a + |w''|_a + 1$, et comme on vient de voir que $|w'|_b = -|w'|_a$, on a aussi $|w''|_b = |w''|_a$. Enfin, le mot $w''$ -vérifie (B) : en effet, si $u''$ est un préfixe de $w''$ alors -$aw'bu''$ est un préfixe de $w = aw'bw''$ donc (puisque $w$ -vérifie (B)) on a $|aw'bu''|_b \leq |aw'bu''|_a$, c'est-à-dire $|w'|_b -+ |u''|_b + 1 \leq |w'|_a + |u''|_a + 1$ donc (toujours puisque -$|w'|_b = |w'|_a$ qu'on vient de voir) $|u''|_b \leq |u''|_a$ comme -annoncé. +(6.3) Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est pas le +cas, comme $|w'|_b \leq |w'|_a$ (par (B), que vérifie $w'$), on a +$|w'|_b < |w'|_a$, mais alors $|w'b|_b = |w'|_b + 1 \leq |w'|_a = +|w'b|_a$ donc $w'b$ vérifie encore (B), ce qui contredit le fait que +$w'$ était \emph{le plus long} préfixe de $v$ vérifiant (B). + +(6.4) Le mot $w''$ vérifie (A) : en effet, on a $|w|_b = |w|_a$ +(puisque $w$ vérifie (A)), c'est-à-dire $|w'|_b + |w''|_b + 1 = |w'|_a ++ |w''|_a + 1$, et comme on vient de voir que $|w'|_b = |w'|_a$, on a +aussi $|w''|_b = |w''|_a$. Enfin, le mot $w''$ vérifie (B) : en +effet, si $u''$ est un préfixe de $w''$ alors $aw'bu''$ est un préfixe +de $w = aw'bw''$ donc (puisque $w$ vérifie (B)) on a $|aw'bu''|_b \leq +|aw'bu''|_a$, c'est-à-dire $|w'|_b + |u''|_b + 1 \leq |w'|_a + |u''|_a ++ 1$ donc (toujours puisque $|w'|_b = |w'|_a$ qu'on vient de voir) +$|u''|_b \leq |u''|_a$ comme annoncé. \end{corrige} (7) Déduire des questions (2) et (6) que tout mot vérifiant (A) et (B) @@ -671,16 +669,21 @@ $H$ des couples\footnote{Pour être rigoureux, on a fixé un codage proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme (=algorithme) $e$ et d'une entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$ termine en temps fini. On a vu en -cours que $H$ était semi-décidable mais non décidable. +cours que $H$ était semi-décidable mais non décidable\footnote{Une + variante consiste à considérer l'ensemble des $e$ tels que $e$ + termine sur l'entrée $e$ : l'ensemble $H$ qu'on vient de définir s'y + ramène facilement.}. On considère l'ensemble $H'$ des triplets $(e_1,e_2,x)$ tels que $(e_1,x) \in H$ \emph{ou bien} $(e_2,x) \in H$ (ou les deux). Autrement dit, au moins l'un des programmes $e_i$ termine en temps fini quand on l'exécute sur l'entrée $x$. -(1) Montrer que $H'$ est semi-décidable. +(1) L'ensemble $H'$ est-il semi-décidable ? \begin{corrige} +Nous allons montrer que $H'$ est semi-décidable. + Considérons l'algorithme suivant : donné en entrée un triplet $(e_1,e_2,x)$, on exécute en parallèle, en fournissant à chacun l'entrée $x$, les programmes (codés par) $e_1$ et $e_2$ (au moyen @@ -690,9 +693,11 @@ algorithme termine (en renvoyant « vrai ») si et seulement si $(e_1,e_2,x) \in H'$, ce qui montre que $H'$ est semi-décidable. \end{corrige} -(2) Montrer que $H'$ n'est pas décidable. +(2) L'ensemble $H'$ est-il décidable ? \begin{corrige} +Nous allons montrer que $H'$ n'est pas décidable. + Supposons par l'absurde qu'il existe un algorithme $T$ qui décide $H'$. Soit $e'$ (le code d')un programme quelconque qui effectue une boucle infinie (quelle que soit son entrée) : comme $e'$ |