summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
blob: 4964c05f1d9838e19eaaf6118bbfab37c2f54898 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage[hyperindex=false]{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{Exercices divers — Corrigé}
\else
\title{Exercices divers}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

{\footnotesize
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pretolerance=8000
\tolerance=50000



%
%
%

\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
$n\in\mathbb{N}$ qui termine toujours en temps fini et renvoie la
valeur $f(n)$.  On rappelle qu'une partie $E$ de $\mathbb{N}$ ou de
$\mathbb{N}^2$ est dite \emph{décidable} lorsque sa fonction
indicatrice est calculable, ou, ce qui revient au même, lorsqu'il
existe un algorithme prenant en entrée un élément de $\mathbb{N}$ ou
de $\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
vrai ($1$) ou faux ($0$) selon que l'élément fourni appartient ou non
à $E$.  On rappelle enfin qu'une partie $E$ de $\mathbb{N}$ ou de
$\mathbb{N}^2$ est dite \emph{semi-décidable} lorsqu'il existe un
algorithme prenant en entrée un élément de $\mathbb{N}$ ou de
$\mathbb{N}^2$ qui termine toujours en temps fini et renvoie
vrai ($1$) si l'élément fourni appartient à $E$, et sinon ne termine
pas (on peut aussi accepter qu'il termine en renvoyant faux, cela ne
change rien).

Soit $f\colon \mathbb{N} \to \mathbb{N}$ : montrer qu'il y a
équivalence entre les affirmations suivantes :
\begin{enumerate}
\item la fonction $f$ est calculable,
\item le graphe $\Gamma_f := \{(n,f(n)) : n\in\mathbb{N}^2\} =
  \{(n,p)\in\mathbb{N}^2 : p=f(n)\}$ de $f$ est décidable,
\item le graphe $\Gamma_f$ de $f$ est semi-décidable.
\end{enumerate}

(Montrer que (3) implique (1) est le plus difficile : on pourra
commencer par s'entraîner en montrant que (2) implique (1).  Pour
montrer que (3) implique (2), on pourra chercher une façon de tester
en parallèle un nombre croissant de valeurs de $p$ de manière à
s'arrêter si l'une quelconque convient.)

\begin{corrige}
Montrons que (1) implique (2) : si on dispose d'un algorithme capable
de calculer $f(n)$ en fonction de $n$, alors il est facile d'écrire un
algorithme capable de décider si $p=f(n)$ (il suffit de calculer
$f(n)$ avec l'algorithme supposé exister, de comparer avec la valeur
de $p$ fournie, et de renvoyer vrai/$1$ si elles sont égales, et
faux/$0$ sinon).

Le fait que (2) implique (3) est évident car tout ensemble décidable
est semi-décidable.

Montrons que (2) implique (1) même si ce ne sera au final pas utile :
supposons qu'on ait un algorithme $T$ qui décide $\Gamma_f$ (i.e.,
donnés $(n,p)$, termine toujours en temps fini, en répondant oui si
$p=f(n)$ et non si $p\neq f(n)$), et on cherche à écrire un algorithme
qui calcule $f(n)$.  Pour cela, donné un $n$, il suffit de lancer
l'algorithme $T$ successivement sur les valeurs $(n,0)$ puis $(n,1)$
puis $(n,2)$ et ainsi de suite (c'est-à-dire faire une boucle infinie
sur $p$ et lancer $T$ sur chaque couple $(n,p)$) jusqu'à trouver un
$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$.

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
sinon), et on cherche à écrire un algorithme qui calcule $f(n)$.  Pour
cela, on va tester les valeurs $0\leq p\leq M$ chacune pour $M$ étapes
et faire tendre $M$ vers l'infini : plus exactement, on utilise
l'algorithme $U$ suivant :
\begin{itemize}
\item pour $M$ allant de $0$ à l'infini,
\begin{itemize}
\item pour $p$ allant de $0$ à $M$,
\begin{itemize}
\item exécuter l'algorithme $T$ sur l'entrée $(n,p)$ pendant au
  plus $M$ étapes,
\item s'il termine en renvoyant vrai ($1$), terminer et renvoyer $p$
  (sinon, continuer les boucles).
\end{itemize}
\end{itemize}
\end{itemize}

(Intuitivement, $U$ essaie de lancer l'algorithme $T$ sur un nombre de
valeurs de $p$ de plus en plus grand et en attendant de plus en plus
longtemps pour voir si l'une d'elles termine.)

Si l'algorithme $U$ défini ci-dessus termine, il renvoie forcément
$f(n)$ (puisque l'algorithme $T$ a répondu vrai, c'est que $p=f(n)$,
et on renvoie la valeur en question) ; il reste à expliquer pourquoi
$U$ termine toujours.  Mais la valeur $f(n)$ existe (même si on ne la
connaît pas) car la fonction $f$ était supposée définie partout, et
lorsque l'algorithme $T$ est lancé sur $(n,f(n))$ il est donc censé
terminer en un certain nombre (fini !) d'étapes : si $M$ est supérieur
à la fois à $f(n)$ et à ce nombre d'étapes, la valeur $f(n)$ va être
prise par $p$ dans la boucle intérieure, et pour cette valeur,
l'algorithme $T$ va terminer sur l'entrée $(n,p)$ en au plus $M$
étapes, ce qui assure que $U$ termine effectivement.

L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui
prouve (1).
\end{corrige}


%
%
%
\end{document}