Union, intersection, concatenation and star of decidable vs. semi-decidable languages.

1 files changed, 97 insertions, 0 deletions

diff --git a/exercices3.tex b/exercices3.tex
index eb19a9f..4964c05 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -94,6 +94,103 @@ Git: \input{vcline.tex}
 
 \exercice
 
+Soit $\Sigma$ un alphabet (i.e., un ensemble fini).  On s'intéresse à
+des langages sur $\Sigma$.
+
+(A) Montrer que si deux langages $L_1$ et $L_2$ sont décidables, alors
+$L_1\cup L_2$ et $L_1\cap L_2$ et $L_1 L_2$ sont décidables ; montrer
+que si un langage $L$ est décidable alors $L^*$ est décidable (pour ce
+dernier, on pourra commencer par chercher, si $w \in \Sigma^*$ est un
+mot de longueur $n$, comment énumérer toutes les façons de le
+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.
+
+\begin{corrige}
+(A) Supposons qu'on dispose d'algorithmes $T_1$ et $T_2$ qui décident
+  $L_1$ et $L_2$ respectivement (i.e., donné $w \in \Sigma^*$,
+  l'algorithme $T_i$ termine toujours en temps fini, en répondant oui
+  si $w\in L_i$ et non si $w\not\in L_i$).
+
+Pour faire un algorithme qui décide $L_1\cup L_2$, donné un mot
+$w\in\Sigma^*$, il suffit de lancer successivement $T_1$ et $T_2$ : si
+l'un des deux répond oui, on répond oui, sinon on répond non
+(autrement dit, on calcule les valeurs de vérité de $w\in L_1$ et
+$w\in L_2$ au moyen de $T_1$ et $T_2$, et on calcule ensuite leur
+« ou » logique).  De même pour décider $L_1\cap L_2$, il suffit de
+lancer successivement $T_1$ et $T_2$, si les deux répondent oui on
+répond oui, sinon on répond non (i.e., on calcule les valeurs de
+vérité de $w\in L_1$ et $w\in L_2$ au moyen de $T_1$ et $T_2$, et on
+calcule ensuite leur « et » logique).
+
+Pour décider $L_1 L_2$, on effectue une boucle sur toutes les
+factorisation $w = uv$ de $w$, c'est-à-dire, une boucle sur toutes les
+longueurs $0\leq i\leq |w|$ en appelant à chaque fois $u$ le préfixe
+de $w$ de longueur $i$ et $v$ le suffixe de $w$ de longueur $|w|-i$,
+et pour chaque paire $(u,v)$ ainsi trouvée, on utilise $T_1$ et $T_2$
+pour tester si $u\in L_1$ et $v\in L_2$ : si c'est le cas, on termine
+l'algorithme en répondant oui (on a $w = uv \in L_1 L_2$) ; si aucune
+paire ne convient, on répond non.
+
+L'algorithme pour décider $L^*$ est semblable : il s'agit de tester
+toutes les manières de factoriser un mot $w \in \Sigma^*$ en facteurs
+de longueur non nulle.  (On peut d'ores et déjà exclure
+$w=\varepsilon$ car le mot vide appartient de toute façon à $L^*$.)
+Si $n=|w| > 0$, on peut effectuer une boucle pour un nombre de
+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
+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
+$w$ appartient à $L^*$) ; si aucune factorisation ne convient, on
+renvoie faux.
+
+(Dans l'algorithme qui précède, on a écarté les factorisations faisant
+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$.)
+
+(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.
+
+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
+fini et répond oui si $w\in L_i$, et ne termine pas sinon), pour
+semi-décider $L_1\cup L_2$, on lance les deux algorithmes $T_1$ et
+$T_2$ en parallèle sur le même mot $w$ : si l'un d'eux termine, on
+termine en renvoyant vrai (sinon, bien sûr, on ne termine pas).
+
+Pour semi-décider $L_1\cap L_2$, en revanche, il n'y a pas de raison
+de procéder en parallèle : on lance d'abord $T_1$ sur le mot $w$ à
+tester : si $T_1$ termine, on lance ensuite $T_1$ sur le même mot : si
+$T_2$ termine et renvoie vrai, on renvoie vrai ; si l'un des deux
+algorithmes $T_i$ lancés séquentiellement ne termine pas, bien sûr, le
+calcul dans son ensemble ne terminera pas.
+
+Pour semi-décider $L_1 L_2$ ou $L^*$, on procède comme dans le cas (A)
+en lançant en parallèle les algorithmes pour tester toutes les
+différentes factorisations possibles $w = uv$ ou bien $w = u_1\cdots
+u_k$ (en mots non vides) du mot $w$.
+\end{corrige}
+
+%
+%
+%
+
+\exercice
+
 On rappelle qu'une fonction $f\colon \mathbb{N} \to \mathbb{N}$ est
 dite \emph{calculable} lorsqu'il existe un algorithme (par exemple, un
 programme pour une machine de Turing) prenant en entrée un