From dcd703cb2963926ac1528859fcf20652fefeea7f Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 27 Jan 2017 14:44:04 +0100 Subject: Union, intersection, concatenation and star of decidable vs. semi-decidable languages. --- exercices3.tex | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 97 insertions(+) diff --git a/exercices3.tex b/exercices3.tex index eb19a9f..4964c05 100644 --- a/exercices3.tex +++ b/exercices3.tex @@ -88,6 +88,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} + % % % -- cgit v1.2.3