summaryrefslogtreecommitdiffstats
path: root/exercices3.tex
blob: a2fa873cf9e1ca1f3cfce7810a47da809f88cbdf (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
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
%% 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



%
%
%

\bigbreak
\centerline{\textbf{Langages rationnels et automates}}

\exercice

Soit $\Sigma = \{a,b\}$.

(1) Tracer l'automate de Thompson de l'expression rationnelle
$a{*}(baa{*}){*}$.  Cet automate est-il déterministe ?

(2) En éliminer les transitions spontanées.

(3) Déterminiser l'automate obtenu.

(4) Minimiser l'automate obtenu.

(5) Vérifier le résultat en décrivant en français le langage dénoté
par l'expression rationnelle initiale et reconnu par l'automate
finalement obtenu.

\begin{corrige}
(1) L'automate de Thompson de $a{*}(baa{*}){*}$ doit comporter $14$
  états puisque cette expression rationnelle contient $7$ symboles
  parenthèses non comptées.  Il est le suivant (où on a omis les
  $\varepsilon$ sur les transitions spontanées) :
\begin{center}
\scalebox{0.34}{%
%%% begin ex3p1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,45bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q3) at (255bp,18bp) [draw,circle,state] {$3$};
  \node (q2) at (176bp,45bp) [draw,circle,state] {$2$};
  \node (q5) at (413bp,48bp) [draw,circle,state] {$5$};
  \node (q4) at (334bp,18bp) [draw,circle,state] {$4$};
  \node (q7) at (571bp,86bp) [draw,circle,state] {$7$};
  \node (q6) at (492bp,86bp) [draw,circle,state] {$6$};
  \node (q9) at (729bp,86bp) [draw,circle,state] {$9$};
  \node (q8) at (650bp,86bp) [draw,circle,state] {$8$};
  \node (q11) at (891.49bp,125bp) [draw,circle,state] {$11$};
  \node (q10) at (809.5bp,125bp) [draw,circle,state] {$10$};
  \node (q13) at (1055.5bp,25bp) [draw,circle,state,final] {$13$};
  \node (q12) at (973.49bp,63bp) [draw,circle,state] {$12$};
  \draw [->] (q0) ..controls (59.7bp,17.371bp) and (103.03bp,16.838bp)  .. (140bp,17bp) .. controls (169.56bp,17.13bp) and (203.43bp,17.448bp)  .. node[auto] {{}} (q3);
  \draw [->] (q12) ..controls (939.5bp,48.432bp) and (914.89bp,40bp)  .. (892.49bp,40bp) .. controls (491bp,40bp) and (491bp,40bp)  .. (491bp,40bp) .. controls (474.34bp,40bp) and (455.77bp,41.875bp)  .. node[auto] {{}} (q5);
  \draw [->] (q2) ..controls (203.44bp,35.73bp) and (216.64bp,31.102bp)  .. node[auto] {{}} (q3);
  \draw [->] (q10) ..controls (835.62bp,135.26bp) and (845.21bp,137.3bp)  .. (854bp,136bp) .. controls (856.94bp,135.57bp) and (859.98bp,134.94bp)  .. node[auto] {$a$} (q11);
  \draw [->] (q7) ..controls (598.66bp,86bp) and (610.82bp,86bp)  .. node[auto] {$a$} (q8);
  \draw [->] (q9) ..controls (788.12bp,80.488bp) and (892.85bp,70.553bp)  .. node[auto] {{}} (q12);
  \draw [->] (q8) ..controls (677.66bp,86bp) and (689.82bp,86bp)  .. node[auto] {{}} (q9);
  \draw [->] (q11) ..controls (915.87bp,107.43bp) and (926.56bp,99.325bp)  .. (935.99bp,92bp) .. controls (940.47bp,88.526bp) and (945.22bp,84.783bp)  .. node[auto] {{}} (q12);
  \draw [->] (q2) ..controls (152.62bp,39.018bp) and (146.07bp,37.685bp)  .. (140bp,37bp) .. controls (134.92bp,36.427bp) and (129.53bp,36.741bp)  .. node[auto] {{}} (q1);
  \draw [->] (q6) ..controls (519.66bp,86bp) and (531.82bp,86bp)  .. node[auto] {{}} (q7);
  \draw [->] (q12) ..controls (1002.2bp,49.853bp) and (1016.2bp,43.176bp)  .. node[auto] {{}} (q13);
  \draw [->] (q9) ..controls (756.02bp,98.925bp) and (770.16bp,105.95bp)  .. node[auto] {{}} (q10);
  \draw [->] (q3) ..controls (282.66bp,18bp) and (294.82bp,18bp)  .. node[auto] {{}} (q4);
  \draw [->] (q11) ..controls (866.59bp,118.91bp) and (860.06bp,117.66bp)  .. (854bp,117bp) .. controls (848.92bp,116.45bp) and (843.55bp,116.73bp)  .. node[auto] {{}} (q10);
  \draw [->] (q5) ..controls (440.12bp,60.892bp) and (454.27bp,67.873bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q4) ..controls (366.77bp,7.9414bp) and (390.7bp,2bp)  .. (412bp,2bp) .. controls (412bp,2bp) and (412bp,2bp)  .. (974.49bp,2bp) .. controls (992.87bp,2bp) and (1012.7bp,7.6737bp)  .. node[auto] {{}} (q13);
  \draw [->] (q0) ..controls (45.436bp,27.27bp) and (58.635bp,31.898bp)  .. node[auto] {{}} (q1);
  \draw [->] (q1) ..controls (121.23bp,55.953bp) and (131.02bp,58.496bp)  .. (140bp,57bp) .. controls (143.13bp,56.478bp) and (146.36bp,55.711bp)  .. node[auto] {$a$} (q2);
  \draw [->] (q4) ..controls (361.28bp,28.238bp) and (374.94bp,33.562bp)  .. node[auto] {{}} (q5);
%
\end{tikzpicture}

%%% end ex3p1 %%%
}
\end{center}

Cet automate n'est pas déterministe : un automate comportant des
ε-transitions est forcément non-déterministe.

(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 :

\begin{center}
\begin{tabular}{r|l}
$q$&ε-fermeture $C(q)$\\
\hline
$0$&$\{0,1,3,4,5,13\}$\\
$2$&$\{2,3,4,5,13\}$\\
$6$&$\{6,7\}$\\
$8$&$\{5,8,9,10,12,13\}$\\
$11$&$\{5,10,11,12,13\}$\\
\end{tabular}
\end{center}

En remplaçant chaque transition $q^\sharp \to q'$ étiquetée par $x$
dans l'automate par une transition $q\to q'$ pour chaque état $q$ tel
que $q^\sharp \in C(q)$, on obtient le NFA suivant :

\begin{center}
%%% begin ex3p1b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q0) at (18bp,31.498bp) [draw,circle,state,initial,final,accepting below] {$0$};
  \node (q2) at (97bp,61.498bp) [draw,circle,state,final] {$2$};
  \node (q11) at (335.5bp,19.498bp) [draw,circle,state,final,accepting below] {$11$};
  \node (q8) at (255bp,49.498bp) [draw,circle,state,final,accepting above] {$8$};
  \node (q6) at (176bp,31.498bp) [draw,circle,state] {$6$};
  \draw [->] (q0) ..controls (45.279bp,41.737bp) and (58.943bp,47.06bp)  .. node[auto] {$a$} (q2);
  \draw [->] (q2) to[loop above] node[auto] {$a$} (q2);
  \draw [->] (q8) ..controls (282.44bp,39.394bp) and (295.8bp,34.29bp)  .. node[auto] {$a$} (q11);
  \draw [->] (q11) to[loop above] node[auto] {$a$} (q11);
  \draw [->] (q11) ..controls (297.15bp,8.7001bp) and (264.63bp,2.1768bp)  .. (237bp,7.4983bp) .. controls (224.85bp,9.8374bp) and (212.04bp,14.613bp)  .. node[auto,near start] {$b$} (q6);
  \draw [->] (q0) ..controls (47.643bp,24.415bp) and (64.2bp,20.964bp)  .. (79bp,19.498bp) .. controls (94.922bp,17.922bp) and (99.078bp,17.922bp)  .. (115bp,19.498bp) .. controls (125.98bp,20.586bp) and (137.94bp,22.768bp)  .. node[auto,below] {$b$} (q6);
  \draw [->] (q2) ..controls (124.28bp,51.26bp) and (137.94bp,45.936bp)  .. node[auto] {$b$} (q6);
  \draw [->] (q8) ..controls (234.03bp,34.749bp) and (226.51bp,30.579bp)  .. (219bp,28.498bp) .. controls (214.15bp,27.154bp) and (208.87bp,26.751bp)  .. node[auto,near start] {$b$} (q6);
  \draw [->] (q6) ..controls (198.21bp,42.911bp) and (205.25bp,45.859bp)  .. (212bp,47.498bp) .. controls (216.59bp,48.613bp) and (221.55bp,49.292bp)  .. node[auto] {$a$} (q8);
%
\end{tikzpicture}

%%% end ex3p1b %%%
\end{center}

Les états $0,2,8,11$ sont finaux car ce sont eux qui ont $13$ dans
leur ε-fermeture.

(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
$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é.

(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
les non-finaux $\{6,\bot\}$.  La transition étiquetée $a$ sépare les
états $6$ et $\bot$ car le premier aboutit dans la classe
$\{0,2,8,11\}$ tandis que le second aboutit dans la classe
$\{6,\bot\}$.  On vérifie ensuite qu'aucune transition ne sépare des
états.  L'automate minimal est donc le suivant :
\begin{center}
%%% begin ex3p1c %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q6) at (97bp,20.28bp) [draw,circle,state] {$6$};
  \node (qbot) at (176bp,20.28bp) [draw,circle,state] {$\bot$};
  \node (qF) at (18bp,20.28bp) [draw,circle,state,initial,final,accepting below] {$F$};
  \draw [->] (q6) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$a$} (qF);
  \draw [->] (q6) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$b$} (qbot);
  \draw [->] (qbot) to[loop above] node[auto] {$a,b$} (qbot);
  \draw [->] (qF) to[loop above] node[auto] {$a$} (qF);
  \draw [->] (qF) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q6);
%
\end{tikzpicture}

%%% end ex3p1c %%%
\end{center}
où l'état $F$ représente la classe $0\equiv 2\equiv 8\equiv 11$.

(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
d'au moins un $a$ : l'expression rationnelle initiale le présente
comme le langage constitués des mots formés d'un nombre quelconque de
$a$ puis d'un nombre quelconque de répétitions d'un $b$ suivi d'au
moins un $a$.  L'automate final interdit les suites de deux $b$
consécutifs comme ceci : l'état $F$ correspond à la situation où on ne
vient pas de rencontrer un $b$ (=la lettre précédente était un $a$ ou
bien on vient de commencer le mot) et on n'en a jamais rencontré deux,
l'état $6$ à la situation où on vient de rencontrer un $b$ et on n'en
a jamais rencontré deux, et l'état $\bot$ à la situation où on a
rencontré au moins une fois deux $b$ consécutifs.  Avec cette
description, il est clair que l'automate fait ce qui était demandé.
\end{corrige}


%
%
%

\exercice

Donner plusieurs (au moins trois) expressions rationnelles
équivalentes dénotant le langage reconnu par l'automate suivant sur
l'alphabet $\Sigma = \{a,b\}$ :

\begin{center}
%%% begin ex3p2 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,initial above,accepting below] {$0$};
  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$b$} (q0);
  \draw [->] (q2) to[loop right] node[auto] {$b$} (q2);
  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q0) to[loop left] node[auto] {$a$} (q0);
  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q1);
  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$a$} (q2);
%
\end{tikzpicture}


%%% end ex3p2 %%%
\end{center}
(On pourra considérer les ordres suivants d'élimination des états :
d'abord $2,1,0$, ensuite $1,2,0$ et enfin $0,2,1$.)

\begin{corrige}
Si on commence par éliminer l'état $2$ (en considérant l'automate
comme un automate à transitions étiquetées par des expressions
rationnelles), l'état $1$ reçoit une transition vers lui-même
étiquetée $ab{*}a$.  Si on élimine l'état $1$, l'état $0$ reçoit à la
place une transition vers lui-même étiquetée par $b(ab{*}a){*}b$,
qu'on peut fusionner avec la transition vers lui-même déjà existante
étiquetée par $a$ pour une seule étiquetée par $a|b(ab{*}a){*}b$.
Quitte éventuellement à ajouter un nouvel état initial (conduisant à
$0$ par une transition spontanée) et un nouvel état final (vers lequel
$0$ conduit par une transition spontanée) et à éliminer n'état $0$, on
obtient finalement l'expression rationnelle
\[
(a|b(ab{*}a){*}b){*}
\]

Si on commence par éliminer l'état $1$, il apparaît une transition
$0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut
appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas
de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter
par $\bot$, symbole d'expression rationnelle qui dénote le lagange
vide, et l'expression rationnelle $\bot{*}$ est équivalente
à $\varepsilon$) ; mais il ne faut pas oublier que l'état $2$ reçoit
lui aussi une transition vers lui-même (en passant par $1$) étiquetée
$aa$, qu'on peut fusionner avec la transition vers lui-même déjà
existante étiquetée par $b$ pour obtenir une transition étiquetée
$b|aa$.  L'élimination de l'état $2$ fait alors apparaître une
transition de $0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut
fusionner avec la transition vers lui-même déjà étiquetée par $a$ pour
une seule étiquetée par $a|b(a(b|aa){*}a){*}b$.  On obtient finalement
\[
(a|b(a(b|aa){*}a){*}b){*}
\]
(en particulier, cette expression est équivalente à celle obtenue
précédemment).

Si on préfère commencer par éliminer l'état $0$, il faut au préalable
ajouter un nouvel état initial $I$ (conduisant à $0$ par une
transition spontanée) et un nouvel état final $F$ (vers lequel $0$
conduit par une transition spontanée).  L'élimination de l'état $0$
fait apparaître une transition de $I$ vers $1$ étiquetée $a{*}b$, une
transition $1$ vers $F$ étiquetée $ba{*}$, et une transition de l'état
$1$ vers lui-même étiquetée $ba{*}b$, et enfin une transition de $I$
vers $F$ étiquetée $a{*}$.  L'élimination de l'état $2$ fait
apparaître une transition de $1$ vers lui-même étiquetée $ab{*}a$,
qu'on peut fusionner avec celle déjà existante étiquetée $ba{*}b$ pour
obtenir une transition $(ab{*}a|ba{*}b)$.  Finalement, l'élimination
de l'état $1$ done l'expression rationnelle
\[
a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*}
\]
(toujours équivalente aux précédentes).
\end{corrige}



%
%
%

\bigbreak
\centerline{\textbf{Langages algébriques et grammaires hors contexte}}

\exercice

On considère la grammaire hors contexte $G$ suivante (d'axiome $S$)
sur l'alphabet $\Sigma = \{a,b\}$ :
\[
S \rightarrow aSS \;|\; b
\]
Soit $L = L(G)$ le langage algébrique qu'elle engendre.

(0) Donner quelques exemples de mots dans $L$.

(1) Expliquer pourquoi un $w\in \Sigma^*$ appartient à $L$ si et
seulement si : soit $w = b$, soit il existe $u,v\in L$ tels que $w =
auv$.

(2) En déduire par récurrence sur la longueur $|w|$ de $w$ que si $w
\in L$ alors on a $wz \not\in L$ pour tout $z \in \Sigma^+$
(c'est-à-dire $z \in \Sigma^*$ et $z \neq \varepsilon$).  Autrement
dit : en ajoutant des lettres à la fin d'un mot de $L$ on obtient un
mot qui n'appartient jamais à $L$.  (Indication : lorsque $auvz =
au'v'$ on pourra considérer les cas (i) $|u'|>|u|$, (ii) $|u'|<|u|$ et
(iii) $|u'|=|u|$.)

(3) En déduire que si $auv = au'v'$ avec $u,v,u',v'\in L$ alors $u=u'$
et $v=v'$.  (Indication analogue.)

(4) En déduire que $G$ est inambiguë, c'est-à-dire que chaque mot
$w\in L$ a un unique arbre d'analyse pour $G$ (on pourra reprendre
l'analyse de la question (1) et procéder de nouveau par récurrence
sur $|w|$).

(5) En s'inspirant des questions précédentes, décrire un algorithme
simple (en une seule fonction récursive) qui, donné un mot
$w\in\Sigma^*$, décide si $w\in L$ (c'est-à-dire répond vrai ou faux
selon que $w\in L$ ou $w\not\in L$) ou plus généralement, donné
$w\in\Sigma^*$, renvoie la longueur du préfixe de $w$ appartenant
à $L$ s'il existe (il est alors unique d'après la question (2)).

\begin{corrige}
(0) Quelques exemples de mots dans $L$ sont $b$, $abb$, $aabbb$,
  $ababb$ ou encore $aabbabb$.

(1) Si $w \in L$, considérons un arbre d'analyse $\mathscr{W}$ de $w$
  pour $G$ : sa racine, étiquetée $S$, doit avoir des fils étiquetés
  selon l'une des deux règles de la grammaire, $S\rightarrow b$ ou
  bien $S\rightarrow aSS$, autrement dit, soit elle a un unique fils
  étiqueté $b$, soit elle a trois fils étiquetés respectivement
  $a,S,S$.  Dans le premier cas, le mot $w$ est simplement $b$ ; dans
  le second, les sous-arbres $\mathscr{U}, \mathscr{V}$ ayant pour
  racine les deux fils étiquetés $S$ sont encore des arbres d'analyse
  pour $G$, et si on appelle $u$ et $v$ les mots dont ils sont des
  arbres d'analyse (c'est-à-dire, ceux obtenus en lisant les feuilles
  de $\mathscr{U}$ et $\mathscr{V}$ respectivement par ordre de
  profondeur), alors on a $w = auv$ et $u,v\in L$ puisqu'ils ont des
  arbres d'analyse pour $G$.

La réciproque est analogue : le mot $b$ appartient trivialement à $L$,
et si $u,v\in L$, ils ont des arbres d'analyse $\mathscr{U},
\mathscr{V}$ pour $G$, et on peut fabriquer un arbre d'analyse pour $w
:= auv$ qui a une racine étiquetée $S$ ayant trois fils étiquetés
$a,S,S$, ces deux derniers ayant pour descendants des sous-arbres
donnés par $\mathscr{U}$ et $\mathscr{V}$.

(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|$.
D'après la question (1), le mot $w$ est soit $b$ soit de la forme
$auv$ avec $u,v\in L$ et trivialement $|u|<|w|$ et $|v|<|w|$.  Si
$w=b$, il est évident qu'aucun mot de la forme $bz$ ne peut appartenir
à $L$ (la question (1) montre que les seuls mots de $L$ sont le mot
$b$ et des mots commençant par $a$).  Il reste le cas $w = auv$ : on
veut montrer que $wz$, c'est-à-dire $auvz$, n'appartient pas à $L$.
Mais s'il y a appartenait, toujours d'après la question (1), il serait
de la forme $au'v'$ (le cas $b$ étant trivialement exclu), où $u',v'
\in L$ ; notamment, $uvz = u'v'$.  Distinguons trois cas : (i) soit
$|u'|>|u|$, mais alors $u$ est un préfixe strict de $u'$, c'est-à-dire
que $u'$ peut s'écrire sous la forme $u' = ut$ pour un $t\in
\Sigma^+$, et par l'hypothèse de récurrence, on a $u'\not\in L$, une
contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe
strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u =
u't$ pour un $t\in\Sigma^+$, et par l'hypothèse de récurrence (puisque
$|u'|<|u|<|w|$), on a $u\not\in 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 $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.

(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'$,
c'est-à-dire que $u'$ peut s'écrire sous la forme $u' = ut$ pour un
$t\in \Sigma^+$, et par la question (2), on a $u'\not\in L$, une
contradiction ; (ii) soit $|u'|<|u|$, mais alors $u'$ est un préfixe
strict de $u$, c'est-à-dire que $u$ peut s'écrire sous la forme $u =
u't$ pour un $t\in\Sigma^+$, et par la question (2), on a $u\not\in
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.

(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
on l'a expliqué en (1), il y a deux possibilités pour un arbre
d'analyse de $w$ : soit la racine a un unique fils étiqueté $b$ et le
mot analysé est $w=b$, soit la racine a trois fils étiquetés $a,S,S$,
et des deux derniers fils partent des arbres d'analyse
$\mathscr{U},\mathscr{V}$ de mots $u,v\in L$ tels que $w=auv$.  Ces
deux cas sont évidemment incompatibles : il reste donc simplement à
expliquer que dans le dernier, $\mathscr{U}$ et $\mathscr{V}$ sont
uniquement déterminés.  Or la question (3) assure que $u,v$ (tels que
$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.

(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 :
\begin{itemize}
\item si $w=\varepsilon$, renvoyer échec,
\item si la première lettre de $w$ est $b$, renvoyer $1$,
\item sinon (la première lettre de $w$ est $a$), soit $x$ le suffixe
  de $w$ correspondant (c'est-à-dire $w = ax$, ou si on préfère, $x$
  enlève la première lettre de $w$),
\item appeler la fonction elle-même (rechercher préfixe dans $L$)
  sur $x$ :
\item si elle échoue, renvoyer échec,
\item si elle retourne $k$, soit $u$ le préfixe de $y$ de longueur
  $k$, et $z$ le suffixe correspondant (c'est-à-dire $y = ux$, ou si
  on préfère, $y$ enlève les $k$ premières lettres de $x$),
\item appeler la fonction elle-même (rechercher préfixe dans $L$)
  sur $y$ :
\item si elle échoue, renvoyer échec,
\item si elle retourne $\ell$, retourner $1+k+\ell$ (en effet, on a $w
  = auvz$ où $u$ est de longueur $k$ et $v$ est de longueur $\ell$).
\end{itemize}

Pour savoir si un mot appartient à $w$, il s'agit simplement de
vérifier que la valeur retournée (=la longueur du préfixe appartenant
à $L$) n'est pas un échec et est égale à la longueur $|w|$.

La terminaison de cet algorithme est claire par récurrence sur la
longueur (chaque appel récursif est fait sur un mot de longueur
strictement plus courte), et sa correction est garantie par les
questions précédentes : les cas $b$ et $auv$ sont disjoints et dans le
dernier cas, $u$ et $v$ sont uniquement déterminés (c'est ce
qu'affirme la non-ambiguïté de la grammaire).

(Il s'agit ici du cas le plus simple d'un analyseur LL, et
l'algorithme présenté ci-dessus est essentiellement un analyseur LL
camouflé sous forme d'analyseur par descente récursive.)
\end{corrige}



%
%
%

\bigbreak
\centerline{\textbf{Calculabilité}}

\exercice

(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
$k$-ième pour un $k\geq 2$ est-il décidable ?  Semi-décidable ?

(2) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
programme (ou, si on préfère, de la $e$-ième machine de Turing),
exécuté sur l'entrée $42$, termine en au plus $10^{1000+e}$ étapes
est-il décidable ?  Semi-décidable ?

(3) L'ensemble des $e \in \mathbb{N}$ tels que l'exécution du $e$-ième
programme (ou, si on préfère, de la $e$-ième machine de Turing),
exécuté sur l'entrée $42$, termine en temps fini est-il décidable ?
Semi-décidable ?  (On pourra montrer qu'on peut y ramener le problème
de l'arrêt.)

\begin{corrige}
(1) Si $w = u^k$ pour un certain $u\neq\varepsilon$, alors
  nécessairement $k\leq |w|$ puisque $|w|=k\cdot|u|$.  On dispose donc
  de l'algorithme suivant pour décider si $w\in L$ : si
  $w=\varepsilon$, retourner vrai immédiatement ; sinon, pour $k$
  allant de $2$ à $|w|$ et qui divise $|w|$, considérer les $k$
  facteurs successifs de $w$ de longueur $|w|/k$ (c'est-à-dire, pour
  $0\leq i<k$, le facteur de $w$ de longueur $\ell := |w|/k$
  commençant à la position $\ell i$) : s'ils sont tous égaux, renvoyer
  vrai ; si la boucle termine sans avoir trouvé de $k$ qui convienne,
  renvoyer faux.  Le langage proposé est donc décidable (et \textit{a
    fortiori} semi-décidable).

(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
  d'étapes (en utilisant la machine universelle, c'est-à-dire, par
  exemple, en simulant la $e$-ième machine de Turing sur une machine
  de Turing).  Si l'exécution termine en le temps imparti, on renvoie
  vrai, sinon, on renvoie faux : ceci montre que l'ensemble proposé
  est bien décidable (et \textit{a fortiori} semi-décidable).

(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$
  alors qu'ici on a fixé l'entrée à $42$.  Il s'agit donc de montrer
  que cette limitation ne rend pas pour autant calculable l'ensemble
  considéré.  Or donnés deux entiers $(e,n)$, on peut fabriquer un
  programme $e'$ qui prend en entrée une valeur, \emph{ignore} cette
  valeur, et exécute le $e$-ième programme sur l'entrée $n$ ; de plus
  un tel $e'$ se calcule algorithmiquement à partir de $e$ et $n$.
  L'exécution du programme $e'$ sur l'entrée $42$ (ou n'importe quelle
  autre entrée) se comporte donc comme l'exécution du programme $e$
  sur l'entrée $n$, et notamment, termine si et seulement si elle
  termine.  Autrement dit, $e'$ appartient à l'ensemble $A$ considéré
  dans cette question si et seulement si $(e,n)$ appartient au
  problème de l'arrêt.  Comme on vient de dire qu'on peut calculer
  $e'$ algorithmiquement à partir de $(e,n)$, si l'ensemble $A$ était
  décidable, le problème de l'arrêt le serait, ce qui n'est pas le
  cas.  Donc $A$ n'est pas décidable.  En revanche, $A$ est
  semi-décidable : il suffit de lancer l'exécution du programme $e$
  sur l'entrée $42$ et renvoyer vrai si ele termine (si elle ne
  termine pas, on ne termine pas).
\end{corrige}


%
%
%

\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}

%
%
%

\exercice

Soit $A \subseteq \mathbb{N}$ un ensemble infini.  Montrer qu'il y a
équivalence entre :
\begin{itemize}
\item l'ensemble $A$ est décidable,
\item il existe une fonction calculable \emph{strictement croissante}
  $f\colon\mathbb{N}\to\mathbb{N}$ telle que $f(\mathbb{N}) = A$.
\end{itemize}

\begin{corrige}
Supposons $A$ décidable : on va construire $f$ comme indiqué.  Plus
exactement, on va appeler $f(n)$ le $n$-ième élément de $A$ par ordre
croissant (c'est-à-dire que $f(0)$ est le plus petit élément de $A$,
et $f(1)$ le suivant par ordre de taille, et ainsi de suite ; noter
que $A$ est infini donc cette fonction est bien définie).  Montrons
que $f$ est calculable : donné un entier $n$, on teste successivement
si $0\in A$ puis $1\in A$ puis $2\in A$ et ainsi de suite, à chaque
fois en utilisant un algorithme décidant $A$ (qui est censé exister
par hypothèse) jusqu'à obtenir $n$ fois la réponse « oui » ; plus
exactement :
\begin{itemize}
\item initialiser $m \leftarrow 0$,
\item pour $k$ allant de $0$ à l'infini,
\begin{itemize}
\item interroger l'algorithme qui décide si $k\in A$,
\item s'il répond « oui » :
\begin{itemize}
\item si $m=n$, terminer et renvoyer $k$,
\item sinon, incrémenter $m$ (c'est-à-dire faire $m \leftarrow m+1$).
\end{itemize}
\end{itemize}
\end{itemize}
La boucle termine car $A$ est infini.

Réciproquement, supposons $f$ strictement croissante calculable et
posons $A = f(\mathbb{N})$ : on veut montrer que $A$ est décidable.
Or pour décider si $k \in A$, il suffit de calculer successivement
$f(0)$, $f(1)$, $f(2)$ et ainsi de suite, et de terminer si $f(n)$
atteint ou dépasse le $k$ fixé : s'il l'atteint, on renvoie vrai (on a
trouvé $n$ tel que $f(n)=k$), sinon, on renvoie faux (la valeur $k$ a
été sautée par la fonction $f$ et ne sera donc jamais atteinte).
L'algorithme est donc explicitement :
\begin{itemize}
\item pour $n$ allant de $0$ à l'infini,
\begin{itemize}
\item calculer $f(n)$,
\item si $f(n) = k$, renvoyer vrai,
\item si $f(n) > k$, renvoyer faux.
\end{itemize}
\end{itemize}
La boucle termine car toute fonction strictement croissante
$\mathbb{N}\to\mathbb{N}$ est de limite $+\infty$ en l'infini (donc
$f(n)$ finit forcément par atteindre ou dépasser $k$).
\end{corrige}

%
%
%

\exercice

Soit $S(e,n)$ le nombre d'étapes de l'exécution du $e$-ième programme
(ou, si on préfère, de la $e$-ième machine de Turing) quand on lui
fournit le nombre $n$ en entrée, à supposer que cette exécution
termine ; sinon, $S(e,n)$ n'est pas défini.

Soit par ailleurs $M(k)$ le maximum des $S(e,n)$ pour $0\leq e\leq k$
et $0\leq n\leq k$ qui soient définis (et $0$ si aucun d'eux n'est
défini).  Autrement dit, il s'agit du plus petit entier supérieur ou
égal au nombre d'étapes de l'exécution de l'un des programmes $0\leq
e\leq k$ sur l'un des entiers $0\leq n\leq k$ en entrée, lorsqu'ils
terminent.

Montrer que la fonction $M$ n'est pas calculable (i.e., n'est pas
calculable par un algorithme) : on pourra pour cela montrer que la
connaissance de $M$ permet de résoudre le problème de l'arrêt.
Montrer même qu'\emph{aucune} fonction $M'$ telle que $M'(k) \geq
M(k)$ pour tout $k$ n'est calculable.  Montrer que même si $M'$
vérifie simplement $M'(k)\geq M(k)$ pour $k\geq k_0$, alors $M'$ n'est
pas calculable.

\emph{Remarque :} La fonction $M$, ou différentes variantes de
celle-ci, s'appelle fonction du « castor affairé ».  On peut montrer
encore plus fort : si $F$ est une fonction calculable quelconque,
alors il existe $k_0$ tel que $M(k) \geq F(k)$ pour $k\geq k_0$
(autrement dit, la fonction $M$ finit par dépasser n'importe quelle
fonction calculable : Radó, 1962, \textit{On Non-Computable
  Functions}).

\begin{corrige}
Supposons que $M$ soit calculable.  On peut alors résoudre le problème
de l'arrêt de la manière suivante : donné un algorithme $T$, de
numéro $e$, et une entrée $n$ à fournir à cet algorithme, pour savoir
si $T$ s'arrête, on calcule $M(k)$ où $k = \max(e,n)$, on exécute
ensuite l'algorithme $T$ pendant au plus $M(k)$ étapes : s'il termine
dans le temps imparti, on répond vrai (il a terminé), sinon, on répond
faux (il ne terminera jamais).  Cette résolution du problème de
l'arrêt est correcte, car si $T$ termine sur l'entrée $n$, il prendra
par définition $S(e,n)$ étapes, avec $0\leq e\leq k$ et $0\leq n\leq
k$ par définition de $k$, donc $S(e,n) \leq M(k)$ par définition de
$M(k)$ : ceci signifie précisément que si $T$ n'a pas terminé en
$M(k)$ étapes, il ne terminera jamais.

Exactement le même argument montre que $M'$ n'est pas calculable sous
l'hypothèse que $M'(k) \geq M(k)$ pour tout $k$ : s'il l'était, on
pourrait exécuter l'algorithme $T$ pendant au plus $M'(k)$ étapes, et
comme on a $S(e,n) \leq M(k) \leq M'(k)$, la même démonstration
convient.

Enfin, si on suppose seulement $M'(k)\geq M(k)$ pour $k\geq k_0$, la
fonction $M'$ n'est toujours pas calculable : en effet, si on suppose
par l'absurde qu'elle l'est, la fonction $M''$ qui à $k$ associe
$M'(k)$ si $k\geq k_0$ et $M(k)$ sinon, serait encore calculable
puisqu'elle ne diffère de $M'$ qu'en un nombre fini de valeurs, or
changer la valeur en un point d'une fonction calculable donne toujours
une fonction calculable (même si on « ne connaît pas » la valeur à
changer, elle existe, donc l'algorithme modifié existe).  Mais d'après
le paragraphe précédent, $M''$ n'est pas calculable puisqu'elle est
partout supérieure ou égale à $M$.
\end{corrige}


%
%
%
\end{document}