summaryrefslogtreecommitdiffstats
path: root/controle-20230615.tex
blob: d9bc00de5d0e2cbef3ed4d1f0bdc2bd24ee2d696 (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
%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,margin=2.5cm]{geometry}
\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{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
\renewcommand{\qedsymbol}{\smiley}
%
\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\par\smallbreak\else\egroup\par\fi}
\newenvironment{commentaire}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
{{\hbox{}\nobreak\hfill\maltese}%
\ifcorrige\par\smallbreak\else\egroup\par\fi}
%
%
% 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{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
\else
\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
\fi
\author{}
\date{15 juin 2023}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont totalement indépendants.  Ils pourront être traités
dans un ordre quelconque, mais on demande de faire apparaître de façon
très visible dans les copies où commence chaque exercice.

\medbreak

L'usage de tous les documents (notes de cours manuscrites ou
imprimées, feuilles d'exercices, livres) est autorisé.

L'usage des appareils électroniques est interdit.

\medbreak

Durée : 1h30

Barème \emph{indicatif} et \emph{approximatif} : exercice 1 :
(a) $1.5$, (b) $1.5$, (c) $1$, (d) $4$, (e) $3$, (f) $3$ (soit au
total $14$) ; exercice 2 : (a) $1$, (b) $2$, (c) $1$, (d) $2$ (soit au
total $6$).

\ifcorrige
Ce corrigé comporte 8 pages (page de garde incluse).
\else
Cet énoncé comporte 4 pages (page de garde incluse).
\fi

\vfill

{\tiny\noindent
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak


%
%
%

\exercice

Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On considère les huit
automates suivants
($A_{\mathrm{s}},A_{\mathrm{t}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{w}},A_{\mathrm{x}},A_{\mathrm{y}},A_{\mathrm{z}}$)
sur l'alphabet $\Sigma$ :

\begin{center}
\begin{tabular}{|c|c|}
\hline
$A_{\mathrm{s}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{t}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{u}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{v}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{w}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
\draw[->] (q1) to[loop above] node[auto]{$a,b$} (q1);
\draw[->] (q2) to[loop above] node[auto]{$a,b$} (q2);
\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
\draw[->] (q4) to[loop above] node[auto]{$a,b$} (q4);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{x}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting below] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,accepting below] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,accepting below] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,accepting below] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,accepting below] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,accepting below] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{y}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial above] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,initial above] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,initial above] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,initial above] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,initial above] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,initial above,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{z}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial above,accepting below] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,initial above,accepting below] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,initial above,accepting below] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,initial above,accepting below] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,initial above,accepting below] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,initial above,accepting below] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\end{tikzpicture}
}\\
\hline
\end{tabular}
\end{center}

On définit aussi les douze langages suivants, où $w_0$ désigne le
mot $ababb$ :
\begin{itemize}
\item $L_0 = \varnothing$ : le langage vide.
\item $L_1 = \{w_0\}$ : le langage constitué du seul mot $w_0$.
\item $L_2$ : le langage constitué des mots qui sont un sous-mot de
  $w_0$.
\item $L_3$ : le langage constitué des mots qui ont $w_0$ comme
  sous-mot.
\item $L_4$ : le langage constitué des mots qui sont un facteur de
  $w_0$.
\item $L_5$ : le langage constitué des mots qui ont $w_0$ comme
  facteur.
\item $L_6$ : le langage constitué des mots qui sont un préfixe de
  $w_0$.
\item $L_7$ : le langage constitué des mots qui ont $w_0$ comme
  préfixe.
\item $L_8$ : le langage constitué des mots qui sont un suffixe de
  $w_0$.
\item $L_9$ : le langage constitué des mots qui ont $w_0$ comme
  suffixe.
\item $L_{10} = \{w_0^i : i\in\mathbb{N}\}$ : le langage constitué des
  mots qui sont une répétition d'un nombre quelconque ($i$) de copies
  de $w_0$ (par exemple, $ababbababb$).
\item $L_{11} = \{b^i w_0 a^i : i\in\mathbb{N}\}$ : le langage
  constitué des mots obtenus en précédant $w_0$ d'un nombre
  quelconque ($i$) de copies de la lettre $b$ et en le suivant du même
  nombre de copies de la lettre $a$ (par exemple, $bbababbaa$).
\end{itemize}

\textbf{(a)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}},
A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire lequel ou
lesquels parmi les douze langages $L_0,\ldots,L_{11}$ est celui
reconnu par l'automate $A$.  On ne demande pas de justifier la
réponse.

\begin{corrige}
L'automate $A_{\mathrm{s}}$ reconnaît le langage $L_1 = \{w_0\}$.

L'automate $A_{\mathrm{t}}$ reconnaît le langage $L_9$ des mots ayant
$w_0$ comme suffixe (car un chemin dans $A_{\mathrm{t}}$ finit par un
chemin consommant $w_0$).

L'automate $A_{\mathrm{u}}$ reconnaît le langage $L_7$ des mots ayant
$w_0$ comme préfixe (car un chemin dans $A_{\mathrm{u}}$ commence
par un chemin consommant $w_0$).

L'automate $A_{\mathrm{v}}$ reconnaît le langage $L_5$ des mots ayant
$w_0$ comme facteur (car un chemin dans $A_{\mathrm{u}}$ passe par un
chemin consommant $w_0$).

L'automate $A_{\mathrm{w}}$ reconnaît le langage $L_3$ des mots ayant
$w_0$ comme sous-mot (car un chemin dans $A_{\mathrm{u}}$ consomme les
lettres $a,b,a,b,b$ dans cet ordre, intercalées par un nombre
quelconque de lettres quelconques).

L'automate $A_{\mathrm{x}}$ reconnaît le langage $L_6$ des préfixes
de $w_0$ (car un chemin dans $A_{\mathrm{x}}$ consomme le début
de $w_0$).

L'automate $A_{\mathrm{y}}$ reconnaît le langage $L_8$ des suffixes
de $w_0$ (car un chemin dans $A_{\mathrm{y}}$ consomme la fin
de $w_0$).

L'automate $A_{\mathrm{z}}$ reconnaît le langage $L_4$ des facteurs
de $w_0$ (car un chemin dans $A_{\mathrm{z}}$ consomme un intervalle
de lettres consécutives de $w_0$).

(Les justifications entre parenthèses n'étaient pas demandées.)
\end{corrige}

\textbf{(b)} Pour chacun des sept automates $A \in \{A_{\mathrm{s}},
A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
A_{\mathrm{x}}, A_{\mathrm{y}}\}$ (cette question-ci n'est pas posée
pour $A_{\mathrm{z}}$), donner une expression rationnelle dénotant le
langage $L$ reconnu par $A$.  On ne demande pas de justifier la
réponse, et il n'est pas obligatoire d'appliquer un algorithme vu en
cours.

\begin{corrige}
L'automate $A_{\mathrm{s}}$ reconnaît le langage dénoté par $ababb$.

L'automate $A_{\mathrm{t}}$ reconnaît le langage dénoté
par $(a|b){*}ababb$.

L'automate $A_{\mathrm{u}}$ reconnaît le langage dénoté
par $ababb(a|b){*}$.

L'automate $A_{\mathrm{v}}$ reconnaît le langage dénoté
par $(a|b){*}ababb(a|b){*}$.

L'automate $A_{\mathrm{w}}$ reconnaît le langage dénoté
par $(a|b){*}a(a|b){*}b(a|b){*}a(a|b){*}b(a|b){*}b(a|b){*}$.

L'automate $A_{\mathrm{x}}$ reconnaît le langage dénoté
par $\underline{\varepsilon}|a|ab|aba|abab|ababb$ (simple énumération
de tous les préfixes de $w_0$) ou, si on préfère, par
$\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|b))))$
(obtenue en éliminant les états de $A_{\mathrm{x}}$ dans
l'ordre $5,4,3,2,1,0$).

L'automate $A_{\mathrm{y}}$ reconnaît le langage dénoté
par $\underline{\varepsilon}|b|bb|abb|babb|ababb$ (simple énumération
de tous les suffixes de $w_0$) ou, si on préfère, par
$\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|a)b)a)b)b$
(obtenue en éliminant les états de $A_{\mathrm{y}}$ dans
l'ordre $0,1,2,3,4,5$).
\end{corrige}

\textbf{(c)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}},
A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire de quel type
d'automate vu en cours (DFA complet, DFA à spécification incomplète,
NFA ou bien NFA à transitions spontanées) est l'automate $A$.  On
donnera à chaque fois le type le plus particulier applicable.

\begin{corrige}
L'automate $A_{\mathrm{s}}$ est un DFA à spécification incomplète (ou
DFAi).

L'automate $A_{\mathrm{t}}$ est un NFA (à cause de la double
transition étiquetée $a$ depuis l'état $0$).

L'automate $A_{\mathrm{u}}$ est un DFA à spécification incomplète (ou
DFAi).

L'automate $A_{\mathrm{v}}$ est un NFA.

L'automate $A_{\mathrm{w}}$ est un NFA.

L'automate $A_{\mathrm{x}}$ est un DFA à spécification incomplète (ou
DFAi).

L'automate $A_{\mathrm{y}}$ est un NFA (à cause des multiples états
initiaux).

L'automate $A_{\mathrm{z}}$ est un NFA.
\end{corrige}

\textbf{(d)} Pour chacun des cinq automates $A \in \{A_{\mathrm{s}},
A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{x}}, A_{\mathrm{z}}\}$
(cette question-ci n'est pas posée pour $A_{\mathrm{t}},
A_{\mathrm{w}}, A_{\mathrm{y}}$), donner un DFA complet sans état
inaccessible qui soit équivalent à $A$ (c'est-à-dire, reconnaissant le
langage $L$).  On appliquera un algorithme vu en cours en le nommant.

{\footnotesize Conseil sur la présentation graphique : pour s'éviter
  des maux de tête dans le placement des états (et en éviter aussi au
  correcteur), il est conseillé de commencer par placer
  horizontalement de gauche à droite les états successifs rencontrés
  lors de la consommation du mot $w_0 = ababb$ par l'automate
  construit, et d'ajouter ensuite les autres états éventuellement
  nécessaires.\par}

\begin{corrige}
S'agissant de $A_{\mathrm{s}}$, comme c'est un DFAi, il s'agit
simplement de lui ajouter un état « puits », noté $\bot$ ci-dessous,
où aboutissent toutes les transitions manquantes :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
\vskip0ptplus20ex\relax
La construction est analogue pour $A_{\mathrm{u}}$ :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
\vskip0ptplus20ex\relax S'agissant de $A_{\mathrm{v}}$, on a affaire à
un « vrai » non-déterminisme et on applique donc l'algorithme de
déterminisation vu en cours, qui donne (en omettant les accolades dans
le nommage des états) :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {\small $0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {\small $0,1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {\small $0,2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {\small $0,1,3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {\small $0,2,4$};
\node (q5) at (300bp,-45bp) [draw,circle,state,final] {\small $0,5$};
\node (q1X) at (30bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,5$};
\node (q2X) at (110bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,5$};
\node (q3X) at (190bp,-90bp) [draw,circle,state,accepting below] {\small $0,1,3,5$};
\node (q4X) at (270bp,-90bp) [draw,circle,state,accepting below] {\small $0,2,4,5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[loop below] node[auto]{$b$} (q0);
\draw[->] (q1) to[loop below] node[auto]{$a$} (q1);
\draw[->] (q2) to[out=120,in=60] node[auto,swap]{$b$} (q0);
\draw[->] (q3) to[out=120,in=60] node[auto,swap]{$a$} (q1);
\draw[->] (q4) to[out=120,in=60] node[auto,swap]{$a$} (q3);
\draw[->] (q5) to[loop above] node[auto]{$b$} (q5);
\draw[->] (q5) to[out=165,in=45] node[auto,swap,near end]{$a$} (q1X);
\draw[->] (q1X) -- node[auto]{$b$} (q2X);
\draw[->] (q2X) -- node[auto]{$a$} (q3X);
\draw[->] (q3X) -- node[auto]{$b$} (q4X);
\draw[->] (q4X) -- node[auto,swap]{$b$} (q5);
\draw[->] (q1X) to[loop left] node[auto]{$a$} (q1X);
\draw[->] (q2X) to[out=45,in=195] node[auto]{$b$} (q5);
\draw[->] (q3X) to[out=240,in=300] node[auto]{$a$} (q1X);
\draw[->] (q4X) to[out=240,in=300] node[auto]{$a$} (q3X);
\end{tikzpicture}
}
\end{center}
\vskip0ptplus20ex\relax {\footnotesize\textbf{Note:} Une version
  précédente de ce corrigé donnait un automate certes correct (DFA
  complet sans état inaccessible qui soit équivalent à $A$) mais qui
  n'est pas celui, représenté ci-dessus, obtenu en appliquant
  l'algorithme de déterminisation.  (L'automate qui était représenté
  était, en fait, l'automate minimal obtenu en identifiant tous les
  états contenant $5$ dans celui ci-dessus.)\par}
La construction pour $A_{\mathrm{x}}$ est exactement comme pour
$A_{\mathrm{s}}$ sauf que les états $0$ à $5$ sont tous marqués
finaux :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
\vskip0ptplus20ex\relax
S'agissant de $A_{\mathrm{z}}$, on a de nouveau affaire à un « vrai »
non-déterminisme et on applique donc l'algorithme de déterminisation
vu en cours, qui donne (en omettant les accolades dans le nommage des
états) :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)]
\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$};
\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$};
\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2,4$};
\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
\node (q245) at (120bp,-120bp) [draw,circle,state,accepting below] {\small $2,4,5$};
\node (qbot) at (300bp,-90bp) [draw,circle,state] {$\varnothing$};
\draw[->] (qI) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (qI) to[out=270,in=150] node[auto,swap]{$b$} (q245);
\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot);
\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5);
\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto,near start]{$a$} (qbot);
\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
\draw[->] (q245) to[out=60,in=240] node[auto]{$a$} (q3);
\draw[->] (q245) to[out=30,in=240] node[auto,swap,very near end]{$b$} (q5);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
où on a noté $I$ au lieu de $\{0,1,2,3,4,5\}$.
\end{corrige}

\textbf{(e)} Pour $A = A_{\mathrm{z}}$ (et seulement celui-ci),
minimiser le DFA trouvé à la question (d).

\begin{corrige}
On a affaire à un DFA complet sans état inaccessible : on va le
minimiser avec l'algorithme de Moore.

Dans une première étape, on fait deux classes d'état : celle des états
finaux, c'est-à-dire $I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$
et celle des états non-finaux, c'est-à-dire le seul
état $\varnothing$.

Séparons maintenant les états selon la cible de la transition
étiquetée par $a$ : la classe formée de
$I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ se scinde en deux :
$I,\{2,4\},\{2,4,5\}$ d'une part, où elle mène à un état final, et
$\{1,3\},\{3\},\{4\},\{5\}$ d'autre part, où elle mène à un état
non-final.  La cible de la transition étiquetée par $b$, pour sa part,
sépare $\{5\}$ de tous les autres états (le seul où elle mène à un
état non-final).  À ce stade, on a quatre classes : la classe formée
de $I,\{2,4\},\{2,4,5\}$, celle de $\{1,3\},\{3\},\{4\}$, et deux
classes singleton, $\{5\}$ et $\varnothing$.

À l'étape suivante, la cible de la transition étiquetée par $a$ ne
sépare rien (les états de la première classe mènent à la seconde et
les états de la seconde mènent au puits).  La cible de la transition
étiquetée par $b$, en revanche, sépare la classe formée de
$I,\{2,4\},\{2,4,5\}$ en $I$ d'une part (qui mène à cette même classe)
et $\{2,4\},\{2,4,5\}$ de l'autre (qui mène à $\{5\}$) ; et elle
sépare la classe formée de $\{1,3\},\{3\},\{4\}$ en trois (puisque les
cibles sont dans trois classes distinctes).  À ce stade, les seuls
états qui n'ont pas été séparés sont $\{2,4\}$ et $\{2,4,5\}$.  Or
comme ils ont exactement les mêmes cibles de transitions étiquetées
par $a$ et $b$, ils ne sont pas séparés, donc l'algorithme s'applique
ici : il fusionne exactement deux états, à savoir
$\{2,4\}$ et $\{2,4,5\}$, en un seul, que nous noterons $B$ :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)]
\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$};
\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$};
\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$B$};
\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\varnothing$};
\draw[->] (qI) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (qI) to[out=60,in=120] node[auto]{$b$} (q2);
\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot);
\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5);
\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

\textbf{(f)} Parmi les douze langages $L_0,\ldots,L_{11}$, lesquels
sont rationnels ?  Lesquels sont algébriques ?  Lesquels sont
décidables ?  Lesquels sont semi-décidables ?  On justifiera la
réponse à chaque fois (par exemple en donnant une expression
rationnelle, un automate, une grammaire hors-contexte, un algorithme,
ou n'importe quel autre type d'argument permettant de conclure).

\begin{corrige}
Les langages $L_1,L_3,L_4,L_5,L_6,L_7,L_8,L_9$ sont rationnels car ils
sont reconnaissables : on a vu que les automates $A_{\mathrm{s}},
A_{\mathrm{w}}, A_{\mathrm{z}}, A_{\mathrm{v}}, A_{\mathrm{x}},
A_{\mathrm{u}}, A_{\mathrm{y}}, A_{\mathrm{t}}$ respectivement les
reconnaissent.  Il reste donc à traiter le cas de
$L_0,L_2,L_{10},L_{11}$.

Les langages $L_0$ et $L_2$ sont rationnels car ils sont finis (on
peut donner des expressions rationnelles pour les deux, à savoir
$\bot$ pour $L_0$ et, en énumérant systématiquement tous les
sous-mots, $\varepsilon | b | bb | a | ab | abb | bbb | ba | bab |
babb | aa | aab | aabb | abbb | aba | abab | ababb$ pour $L_2$, mais
ce n'est pas très intéressant et ce n'était pas demandé).

Le langage $L_{10} = \{w_0^i : i\in\mathbb{N}\} = L_1^*$ est rationnel
car il est l'étoile de Kleene d'un langage rationnel (si on préfère,
il est dénoté par l'expression rationnelle $(ababb){*}$).

Tous les langages $L_0$ à $L_{10}$ sont donc rationnels, et, en
particulier, algébriques, décidables et semi-décidables.

Reste à évoquer le cas du langage $L_{11} = \{b^i w_0 a^i :
i\in\mathbb{N}\}$.  Montrons qu'il n'est pas rationnel, et montrons
qu'il est algébrique.

Il n'est pas rationnel par le lemme de pompage.  En effet, supposons
par l'absurde que $\{b^i w_0 a^i : i\in\mathbb{N}\}$ soit rationnel,
et soit $k$ tel que donné par le lemme de pompage.  Considérons le mot
$t := b^k ababb a^k \in L_{11}$.  D'après la propriété de $k$, il
existe une factorisation $t = uvw$ vérifiant les propriétés garanties
par le lemme de pompage.  Le fait que $|uv|\leq k$, comme le préfixe
de longueur $k$ de $t$ est formé uniquement de la lettre $b$, assure
que $u = b^{\ell_1}$ et $v = b^{\ell_2}$ pour certains $\ell_1,\ell_2$
avec, de plus, $\ell_2 > 0$ (car $v\neq\varepsilon$) et
$\ell_1+\ell_2\leq k$.  On a alors $w = b^{k-\ell_1-\ell_2} ababb
a^k$, et $uv^iw = b^{k+(i-1)\ell_2} ababb a^k$.  Comme les mots de
$L_{11}$ ont la propriété nécessaire que leur nombre initial de $b$
(i.e., la longueur de leur plus long préfixe formé uniquement de la
lettre $b$) est égale à leur nombre final de $a$ (i.e., la longueur de
leur plus long suffixe formé uniquement de la lettre $a$), on devrait
avoir $k+(i-1)\ell_2 = k$, ce qui est une contradiction dès que $i\neq
1$.

En revanche, le langage $L_{11}$ est algébrique, car il est engendré
par la grammaire suivante d'axiome $S$ :
\[
S \rightarrow ababb \;|\; bSa
\]
Étant algébrique, le langage $L_{11}$ est décidable et semi-décidable.
(Au demeurant, il est facile de donner un algorithme qui décide si un
mot appartient à $L_{11}$ : on vérifie que son nombre initial de $b$
est égal à son nombre final de $a$ et, une fois ce fait vérifié, on
vérifie qu'une fois retiré le préfixe et le suffixe en question il
reste exactement le mot $ababb$.)

Pour résumer, tous les langages dont on a parlé sont algébriques,
décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels.
\end{corrige}


%
%
%

\exercice

{\footnotesize Dans cet exercice, les questions (1) et (2) sont
  indépendantes, et la question (4) ne dépend que de la
  question (2).\par}

\textbf{(1)} La fonction $h\colon \mathbb{N} \to \mathbb{N}$ suivante
est-elle calculable ?
\[
h(0) = 1\;\;,\;\;
h(1) = 10\;\;,\;\;
h(2) = 10^{10}\;\;,\;\;
h(3) = 10^{10^{\scriptstyle 10}}\;\;,\;\;
h(4) = 10^{10^{\scriptstyle 10^{\scriptstyle 10}}}\;\;,\;\;
\]
\[
\left.\begin{matrix} h(n) = 10^{\scriptstyle 10^{\scriptstyle \cdots^{\scriptstyle 10}}}\end{matrix}\right\} n
\]
(Autrement dit, $h(n)$ est une tour d'exponentielle de hauteur $n$ sur
le nombre $10$.  Bien sûr, $10^{10^{\scriptstyle 10}}$ se comprend
comme $10^{\big(10^{\scriptstyle 10}\big)}$.)

\begin{corrige}
La fonction $g\colon n\mapsto 10^n$ est calculable : en effet, on peut
exécuter une boucle à $n$ itérations en multipliant par $10$ la valeur
d'une variable en partant de $1$.  On en déduit que la fonction $h$
est calculable : en effet, on peut exécuter une boucle à $n$
itérations en appliquant la fonction $g$ à une variable en partant
de $1$.
\end{corrige}

\medskip

Fixons maintenant une numérotation (« codage de Gödel ») des
algorithmes prenant en entrée un entier et renvoyant un entier, et
appelons $\varphi_e(n)$ le résultat de l'exécution du programme codé
par l'entier $e$ sur l'entrée $n$, si cette exécution termine (et
$\varphi_e(n)$ non défini si cette exécution ne termine pas).
Considérons la fonction $b\colon \mathbb{N} \to \mathbb{N}$ suivante :
\[
b(n) = \max\{\varphi_e(n) : 0\leq e\leq n
\text{~et~}\varphi_e(n)\text{~défini}\}
\]
(Autrement dit, $b(n)$ est la plus grande des valeurs $\varphi_e(n)$
qui sont définies lorsque $e$ parcourt les entiers de $0$ à $n$.)

\textbf{(2)} On veut montrer que pour toute fonction calculable
$f\colon \mathbb{N} \to \mathbb{N}$, il existe un $n_0$ tel que pour
tout $n\geq n_0$ on ait $b(n) > f(n)$.  Supposons donc $f\colon
\mathbb{N} \to \mathbb{N}$ calculable.\quad\textbf{(a)} Expliquer
pourquoi il existe $p$ tel que $\varphi_p = f+1$ (c'est-à-dire
$\varphi_p(n) = f(n)+1$ pour tout $n$).\quad\textbf{(b)} En déduire
que $b(n) > f(n)$ lorsque $n\geq p$, et conclure.

\begin{corrige}
\textbf{(a)} La fonction $n \mapsto f(n)+1$ est calculable puisque $f$
l'est et que l'addition l'est.  Il existe donc un algorithme qui la
calcule, c'est-à-dire un $p$ tel que $\varphi_p = f+1$.

\textbf{(b)} Sachant que $\varphi_p = f+1$, si $n \geq p$, la valeur
$b(n)$ est le maximum des valeurs $\varphi_e(n)$ qui sont définies
lorsque $e$ et $n$ parcourent les entiers de $0$ à $n$.  En
particulier, puisque $0\leq p\leq n$, parmi ces entiers se trouve la
valeur $\varphi_p(n) = f(n)+1$ (qui est bien définie car $f$ est une
fonction totale ici).  On a donc $b(n) \geq \varphi_p(n) = f(n)+1 >
f(n)$.  On a bien montré que si $n \geq p$ alors $b(n) > f(n)$, ce qui
était voulu (pour $n_0 = p$).
\end{corrige}

\textbf{(3)} Montrer que (pour les fonctions $h$ et $b$ introduites
ci-dessus) :
\[
\lim_{n\to+\infty} \frac{b(n)}{h(n)} = +\infty
\]

\begin{corrige}
On souhaite montrer que pour tout $C>0$ il existe $n_0$ tel que si
$n\geq n_0$ alors $\frac{b(n)}{h(n)} > C$.  Pour cela, soit $C$ un
réel $>0$, et, quitte à l'augmenter encore un peu, on peut supposer
$C$ entier.  La fonction $C\cdot h$ (c'est-à-dire $n \mapsto C\cdot
h(n)$) est calculable car $h$ l'est (question (1)) et que la
multiplication l'est.  D'après la question (2), il existe $n_0$ tel
que pour tout $n\geq n_0$ on ait $b(n) > C\cdot h(n)$ : c'est ce qu'on
voulait montrer.
\end{corrige}

\textbf{(4)} On se propose ici de redémontrer l'indécidabilité du
problème de l'arrêt de manière légèrement différente de ce qui a été
vu en cours.  Supposons donc par l'absurde que le problème de l'arrêt
$H = \{(e,n) : \varphi_e(n)\text{~défini}\}$ soit
décidable.\quad\textbf{(a)} Montrer soigneusement, sous cette
hypothèse, que $b$ est calculable.\quad\textbf{(b)} Conclure.

\begin{corrige}
\textbf{(a)} Supposons par l'absurde qu'il existe un algorithme $T$
qui décide le problème de l'arrêt : autrement dit, donnés $e$ et $n$,
cet algorithme est censé terminer en temps fini et répondre « oui » si
le programme codé par $e$ termine sur l'entrée $n$, « non » sinon.  On
peut alors calculer $b(n)$ de la manière suivante : on démarre avec
$m=0$ et on effectue une boucle pour $e$ allant de $0$ à $n$, et pour
chacune des valeurs en question, on utilise $T$ pour savoir si
$\varphi_e(n)$ est défini, puis, \emph{si} c'est le cas, on caclcule
cette valeur $\varphi_e(n)$ au moyen de la machine universelle (ce
calcul termine en temps fini justement puisque $\varphi_e(n)$ est
défini), et on remplace la variable $m$ par $\max(m, \varphi_e(n))$.
À la fin de la boucle, on a bien calculé le max de toutes les valeurs
$\varphi_e(n)$ qui sont définies, c'est-à-dire $b(m)$.  La fonction
$b$ est donc calculable (de nouveau, sous l'hypothèse que le problème
de l'arrêt l'est).

\textbf{(b)} On a vu en (2) que pour toute fonction calculable $f$ il
existe un $n_0$ tel que pour tout $n\geq n_0$ on ait $b(n) > f(n)$.
Comme on vient de voir que (sous l'hypothèse que le problème de
l'arrêt est calculable) la fonction $b$ est calculable, en appliquant
ce résultat à $f = b$, il doit exister un $n_0$ tel que tout $n\geq
n_0$ on ait $b(n) > b(n)$, ce qui est absurde.  C'est donc que
l'hypothèse était absurde : le problème de l'arrêt n'est pas
décidable.
\end{corrige}


%
%
%
\end{document}